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

13. Графы

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

Поиск самого длинного пути в ориентированном графе

Задание 1 #14924

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Какова длина самого длинного пути из города А в город H? Длиной пути считать количество дорог, составляющих этот путь.

При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).

1. Зачёркиваем EH, потому что выгоднее пройти по EF-FH или EG-GH.

2. Зачёркиваем DF и CE потому что выгоднее пройти по CD-DE-EF.

3. Зачёркиваем BE и DG потому что выгоднее пройти по BD-DE-EG.

3. Зачёркиваем AD потому что выгоднее пройти по AC-CD или AB-BD.

Теперь нам не важно, пойдём мы по AB или по AC. По EG или по EF. Длина всегда будет одинакова и равна 5. Для примера возьмём путь AC-CD-DE-EF-FH.

Ответ: 5

Задание 2 #14926

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, X, J, Q, P, L, M, O, N. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Какова длина самого длинного пути из города А в город N? Длиной пути считать количество дорог, составляющих этот путь.

При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).

Нужно лишь зачеркнуть дороги CE, EG, GJ потому что вместо них можно пойти по верхним или нижним путям. Для примера возьмём нижние дороги.

Дороги QO, QM, MO лишние.

Наш путь: AC-CD-DE-EF-FG-GX-XJ-JQ-QL-LN с длиной 10.

Ответ: 10

Задание 3 #14927

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, H, K, I, J, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Какова длина самого длинного пути из города А в город G? Длиной пути считать количество дорог, составляющих этот путь.

При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).

Рисунок симметричен, можно рассматривать только верхнюю или только нижнюю его часть. Возьмём верхнюю.

1. Зачеркнём BJ т.к. выгоднее пройти через BD-DJ.

2. Зачеркнём JE т.к. выгоднее пройти через JK-KE.

Получаем путь AB-BD-DJ-JK-KE-EG длиной 6.

Ответ: 6

Задание 4 #14928

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, I, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Какова длина самого длинного пути из города А в город J? Длиной пути считать количество дорог, составляющих этот путь.

При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).

1. Зачеркнём HJ и IJ т.к. выгоднее пройти через HI-IK-KJ.

2. Зачеркнём FK т.к. выгоднее пройти через FH-HI-IK-KJ.

3. Зачеркнём BF, BG, GF т.к. выгоднее пройти через BC-CE-EF.

4. Зачеркнём AC т.к. выгоднее пройти через AB-BC или AD-DC.

5. Неважно, пойдём мы через D или через B.

Получаем путь AB-BC-CE-EF-FH-HI-IK-KJ длиной 8.

Ответ: 8

Задание 5 #14929

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Какова длина самого длинного пути из города А в город J? Длиной пути считать количество дорог, составляющих этот путь.

При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).

1. Зачеркнём очевидно невыгодный путь BF.

2. Нужно заметить, что выгоднее всего будет пройти через вертикальную дорогу DH.

Зачеркнём ненужные дороги и получим путь AB-BC-CD-DH-HI-IF-FJ длиной 7.

Ответ: 7

Задание 6 #14930

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Какова длина самого длинного пути из города А в город I? Длиной пути считать количество дорог, составляющих этот путь.

При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).

1. Зачеркнём очевидно невыгодный путь AE.

2. Зачеркнём DE т.к. выгоднее пройти через DF-FE.

3. Зачеркнём AD, AC т.к. выгоднее пройти через AB-BC-CD.

4. Зачеркнём AF, AG т.к. выгоднее пройти через AH-HG-GF.

5. Зачеркнём AH т.к. выгоднее пройти через AB-BH.

6. Зачеркнём BC т.к. выгоднее пройти через BH-HG-GC.

7. Зачеркнём GF т.к. выгоднее пройти через GC-CD-DF.

Получаем путь AB-BH-HG-GC-CD-DF-FE-EI длиной 8.

Ответ: 8

Задание 7 #14931

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, G, F. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Какова длина самого длинного пути из города А в город F? Длиной пути считать количество дорог, составляющих этот путь.

При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).

1. Зачеркнём CF, CE, DF т.к. из C в F выгоднее пройти через CD-DE-EF.

2. Зачеркнём AD, AC т.к. из A в D выгоднее пройти через AB-BC-CD.

3. Зачеркнём очевидно невыгодные дороги AG, GE.

Получаем путь AB-BC-CD-DE-EF длиной 5.

Ответ: 5