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

13. Графы

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

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

Задание 1 #14923

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

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

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

1. Вместо FJ можем пройти по FH-HJ. Зачёркиваем FJ.

2. Вместо FH-HJ и FI-IJ можем пройти по FH-HI-IJ. Зачёркиваем HJ, FI.

3. Вместо GI выгоднее пройти по GF. Зачёркиваем GI.

4. Вместо EH выгоднее пройти по EF. Зачёркиваем EH.

5. Зачёркиваем BF, потому что выгоднее пройти по BG-GF или BE-EF.

6. Зачёркиваем DG потому что выгоднее пройти по DB-BG.

7. Зачёркиваем CE потому что выгоднее пройти по CB-BE.

8. Зачёркиваем AC, CB, AB, AD, потому что выгоднее пройти по AK-KD-DB.

Наш самый выгодный путь – AK-KD-DB-BG-GF-FH-HI-IJ, длина которого равна 8.

Ответ: 8

Задание 2 #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

Задание 3 #14925

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

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

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

Фигура на рисунке симметрична, поэтому можно выбрать левую или правую часть и рассмотреть только её. Например возьмём правую.

1. Зачёркиваем очевидно короткие пути AP и IP.

2. Зачёркиваем JO, JM и KO потому что выгоднее пройти по JK-KL-LM-MN-NO.

Наш путь: AI-IJ-JK-KL-LM-MN-NO-OP с длиной 8.

Ответ: 8

Задание 4 #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

Задание 5 #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

Задание 6 #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

Задание 7 #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