Графы дорог: практикум
Листы материала (6)
Разбор листа 1
Задача 0
Граф: A, B, C, D, E, F, G. Рёбра: A→B, A→C, C→B, C→F, B→D, B→E, D→G, E→F, E→G, F→G. Путь из A в G. Ответ: 7 Решение: Топологический порядок: A, C, B, D, E, F, G. paths(A)=1; paths(C)=paths(A)=1; paths(B)=paths(A)+paths(C)=1+1=2; paths(D)=paths(B)=2; paths(E)=paths(B)=2; paths(F)=paths(C)+paths(E)=1+2=3; paths(G)=paths(D)+paths(E)+paths(F)=2+2+3=7.
Задача 1
Граф: A, Б, В, Г, Д, Е, К. Рёбра: A→Б, A→Г, Б→Д, Б→В, Б→К, Г→В, Г→Е, В→К, В→Е, Д→К, Е→К. Путь из A в К. Ответ: 7 Решение: Топологический порядок: A, Б, Г, В, Д, Е, К. paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=paths(Б)+paths(Г)=1+1=2; paths(Д)=paths(Б)=1; paths(Е)=paths(Г)+paths(В)=1+2=3; paths(К)=paths(Б)+paths(В)+paths(Д)+paths(Е)=1+2+1+3=7.
Задача 2
Граф: A, Б, В, Г, Д, Е, Ж, З, И, К, Л (11 узлов). Рёбра: A→Б,В,Г,Д; Б→Е,В; В→Г,Е,З; Г→Ж,З; Д→Г,Ж; Е→И,З; Ж→З,К; З→Л; И→Л; К→Л. Путь из A в Л. Ответ: 22 Решение: Топологический порядок: A, Б, Д, В, Г, Е, Ж, З, И, К, Л. paths(A)=1; paths(Б)=1; paths(Д)=1; paths(В)=paths(A)+paths(Б)=1+1=2; paths(Г)=paths(A)+paths(В)+paths(Д)=1+2+1=4; paths(Е)=paths(Б)+paths(В)=1+2=3; paths(Ж)=paths(Г)+paths(Д)=4+1=5; paths(З)=paths(В)+paths(Г)+paths(Е)+paths(Ж)=2+4+3+5=14; paths(И)=paths(Е)=3; paths(К)=paths(Ж)=5; paths(Л)=paths(З)+paths(И)+paths(К)=14+3+5=22.
Задача 3
Тот же граф, что и в Задаче 2 (те же города и рёбра). Путь из A в Л. Ответ: 22 Решение: Совпадает с решением Задачи 2 (идентичная схема): итоговое значение paths(Л)=14+3+5=22.
Разбор листа 2
Задача 4
Граф: A, Б, В, Г, Д, Е, Ж, К. Рёбра: A→Б, A→В, A→Д, Б→Е, Б→В, В→Г, В→Е, Г→Ж, Г→К, Д→Ж, Е→К, Ж→К. Путь из A в К. Ответ: 8 Решение: Топологический порядок: A, Б, Д, В, Г, Е, Ж, К. paths(A)=1; paths(Б)=1; paths(Д)=1; paths(В)=paths(A)+paths(Б)=1+1=2; paths(Г)=paths(В)=2; paths(Е)=paths(Б)+paths(В)=1+2=3; paths(Ж)=paths(Г)+paths(Д)=2+1=3; paths(К)=paths(Г)+paths(Е)+paths(Ж)=2+3+3=8.
Задача 5
Граф: A, Б, В, Г, Д, Е, Ж, З, И, К (10 узлов, симметричная «решётка»). Рёбра: A→Б,В,Г; Б→Д,В; Г→Ж,В; Д→З,Е; Ж→И,Е; В→Е; Е→К,З; З→К; И→К. Путь из A в К. Ответ: 12 Решение: Топологический порядок: A, Б, Г, В, Д, Ж, Е, З, И, К. paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=paths(A)+paths(Б)+paths(Г)=1+1+1=3; paths(Д)=paths(Б)=1; paths(Ж)=paths(Г)=1; paths(Е)=paths(В)+paths(Д)+paths(Ж)=3+1+1=5; paths(З)=paths(Д)+paths(Е)=1+5=6; paths(И)=paths(Ж)=1; paths(К)=paths(Е)+paths(З)+paths(И)=5+6+1=12.
Задача 6
Граф: A, Б, В, Г, Д, Е, К («шестиугольник с центром»). Рёбра: A→Б,В,Г; Б→Д,В; Г→В,Е; В→Д,Е,К; Д→К; Е→К. Путь из A в К. Ответ: 11 Решение: Топологический порядок: A, Б, Г, В, Д, Е, К. paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=paths(A)+paths(Б)+paths(Г)=1+1+1=3; paths(Д)=paths(Б)+paths(В)=1+3=4; paths(Е)=paths(Г)+paths(В)=1+3=4; paths(К)=paths(В)+paths(Д)+paths(Е)=3+4+4=11.
Задача 7
Граф: A, Б, В, Г, Д, Е, Ж, З, И, К, Л (11 узлов). Рёбра: A→Б,В,Г,Д; Б→Е,В; В→Е,З; Г→Ж; Д→Г,Ж; Е→И,З; Ж→З,К; З→Л; И→Л; К→Л. Путь из A в Л. Ответ: 14 Решение: Топологический порядок: A, Б, Д, В, Г, Е, Ж, З, И, К, Л. paths(A)=1; paths(Б)=1; paths(Д)=1; paths(В)=paths(A)+paths(Б)=1+1=2; paths(Г)=paths(A)+paths(Д)=1+1=2; paths(Е)=paths(Б)+paths(В)=1+2=3; paths(Ж)=paths(Г)+paths(Д)=2+1=3; paths(З)=paths(В)+paths(Е)+paths(Ж)=2+3+3=8; paths(И)=paths(Е)=3; paths(К)=paths(Ж)=3; paths(Л)=paths(З)+paths(И)+paths(К)=8+3+3=14.
Разбор листа 3
Задача 8
Граф: A, Б, В, Г, Д, Е, К («шестиугольник с центром», как в Задаче 6, но без ребра В→К). Рёбра: A→Б,В,Г; Б→Д,В; Г→В,Е; В→Д,Е; Д→К; Е→К. Путь из A в К. Ответ: 8 Решение: Топологический порядок: A, Б, Г, В, Д, Е, К. paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=paths(A)+paths(Б)+paths(Г)=1+1+1=3; paths(Д)=paths(Б)+paths(В)=1+3=4; paths(Е)=paths(Г)+paths(В)=1+3=4; paths(К)=paths(Д)+paths(Е)=4+4=8.
Задача 9
Граф: A, Б, В, Г, Д, Е, К. Рёбра: A→Б,В,Г; Б→Д; Г→В,Д,Е,К; В→К; Д→К; Е→К. Путь из A в К. Ответ: 6 Решение: Топологический порядок: A, Б, Г, В, Д, Е, К. paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=paths(A)+paths(Г)=1+1=2; paths(Д)=paths(Б)+paths(Г)=1+1=2; paths(Е)=paths(Г)=1; paths(К)=paths(В)+paths(Д)+paths(Е)+paths(Г)=2+2+1+1=6.
Задача 10
Граф: A, Б, В, Г, Д, Е, Ж, З, И, К, Л (11 узлов). Рёбра: A→Б,В,Г,Д; Б→Е,В; В→Е,З; Г→З; Д→Г,Ж; Е→И,З; Ж→З,К; З→Л; И→Л; К→Л. Путь из A в Л. Ответ: 12 Решение: Топологический порядок: A, Б, Д, В, Г, Е, Ж, З, И, К, Л. paths(A)=1; paths(Б)=1; paths(Д)=1; paths(В)=paths(A)+paths(Б)=1+1=2; paths(Г)=paths(A)+paths(Д)=1+1=2; paths(Е)=paths(Б)+paths(В)=1+2=3; paths(Ж)=paths(Д)=1; paths(З)=paths(В)+paths(Г)+paths(Е)+paths(Ж)=2+2+3+1=8; paths(И)=paths(Е)=3; paths(К)=paths(Ж)=1; paths(Л)=paths(З)+paths(И)+paths(К)=8+3+1=12.
Задача 11
Граф: A, B, C, D, E, F, G, H (латиница). Рёбра: A→B, A→E, A→G, B→C, E→C, E→F, G→E, G→F, G→H, F→D, F→H, H→D, C→D. Путь из A в D. Ответ: 10 Решение: Топологический порядок: A, B, G, E, C, F, H, D. paths(A)=1; paths(B)=1; paths(G)=1; paths(E)=paths(A)+paths(G)=1+1=2; paths(C)=paths(B)+paths(E)=1+2=3; paths(F)=paths(E)+paths(G)=2+1=3; paths(H)=paths(G)+paths(F)=1+3=4; paths(D)=paths(C)+paths(F)+paths(H)=3+3+4=10.
Разбор листа 4
Задача 12
Граф: A, Б, В, Г, Д, Е, К. Рёбра: A→Б, A→Г, Б→Д, Б→В, Б→К, Г→В, Г→Е, Г→К, В→К, Д→К, Е→К. Путь из A в К. Ответ: 6 Решение: Топологический порядок: A, Б, Г, В, Д, Е, К. paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=paths(Б)+paths(Г)=1+1=2; paths(Д)=paths(Б)=1; paths(Е)=paths(Г)=1; paths(К)=paths(Б)+paths(Г)+paths(В)+paths(Д)+paths(Е)=1+1+2+1+1=6.
Задача 13
Граф: A, Б, В, Г, Д, Е, Ж, З, И, К, Л (11 узлов). Рёбра: A→Б,В,Г,Д; Б→Е,В; В→Г,З; Г→Ж; Д→Г,Ж; Е→И,З; Ж→З,К; З→Л; И→Л; К→Л. Путь из A в Л. Ответ: 14 Решение: Топологический порядок: A, Б, Д, В, Г, Е, Ж, З, И, К, Л. paths(A)=1; paths(Б)=1; paths(Д)=1; paths(В)=paths(A)+paths(Б)=1+1=2; paths(Г)=paths(A)+paths(В)+paths(Д)=1+2+1=4; paths(Е)=paths(Б)=1; paths(Ж)=paths(Г)+paths(Д)=4+1=5; paths(З)=paths(В)+paths(Е)+paths(Ж)=2+1+5=8; paths(И)=paths(Е)=1; paths(К)=paths(Ж)=5; paths(Л)=paths(З)+paths(И)+paths(К)=8+1+5=14.
Задача 15
Граф: A, Б, В, Г, Д, Е, Ж, З, И, К, Л — та же схема, что в Задаче 7 (В→Е и В→З, Г→Ж без ветвления на З). Путь из A в Л. Ответ: 14 Решение: Идентично Задаче 7: paths(Л)=paths(З)+paths(И)+paths(К)=8+3+3=14.
Задача 14
Граф: A, Б, В, Г, Д, Е, Ж, З, И, К, Л — та же схема, что в Задаче 7. Путь из A в Л. Ответ: 14 Решение: Идентично Задаче 7: paths(Л)=paths(З)+paths(И)+paths(К)=8+3+3=14.
Разбор листа 5
Задача 16
Граф: A, Б, В, Г, Д, Е, Ж, З. Рёбра: A→Б, A→Д, A→Е, Б→В, Д→Б, Д→В, Д→Г, Д→Ж, Г→В, Г→З, Е→Ж, Ж→З. Путь из A в З (узел В — тупиковый, не участвует в пути к З). Ответ: 3 Решение: Топологический порядок (для нужных узлов): A, Д, Г, Е, Ж, З. paths(A)=1; paths(Д)=paths(A)=1; paths(Г)=paths(Д)=1; paths(Е)=paths(A)=1; paths(Ж)=paths(Д)+paths(Е)=1+1=2; paths(З)=paths(Г)+paths(Ж)=1+2=3.
Задача 17
Граф: A, Б, В, Г, Д, Е, Ж. Рёбра: A→Б, A→В, A→Г, Б→Д, В→Б, Д→В, В→Д, Д→Е, Д→Ж, Г→В, В→Е, Г→Е, Е→Ж. Путь из A в Ж. Ответ: 13 Решение: Топологический порядок: A, Г, В, Б, Д, Е, Ж. paths(A)=1; paths(Г)=paths(A)=1; paths(В)=paths(A)+paths(Г)=1+1=2; paths(Б)=paths(A)+paths(В)=1+2=3; paths(Д)=paths(Б)+paths(В)=3+2=5; paths(Е)=paths(Д)+paths(В)+paths(Г)=5+2+1=8; paths(Ж)=paths(Д)+paths(Е)=5+8=13.
Задача 19
Граф: A, Б, В, Г, Д, Е, И, К. Рёбра: A→В, A→Г, Б→В, Г→Б, В→Д, В→И, В→К, Г→И, Г→Е, Г→К, Д→К, И→К, Е→К. Путь из A в К. Ответ: 9 Решение: Топологический порядок: A, Г, Б, В, Д, И, Е, К. paths(A)=1; paths(Г)=paths(A)=1; paths(Б)=paths(Г)=1; paths(В)=paths(A)+paths(Б)=1+1=2; paths(Д)=paths(В)=2; paths(И)=paths(В)+paths(Г)=2+1=3; paths(Е)=paths(Г)=1; paths(К)=paths(В)+paths(Д)+paths(И)+paths(Е)+paths(Г)=2+2+3+1+1=9.
Задача 18
Граф: A, Б, В, Г, Д, Е, Ж, К. Рёбра: A→Б, A→В, A→Г, A→Д, Б→В, Б→Е, В→Е, Г→К, Г→Ж, Д→Г, Д→Ж, Ж→К, Е→К. Путь из A в К. Ответ: 8 Решение: Топологический порядок: A, Б, Д, В, Г, Е, Ж, К. paths(A)=1; paths(Б)=1; paths(Д)=1; paths(В)=paths(A)+paths(Б)=1+1=2; paths(Г)=paths(A)+paths(Д)=1+1=2; paths(Е)=paths(Б)+paths(В)=1+2=3; paths(Ж)=paths(Г)+paths(Д)=2+1=3; paths(К)=paths(Г)+paths(Ж)+paths(Е)=2+3+3=8.
Разбор листа 6
Задача 20
Граф: A, B, C, D, E, F, G (латиница). Рёбра: A→B, A→C, B→D, B→E, C→E, C→F, D→G, E→F, E→G, F→G. Путь из A в G. Ответ: 6 Решение: Топологический порядок: A, B, C, D, E, F, G. paths(A)=1; paths(B)=1; paths(C)=1; paths(D)=paths(B)=1; paths(E)=paths(B)+paths(C)=1+1=2; paths(F)=paths(C)+paths(E)=1+2=3; paths(G)=paths(D)+paths(E)+paths(F)=1+2+3=6.
Задача 21
Граф: A, B, C, D, E, F, G (латиница). Рёбра: A→B, A→D, B→C, B→E, B→D, C→E, C→G, D→E, D→F, E→F, E→G. Путь из A в G (F — тупиковый узел). Ответ: 5 Решение: Топологический порядок: A, B, D, C, E, F, G. paths(A)=1; paths(B)=paths(A)=1; paths(D)=paths(A)+paths(B)=1+1=2; paths(C)=paths(B)=1; paths(E)=paths(B)+paths(C)+paths(D)=1+1+2=4; paths(G)=paths(C)+paths(E)=1+4=5.
Задача 22
Граф: A, Б, В, Г, Д, Е, Ж, З, И, К, Л (11 узлов) — та же схема, что в Задаче 13. Путь из A в Л. Ответ: 14 Решение: Идентично Задаче 13: paths(Л)=paths(З)+paths(И)+paths(К)=8+1+5=14.
Задача 23
Граф: A, Б, В, Г, Д, Е, К — та же схема, что в Задаче 6. Путь из A в К. Ответ: 11 Решение: Идентично Задаче 6: paths(К)=paths(В)+paths(Д)+paths(Е)=3+4+4=11.
grafy-dorog-praktikum-list-1.png
554.5 КБ
grafy-dorog-praktikum-list-2.png
547.8 КБ
grafy-dorog-praktikum-list-3.png
534.8 КБ
grafy-dorog-praktikum-list-4.png
566.2 КБ
grafy-dorog-praktikum-list-5.png
567.1 КБ
grafy-dorog-praktikum-list-6.png
549.3 КБ