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

13. Графы

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

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

Задание 1 #14938

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

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

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

1. Зачеркнём CD т.к. из C в D выгоднее пройти через CJ-JD.

2. Зачеркнём EJ т.к. из E в J выгоднее пройти через EC-CJ.

3. Зачеркнём FC т.к. из F в C выгоднее пройти через FE-EC.

4. Зачеркнём AK, KG т.к. из A в G выгоднее пройти через AI-IH-HG.

5. Зачеркнём IF, HF т.к. из I в F выгоднее пройти через FH-HG-GF.

6. Зачеркнём AB, BC т.к. из A в C выгоднее пройти через AI-IH-HG-GF-FE-FC.

Получаем путь AI-IH-HG-GF-FE-EC-CJ-JD длиной 8.

Ответ: 8

Задание 2 #14934

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

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

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

1. Заметим, что через середину идти совсем невыгодно, зачеркнём все дороги оттуда.

2. Также заметим дорогу LN, делающую левое направление более выгодным. Зачеркнём все дороги справа.

3. Зачеркнём OQ т.к. из O в Q выгоднее пройти через OP-PQ.

4. Зачеркнём LM т.к. из L в M выгоднее пройти через LN-NM.

Получаем путь AB-BE-EI-IO-OP-PQ-QL-LN-NM длиной 9.

Ответ: 9

Задание 3 #14935

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

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

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

1. Зачеркнём FG т.к. из F в G выгоднее пройти через FI-IG.

2. Зачеркнём EG т.к. из E в G выгоднее пройти через EF-FI-IG.

3. Зачеркнём CF, CG т.к. из C в G выгоднее пройти через CE-EF-FI-IG.

4. Зачеркнём HI т.к. из H в I выгоднее пройти через HF-FI.

5. Зачеркнём DH, HF т.к. из D в G выгоднее пройти через DC-CE-EF-FI-IG.

Получаем путь AD-DC-CE-EF-FI-IG длиной 6.

Ответ: 6

Задание 4 #14936

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

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

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

1. Зачеркнём FL т.к. из F в L выгоднее пройти через FM-MN-NL.

2. Зачеркнём FM т.к. из F в M выгоднее пройти через FG-GI-IK-KM.

3. Зачеркнём KN т.к. из K в N выгоднее пройти через KM-MN.

4. Зачеркнём IJ т.к. из J в L выгоднее пройти через IK-KM-MN-NL.

5. Зачеркнём FC т.к. из A в C выгоднее пройти через AB-BC.

6. Зачеркнём GE т.к. из A в E выгоднее пройти через AB-BC-CD-DE.

Получаем 2 пути одинаковой длины 7: AB-BC-CD-DE-EH-HJ-JL и AF-FG-GI-IK-KM-MN-NL.

Ответ: 7

Задание 5 #14937

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

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

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

1. Зачеркнём TJ т.к. из T в J выгоднее пройти через TL-LJ.

2. Зачеркнём TL т.к. из T в L выгоднее пройти через TK-KL.

3. Зачеркнём IK т.к. из I в K выгоднее пройти через IT-TK.

4. Зачеркнём IT т.к. из I в T выгоднее пройти через IM-MT.

5. Зачеркнём IJ т.к. из I в J выгоднее пройти через IM-MT-TK-KL-LJ.

6. Зачеркнём AF т.к. из A в F выгоднее пройти через AE-EF.

7. Зачеркнём EC т.к. из E в C выгоднее пройти через EF-FC.

8. Зачеркнём AC т.к. из A в C выгоднее пройти через AE-EF-EC.

9. Зачеркнём AI т.к. из A в I выгоднее пройти через AE-EF-EC-CG-GI.

Получаем путь AE-EF-FC-CG-GI-IM-MT-TK-KL-LJ длиной 10.

Ответ: 10

Задание 6 #14940

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

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

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

1. Зачеркнём KL т.к. из K в L выгоднее пройти через KJ-JL.

2. Зачеркнём HJ, HL т.к. из H в L выгоднее пройти через HK-KJ-JL.

3. Зачеркнём EH т.к. из E в H выгоднее пройти через EG-GH.

4. Зачеркнём FH т.к. из F в H выгоднее пройти через FG-GH.

5. Зачеркнём DG т.к. из D в G выгоднее пройти через DE-EG или через DF-FG.

6. Зачеркнём CE т.к. из C в E выгоднее пройти через CD-DE.

7. Зачеркнём BF т.к. из B в F выгоднее пройти через BD-DF.

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

9. Зачеркнём EF, FI т.к. из E в I выгоднее пройти через ED-DG-GH-HI.

Получаем путь AI-IB-BD-DE-EG-GH-HK-KJ-JL длиной 9.

Ответ: 9

Задание 7 #14941

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

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

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

1. Зачеркнём GJ, GK, IK т.к. из G в K выгоднее пройти через GI-IJ-JK.

2. Зачеркнём FJ т.к. из F в J выгоднее пройти через FG-GI-IJ.

3. Зачеркнём HI т.к. из H в I выгоднее пройти через HG-GI.

4. Зачеркнём DG т.к. из D в G выгоднее пройти через DF-FG или через DH-HG.

5. Зачеркнём AE т.к. из A в E выгоднее пройти через AB-BE.

6. Зачеркнём AC т.к. из A в C выгоднее пройти через AB-BC.

Теперь у нас есть много различных путей с одинаковой длиной 7. Выберем например AB-BE-EF-FG-GI-IG-GK

Ответ: 7