Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

3. Графы через матрицу смежности

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

Оптимизация маршрута с помощью матрицы смежности

Задание 1 #8329


Между населёнными пунктами A, B, C, D, E, F, G построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

 

Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).

Для удобства представим таблицу в виде графа.

Начнем из пункта А. Из него мы можем попасть в B, С и сразу в G. Запомним, что A-G = 21. Пункт В приведет только к пункту С. A-B-C = 6 + 1 = 7, A-C = 4. Т.к. в обоих случаях мы попадаем в пункт С, выбираем наиболее короткий путь: это прямой путь A-C = 4.

Из пункта C мы можем попасть в пункт D и в пункт G – нашу цель. До пункта C длина пути 4, из С в G – 27, то есть A-G = 31. Это больше, чем прямой путь, посчитанный ранее, поэтому это значение запоминать не будем.

Значит, идем в пункт D. A-D = A-C + 5 = 9. Из пункта D можем попасть в E, F.

Посмотрим, какой маршрут короче. Из пункта F мы можем попасть в E – и оттуда в G – и сразу в G. D-F-E-G = 8 + 1 + 8 = 17, D-F-G = 8 + 2 = 10. Из пункта E можем пойти в F – и потом в G – или сразу в G: D-E-F-G = 4 + 1 + 2 = 7, D-E-G = 4 + 8 = 12. Выбираем кратчайший маршрут: D-G = 7.

Итак, A-C = 4, D-G = 7, то есть A-G = 4 + 5 + 7 (учитываем дорогу C-D) = 16. Прямая дорога A-G = 21, а A-C-D-G = 16.

Значит, ответ – 16.

Ответ: 16

Задание 2 #8330

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Для удобства представим таблицу в виде графа:

Т.к. в пункт F можем попасть только из E, сейчас задача сводится к нахождению кратчайшего расстояния между А и Е.

Сейчас нужно аккуратно разобрать все случаи. Итак, если мы идем из А в В, до Е мы можем добраться следующими способами: A-B-E = 4 + 1 = 5, A-B-C-E = 4 + 7 + 4 = 15 – причем из графа видно, что в вершину D заходить не стоит: мы сделаем крюк.

Если мы идем из А в С, то до Е мы доходим так: А-С-Е = 2 + 4 = 6. Видим, что из А до Е наименьшее расстояние по маршруту A-B-E = 5. Тогда A-F = 5 + 2 = 7.

Ответ: 7

Задание 3 #8331

Между населёнными пунктами А, В, С, D, Е, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

Определите длину кратчайшего пути между пунктами А и G (при условии, что передвигаться можно только по построенным дорогам).

Для удобства представим таблицу в виде графа:

Прямой путь A-G = 34. Из А также можем попасть в B, D, C.

Из B в D можно попасть напрямую – длина 6, через С – длина 4 + 2 = 6, то есть из A через B в D – 4 + 6 = 10. Из A в D – напрямую за 15 или через C: 10 + 2 = 12. Тогда из A в D можно попасть по пути длиной 10.

Из D в G – по пути длиной 15 напрямую или через E и F. D-E-G = 3 + 9 = 12, D-E-F-G = 3 + 8 + 4 = 15, D-F-G = 11 + 4 = 15. То есть кратчайший путь из D в G – длиной 12. Тогда кратчайший путь из A в G = 10 + 12 = 22.

Ответ: 22

Задание 4 #8332

Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами А и G (при условии, что передвигаться можно только по построенным дорогам).

 

Для удобства представим таблицу в виде графа:

Прямой путь из A в G – 25, из A в C самый короткий путь – через B (прямой = 9, через B – 4 + 3 = 7), C-F-G = 13 + 1 = 14, прямой путь из C в G = 20 > 14, C-D-E-G = 2 + 4 + 4 = 10 < 14, то есть из C кратчайший путь в G = 10, а кратчайший путь в C = 7, то есть весь путь из A в G = 7 + 10 = 17 < 25 (прямой путь из A в G). Тогда наш ответ – 17.

Ответ: 17

Задание 5 #8333

Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых в километрах приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам). В ответе укажите только число.

Для удобства представим таблицу в виде графа:

Прямой путь из A в F = 11. Путь из A в В, как видим, никуда не ведет, поэтому его не рассматриваем. Рассмотрим все остальные пути.

Если пойдем в С, пути будут такие:

1) A-C-F = 8;

2) A-C-D-F = 9;

3) A-C-D-E-F = 19.

Если пойдем в D:

1) A-D-F = 9;

2) A-D-C-F = 12;

3) A-D-E-F = 19.

Если пойдем в E:

1) A-E-F = 10;

2) A-E-D-F = 6;

3) A-E-D-C-F = 9.

Видим, что кратчайший путь = 6.

Ответ: 6

Задание 6 #8334

Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет

 

Определите длину кратчайшего пути между пунктами A и G. Передвигаться можно только по указанным дорогам. В ответе укажите только число.

Для удобства представим таблицу в виде графа:

Из вершины A попасть в вершину D можно путем длины 5 (через В): прямой (длина = 6) и через С (длина = 2 + 5 + 1 = 8) больше, поэтому их мы не рассматриваем.

Из вершины D можно попасть в G через F – тогда длина пути = 7 + 7 = 14 – или через E – тогда длина = 9 + 5 = 14. То есть из D мы попадаем в G путем длины 14, тогда минимальный путь через D в G = 5 + 14 = 19.

Из C в G можно попасть за 8 (варианты, когда идем через D, уже рассмотрены выше – мы решили, что через С идти в D дольше, чем через B, поэтому этот вариант мы не рассматриваем). Попасть в С можно за 6: мы можем сделать это маршрутами A-D-C (длина = 6 + 1 = 7), A-B-D-C (длина = 2 + 3 + 1 = 6), A-B-C (длина = 2 + 5 = 7).

Значит, в С из А мы попадаем путем длины 6, а из С в G – 8. То есть из A в G через С – за 6 + 8 = 14 < 19 (путь через D). Значит, 14 – наш ответ.

Ответ: 14

Задание 7 #8335

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

Определите длину кратчайшего пути между пунктами A и F при условии, что передвигаться можно только по указанным в таблице дорогам.

Для удобства представим таблицу в виде графа:

Прямой путь из A в F = 16. Как видим из графа, через B и C мы можем пройти только в D, тогда определим наименьший путь из A в D: через B – 3 + 5 = 8, C – 4 + 2 = 6, прямой – 4. Итак, в D из A можно добраться путем длины 4.

Из D можно сразу добраться в F путем длины 10,а через E – путем длины 6 + 3 = 9. То есть через D добраться до F можно путем длины 4 + 9 = 13 < 16 (прямой путь из A в F). Значит, 13 – наш ответ.

Ответ: 13