Анализ схемы дорог: сборник задач
Листы материала (6)
Разбор листа 1
Задача 0
Граф: A, Б, В, Г, Д, Е, К. Рёбра: A→Б, A→В, A→Г, Б→Д, Б→В, Б→К, Г→В, Г→Е, В→Е, Д→К, Е→К. Путь ищем из A в К. Ответ: 6 Решение: paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=paths(A)+paths(Б)+paths(Г)=1+1+1=3; paths(Д)=paths(Б)=1; paths(Е)=paths(В)+paths(Г)=3+1=4; paths(К)=paths(Б)+paths(Д)+paths(Е)=1+1+4=6. Ответ: 6.
Задача 1
Граф: A, Б, В, Г, Д, Е, Ж, З, И, К, Л. Рёбра: A→Б, A→В, A→Г, A→Д, Б→Е, Б→В, В→Е, В→Г, Г→Ж, Д→Ж, Е→И, Е→З, Ж→З, Ж→К, З→Л, И→Л, К→Л. Путь из A в Л. Ответ: 12 Решение: 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(Е)=3; paths(З)=paths(Е)+paths(Ж)=3+3=6; paths(К)=paths(Ж)=3; paths(Л)=paths(З)+paths(И)+paths(К)=6+3+3=12. Ответ: 12.
Задача 2
Граф: A, Б, В, Г, Д, Е, Ж, К. Рёбра: A→Б, A→В, A→Г, A→Д, Б→Е, Б→В, В→Е, В→Г, В→К, Г→К, Д→Г, Д→Ж, Е→К, Ж→К. Путь из A в К. Ответ: 9 Решение: paths(A)=1; paths(Б)=1; paths(Д)=1; paths(В)=paths(A)+paths(Б)=1+1=2; paths(Г)=paths(В)+paths(Д)=2+1=3; paths(Ж)=paths(Д)=1; paths(Е)=paths(Б)+paths(В)=1+2=3; paths(К)=paths(В)+paths(Г)+paths(Е)+paths(Ж)=2+3+3+1=9. Ответ: 9.
Задача 3
Граф: A, B, C, D, E, F, G, H. Рёбра: A→B, A→E, A→F, A→G, B→C, E→C, E→D, F→D, F→G, F→H, G→H, C→D, H→D. Путь из A в D. Ответ: 7 Решение: paths(A)=1; paths(B)=1; paths(E)=1; paths(F)=1; paths(G)=paths(A)+paths(F)=1+1=2; paths(C)=paths(B)+paths(E)=1+1=2; paths(H)=paths(F)+paths(G)=1+2=3; paths(D)=paths(C)+paths(E)+paths(F)+paths(H)=2+1+1+3=7. Ответ: 7.
Разбор листа 2
Задача 4
Граф: A, B, C, D, E, F. Рёбра: A→C, A→E, A→D, A→B, B→D, D→E, D→F, E→C, E→F, C→F. Путь из A в F. Ответ: 9 Решение: paths(A)=1; paths(B)=1; paths(D)=paths(A)+paths(B)=1+1=2; paths(E)=paths(A)+paths(D)=1+2=3; paths(C)=paths(A)+paths(E)=1+3=4; paths(F)=paths(D)+paths(E)+paths(C)=2+3+4=9. Ответ: 9.
Задача 5
Граф: A, Б, В, Г, Д, Е, К. Рёбра: A→Б, A→В, A→Г, Б→Д, Б→В, Б→К, В→К, В→Е, Г→Е, Д→К, Е→К. Путь из A в К. Ответ: 7 Решение: paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=paths(A)+paths(Б)=1+1=2; paths(Д)=paths(Б)=1; paths(Е)=paths(В)+paths(Г)=2+1=3; paths(К)=paths(Б)+paths(В)+paths(Д)+paths(Е)=1+2+1+3=7. Ответ: 7.
Задача 6
Граф: A, B, C, D, E, F, G. Рёбра: A→B, A→F, F→E, F→G, G→E, E→B, E→C, E→D, B→C, C→D. Путь из A в D. Ответ: 7 Решение: paths(A)=1; paths(F)=paths(A)=1; paths(G)=paths(F)=1; paths(E)=paths(F)+paths(G)=1+1=2; paths(B)=paths(A)+paths(E)=1+2=3; paths(C)=paths(B)+paths(E)=3+2=5; paths(D)=paths(C)+paths(E)=5+2=7. Ответ: 7.
Задача 7
Граф: A, Б, В, Г, Д, Е, Ж, З. Рёбра: A→Б, A→Д, A→Е, Б→В, В→Г, Д→Б, Д→Г, Д→Ж, Е→Д, Е→Ж, Г→З, Ж→З. Путь из A в З. Ответ: 8 Решение: paths(A)=1; paths(Е)=paths(A)=1; paths(Д)=paths(A)+paths(Е)=1+1=2; paths(Б)=paths(A)+paths(Д)=1+2=3; paths(В)=paths(Б)=3; paths(Г)=paths(Д)+paths(В)=2+3=5; paths(Ж)=paths(Д)+paths(Е)=2+1=3; paths(З)=paths(Г)+paths(Ж)=5+3=8. Ответ: 8.
Разбор листа 3
Задача 8
Граф: A, Б, В, Г, Д, Е, Ж, К. Рёбра: A→Б, A→В, A→Г, A→Д, Б→Е, Б→В, В→Г, В→К, Г→К, Г→Ж, Д→Ж, Е→К, Ж→К. Путь из A в К. Ответ: 10 Решение: paths(A)=1; paths(Б)=1; paths(Д)=1; paths(В)=paths(A)+paths(Б)=1+1=2; paths(Г)=paths(A)+paths(В)=1+2=3; paths(Е)=paths(Б)=1; paths(Ж)=paths(Г)+paths(Д)=3+1=4; paths(К)=paths(В)+paths(Г)+paths(Е)+paths(Ж)=2+3+1+4=10. Ответ: 10.
Задача 9
Граф: A, B, C, D, E, F, G, H. Рёбра: A→B, A→D, A→E, D→B, D→G, E→D, E→F, F→G, B→C, C→H, G→H. Путь из A в H. Ответ: 6 Решение: paths(A)=1; paths(E)=paths(A)=1; paths(F)=paths(E)=1; paths(D)=paths(A)+paths(E)=1+1=2; paths(B)=paths(A)+paths(D)=1+2=3; paths(C)=paths(B)=3; paths(G)=paths(D)+paths(F)=2+1=3; paths(H)=paths(C)+paths(G)=3+3=6. Ответ: 6.
Задача 10
Граф: A, Б, Д, В(центр), Г, Е, К. Рёбра: A→Б, A→В, A→Г, Б→Д, Б→В, В→Д, В→К, В→Е, Г→В, Г→Е, Д→К, Е→К. Путь из A в К. Ответ: 11 Решение: 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(Г)=3+1=4; paths(К)=paths(В)+paths(Д)+paths(Е)=3+4+4=11. Ответ: 11.
Задача 11
Граф: A, Б, Д, В, Г, Е, К. Рёбра: A→Б, A→В, A→Г, Б→Д, Б→В, В→Д, В→К, Г→В, Г→Е, Д→К, Е→К. Путь из A в К. Ответ: 8 Решение: paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=paths(A)+paths(Б)+paths(Г)=1+1+1=3; paths(Д)=paths(Б)+paths(В)=1+3=4; paths(Е)=paths(Г)=1; paths(К)=paths(В)+paths(Д)+paths(Е)=3+4+1=8. Ответ: 8.
Разбор листа 4
Задача 12
Граф: A, Б, Д, В, Г, Е, К. Рёбра: A→Б, A→В, A→Г, Б→Д, Б→К, Г→В, Г→Е, В→К, Д→К, Е→К. Путь из A в К. Ответ: 5 Решение: paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=paths(A)+paths(Г)=1+1=2; paths(Д)=paths(Б)=1; paths(Е)=paths(Г)=1; paths(К)=paths(Б)+paths(В)+paths(Д)+paths(Е)=1+2+1+1=5. Ответ: 5.
Задача 13
Граф: A, Б, Д, В, Г, Е, К. Рёбра: A→Б, A→В, A→Г, Б→Д, Б→В, В→Д, В→К, Г→Е, Д→К, Е→К. Путь из A в К. Ответ: 6 Решение: paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=paths(A)+paths(Б)=1+1=2; paths(Д)=paths(Б)+paths(В)=1+2=3; paths(Е)=paths(Г)=1; paths(К)=paths(В)+paths(Д)+paths(Е)=2+3+1=6. Ответ: 6.
Задача 14
Граф: A, Б, В, Г, Д, Е, К. Рёбра: A→Б, A→В, A→Г, Б→Д, Б→В, Б→К, Г→В, Г→Е, В→К, Д→К, Е→К. Путь из A в К. Ответ: 6 Решение: 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(Д)+paths(Е)=1+3+1+1=6. Ответ: 6.
Задача 15
Граф: A, Б, В, Г, Д, Е, Ж, К. Рёбра: A→Б, A→В, A→Г, A→Д, Б→Е, В→Е, В→Г, В→К, Г→К, Г→Ж, Д→Г, Д→Ж, Е→К, Ж→К. Путь из A в К. Ответ: 10 Решение: paths(A)=1; paths(Б)=1; paths(Д)=1; paths(В)=paths(A)=1; paths(Г)=paths(A)+paths(В)+paths(Д)=1+1+1=3; paths(Е)=paths(Б)+paths(В)=1+1=2; paths(Ж)=paths(Г)+paths(Д)=3+1=4; paths(К)=paths(В)+paths(Г)+paths(Е)+paths(Ж)=1+3+2+4=10. Ответ: 10.
Разбор листа 5
Задача 16
Граф: A, B, C, D(центр), E, F, G. Рёбра: A→D, A→E, E→D, E→F, F→D, F→G, D→B, D→C, D→G, B→C, C→G. Путь из A в G. Ответ: 10 Решение: paths(A)=1; paths(E)=paths(A)=1; paths(F)=paths(E)=1; paths(D)=paths(A)+paths(E)+paths(F)=1+1+1=3; paths(B)=paths(D)=3; paths(C)=paths(D)+paths(B)=3+3=6; paths(G)=paths(D)+paths(F)+paths(C)=3+1+6=10. Ответ: 10.
Задача 17
Граф: A, Б, Е, В, Г, Д, Ж, К. Рёбра: A→Б, A→В, A→Г, A→Д, Б→Е, Б→В, В→Е, В→Г, В→К, Г→Ж, Д→Ж, Е→К, Ж→К. Путь из A в К. Ответ: 8 Решение: 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. Ответ: 8.
Задача 18
Граф: A, B, C, D, E, F, G, H. Рёбра: A→B, A→E, A→F, B→C, B→E, B→D, C→D, F→E, F→G, E→D, E→G, G→D, G→H, H→D. Путь из A в D. Ответ: 13 Решение: paths(A)=1; paths(F)=paths(A)=1; paths(B)=paths(A)=1; paths(E)=paths(A)+paths(B)+paths(F)=1+1+1=3; paths(C)=paths(B)=1; paths(G)=paths(E)+paths(F)=3+1=4; paths(H)=paths(G)=4; paths(D)=paths(B)+paths(C)+paths(E)+paths(G)+paths(H)=1+1+3+4+4=13. Ответ: 13.
Задача 19
Граф: A, B, C, D(центр), E, F, G. Рёбра: A→B, A→C, A→D, B→D, B→E, C→G, D→C, D→F, D→G, E→D, E→F, F→G. Путь из A в G. Ответ: 11 Решение: paths(A)=1; paths(B)=paths(A)=1; paths(E)=paths(B)=1; paths(D)=paths(A)+paths(B)+paths(E)=1+1+1=3; paths(C)=paths(A)+paths(D)=1+3=4; paths(F)=paths(D)+paths(E)=3+1=4; paths(G)=paths(C)+paths(D)+paths(F)=4+3+4=11. Ответ: 11.
Разбор листа 6
Задача 20
Граф: A, Б, В, Г, Д, Е, Ж. Рёбра: A→Б, A→Г, Г→Б, Г→В, Г→Е, В→Б, В→Д, В→Е, Б→Д, Д→Ж, Е→Ж. Путь из A в Ж. Ответ: 6 Решение: paths(A)=1; paths(Г)=paths(A)=1; paths(В)=paths(Г)=1; paths(Б)=paths(A)+paths(Г)+paths(В)=1+1+1=3; paths(Д)=paths(Б)+paths(В)=3+1=4; paths(Е)=paths(Г)+paths(В)=1+1=2; paths(Ж)=paths(Д)+paths(Е)=4+2=6. Ответ: 6.
Задача 21
Граф: A, Б, Д, В, Г, Е, К. Рёбра: A→Б, A→В, A→Г, Б→Д, Б→К, Г→В, Г→Е, В→К, Д→К, Е→К. Путь из A в К. Ответ: 5 Решение: paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=paths(A)+paths(Г)=1+1=2; paths(Д)=paths(Б)=1; paths(Е)=paths(Г)=1; paths(К)=paths(Б)+paths(В)+paths(Д)+paths(Е)=1+2+1+1=5. Ответ: 5.
Задача 22
Граф: A, Б, В, Г, Д, Е, Ж, З, И, К, Л. Рёбра: A→Б, A→В, A→Г, A→Д, Б→Е, Б→В, В→Е, В→З, В→Г, Г→З, Г→Ж, Д→Г, Д→Ж, Е→И, Е→З, Ж→З, Ж→К, З→Л, И→Л, К→Л. Путь из A в Л. Ответ: 22 Решение: 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(Е)=3; paths(З)=paths(В)+paths(Г)+paths(Е)+paths(Ж)=2+4+3+5=14; paths(К)=paths(Ж)=5; paths(Л)=paths(З)+paths(И)+paths(К)=14+3+5=22. Ответ: 22.
Задача 23
Граф: A, B, C, D, E, F, G. Рёбра: A→B, A→F, B→C, B→E, C→E, C→D, E→D, F→E, F→G, G→E. Путь из A в D. Ответ: 5 Решение: paths(A)=1; paths(F)=paths(A)=1; paths(B)=paths(A)=1; paths(G)=paths(F)=1; paths(C)=paths(B)=1; paths(E)=paths(B)+paths(C)+paths(F)+paths(G)=1+1+1+1=4; paths(D)=paths(C)+paths(E)=1+4=5. Ответ: 5.
analiz-shemy-dorog-sbornik-list-1.png
538.2 КБ
analiz-shemy-dorog-sbornik-list-2.png
523.6 КБ
analiz-shemy-dorog-sbornik-list-3.png
531.4 КБ
analiz-shemy-dorog-sbornik-list-4.png
482.7 КБ
analiz-shemy-dorog-sbornik-list-5.png
534.5 КБ
analiz-shemy-dorog-sbornik-list-6.png
547.4 КБ