Теоретическая справка
Граф это графическая информационная модель, которая состоит из вершин, связанных линиями — рёбрами. Вершины графа могут изображаться кругами, овалами, точками, прямоугольниками, да чем угодно, хоть сердечками, просто буквами или загагулинами. Граф называется взвешенным, если его вершины или рёбра характеризуются некоторой дополнительной информацией — весами вершин или рёбер (например расстояние между двумя точками — это вес ребра графа).
Табличные информационные модели так же важны как и графические. В табличных информационных моделях информация об объектах представляется в виде прямоугольной таблицы, состоящей из столбцов и строк.
Вам хорошо известно табличное представление расписания уроков, в табличной форме представляются расписания движения автобусов, самолётов, поездов и многое другое.
И если мне необходимо проложить маршрут по карте, я возьму линейку, бумажную карту и проложу кратчайший маршрут (мое зрение сделает 80% работы).
Но что если я хочу создать программу, которая прокладывает кратчайший маршрут из пунтка А в пункт Б? К сожалению программы еще не умеют анализировать картинки и изображения, однако они хорошо обрабатывают числовые данные, особенно если они представлены в виде таблицы.
Это таже информация, что и в синем графе выше. Есть города с условными именами A, B, C, D, E они связаны дорогами, протяженность которых указана на пересечении столбцов и строк (Из А в В = 50), но компьютеру таблицу анализировать проще, однако человеку проще анализировать граф.
Для решения задания нам необходимо преобразовать табличную информацию в граф.
- анализируем первую строчку: город А связан с городом В (расстояние = 2), город А связан с городом С (расстояние = 5), город А связан с городом D (расстояние = 1). Строим граф:
- анализируем вторую строчку: город B связан с городом A (расстояние = 2 на графе информация уже есть), город В связан с городом С (расстояние = 1). Достроим граф:
- анализируем третью строчку: город С связан с городом А (расстояние = 5 на графе информация уже есть), город С связан с городом В (расстояние = 1 на графе информация уже есть), город С связан с городом D (расстояние = 3), город С связан с городом Е (расстояние = 2). Достроим граф:
- анализируем четвертую строчку: город D связан с городом A (расстояние = 1 на графе информация уже есть), город D связан с городом С (расстояние = 3 на графе информация уже есть).
- анализируем пятую строчку: город Е связан с городом С (расстояние = 2 на графе информация уже есть)
- анализируем граф и находим кратчайший путь из А в Е: А-В-С-Е складываем расстояния 2+1+2=5.
Задачи для тренировки
1.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
| A | B | C | D | E | |
| A | |||||
| B | |||||
| C | |||||
| D | |||||
| E |
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 5 2) 6 3) 7 4) 8
2.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 7 2) 8 3) 9 4) 10
3.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 9 2) 10 3) 11 4) 12
4.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 5 2) 6 3) 7 4) 9
5.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 8 2) 9 3) 10 4) 11
6.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 9 2) 10 3) 11 4) 12
7.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 9 2) 8 3) 7 4) 6
8.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 4 2) 5 3) 6 4) 7
9.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 6 2) 7 3) 8 4) 9
10.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 5 2) 6 3) 7 4) 8
11.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 6 2) 7 3) 8 4) 9
12.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 6 2) 7 3) 8 4) 9
13.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 6 2) 7 3) 8 4) 9
14.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 4 2) 5 3) 6 4) 7
15.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 7 2) 8 3) 9 4) 10
16.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 13 2) 12 3) 11 4) 10
17.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 9 2) 11 3) 13 4) 15
18.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 5 2) 6 3) 7 4) 4
19.Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена в таблице:
Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 5 2) 6 3) 7 4) 4
20.Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 5 2) 6 3) 7 4) 8
21.Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена в таблице:
Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 5 2) 6 3) 7 4) 9
