Подсчёт путей на графе: тренажёр
Листы материала (6)
Разбор листа 1
Задача 0
Граф: A→Б,В,Г,Д; Б→В,Е; В→Е,Г; Д→Г,Ж; Г→Ж,К; Е→К; Ж→К. Путь из А в К. Ответ: 12 Решение: paths(A)=1; paths(Б)=A=1; paths(В)=A+Б=2; paths(Д)=A=1; paths(Г)=A+В+Д=1+2+1=4; paths(Е)=Б+В=1+2=3; paths(Ж)=Д+Г=1+4=5; paths(К)=Е+Г+Ж=3+4+5=12
Задача 1
Граф: A→Б,В,Г,Д; Б→В,Е; В→Е,К; Д→Г,Ж; Г→К; Е→К; Ж→К. Путь из А в К. Ответ: 8 Решение: paths(A)=1; paths(Б)=1; paths(В)=A+Б=2; paths(Д)=1; paths(Г)=A+Д=1+1=2; paths(Е)=Б+В=1+2=3; paths(Ж)=Д=1; paths(К)=В+Г+Е+Ж=2+2+3+1=8
Задача 2
Граф (латиница): A→B,C,D; B→E,C,G; C→G,D; D→F; E→G; F→G. Путь из А в G. Ответ: 7 Решение: paths(A)=1; paths(B)=1; paths(C)=A+B=2; paths(D)=A+C=1+2=3; paths(E)=B=1; paths(F)=D=3; paths(G)=B+C+E+F=1+2+1+3=7
Задача 3
Большой граф (11 узлов): A→Б,В,Г,Д; Б→В,Е; В→Е,З; Г→В,Ж; Д→Г; Е→И,З; Ж→З; З→Л; И→Л; К→Л (Ж→К). Путь из А в Л. Ответ: 14 Решение: paths(A)=1; paths(Б)=1; paths(В)=A+Б=2; paths(Д)=1; paths(Г)=A+В+Д=1+2+1=4; paths(Е)=Б+В=1+2=3; paths(Ж)=Д=1; paths(З)=В+Г+Е+Ж=2+4+3+1=10; paths(И)=Е=3; paths(К)=Ж=1; paths(Л)=З+И+К=10+3+1=14
Разбор листа 2
Задача 4
Граф (11 узлов): A→Б,В,Г; Б→Д; В→Д,Е; Г→В,Ж; Д→З; Е→З,К; Ж→Е,И; З→К; И→К. Путь из А в К. Ответ: 10 Решение: paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=A+Г=1+1=2; paths(Д)=Б+В=1+2=3; paths(Ж)=Г=1; paths(Е)=В+Ж=2+1=3; paths(З)=Д+Е=3+3=6; paths(И)=Ж=1; paths(К)=Е+З+И=3+6+1=10
Задача 5
Граф (латиница): A→B,D,C; B→E; D→E,F,G; C→D; E→F; F→H; G→H. Путь из А в H. Ответ: 7 Решение: paths(A)=1; paths(B)=1; paths(C)=1; paths(D)=A+C=1+1=2; paths(E)=B+D=1+2=3; paths(F)=E+D=3+2=5; paths(G)=D=2; paths(H)=F+G=5+2=7
Задача 6
Граф: A→Б,В,Г,Д; Б→Е; В→Е,Г,К; Д→Г,Ж; Г→Ж; Е→К; Ж→К. Путь из А в К. Ответ: 7 Решение: paths(A)=1; paths(Б)=1; paths(В)=1; paths(Д)=1; paths(Г)=A+В+Д=1+1+1=3; paths(Е)=Б+В=1+1=2; paths(Ж)=Г+Д=3+1=4; paths(К)=Е+В+Ж=2+1+4=7
Задача 7
Граф (латиница): A→C,D,B; C→E,D; B→D,F; D→G,F; E→G,H; F→G; G→H. Путь из А в H. Ответ: 9 Решение: paths(A)=1; paths(C)=1; paths(B)=1; paths(D)=A+C+B=1+1+1=3; paths(E)=C=1; paths(F)=B+D=1+3=4; paths(G)=D+E+F=3+1+4=8; paths(H)=E+G=1+8=9
Разбор листа 3
Задача 8
Граф: A→Б,В,Г,Д; Б→В,Е; В→Е,К; Д→Г,Ж; Г→Ж; Е→К; Ж→К. Путь из А в К. Ответ: 8 Решение: paths(A)=1; paths(Б)=1; paths(В)=A+Б=2; paths(Д)=1; paths(Г)=A+Д=1+1=2; paths(Е)=Б+В=1+2=3; paths(Ж)=Г+Д=2+1=3; paths(К)=В+Е+Ж=2+3+3=8
Задача 9
Граф: A→Б,В,Г; Б→Д,В; Г→В,Е; В→К,Е; Д→К; Е→К. Путь из А в К. Ответ: 8 Решение: paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=A+Б+Г=1+1+1=3; paths(Д)=Б=1; paths(Е)=Г+В=1+3=4; paths(К)=Д+В+Е=1+3+4=8
Задача 10
Граф идентичен задаче 9: A→Б,В,Г; Б→Д,В; Г→В,Е; В→К,Е; Д→К; Е→К. Путь из А в К. Ответ: 8 Решение: paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=A+Б+Г=3; paths(Д)=Б=1; paths(Е)=Г+В=1+3=4; paths(К)=Д+В+Е=1+3+4=8
Задача 11
Большой граф (11 узлов): A→Б,В,Г,Д; Б→В,Е; В→Г,Е,З; Г→Ж,З; Д→Ж; Е→И,З; Ж→З,К; З→Л; И→Л; К→Л. Путь из А в Л. Ответ: 19 Решение: paths(A)=1; paths(Б)=1; paths(В)=A+Б=2; paths(Г)=A+В=1+2=3; paths(Д)=1; paths(Е)=Б+В=1+2=3; paths(Ж)=Г+Д=3+1=4; paths(З)=В+Г+Е+Ж=2+3+3+4=12; paths(И)=Е=3; paths(К)=Ж=4; paths(Л)=З+И+К=12+3+4=19
Разбор листа 4
Задача 12
Граф (латиница, 8 узлов): A→B,C,D,E; B→F; C→G; D→E,G; E→G,H; G→F; H→G,F. Путь из А в F. Ответ: 9 Решение: paths(A)=1; paths(B)=1; paths(C)=1; paths(D)=1; paths(E)=A+D=1+1=2; paths(H)=E=2; paths(G)=C+D+E+H=1+1+2+2=6; paths(F)=B+G+H=1+6+2=9
Задача 13
Граф: A→Б,В,Г; Б→Д,В; Г→В,Е; В→К,Е; Д→К; Е→К (идентичен задачам 9-10). Путь из А в К. Ответ: 8 Решение: paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=A+Б+Г=3; paths(Д)=Б=1; paths(Е)=Г+В=1+3=4; paths(К)=Д+В+Е=1+3+4=8
Задача 14
Граф: A→Б,В,Г; Б→В,Д; Г→В,Е,К; В→Д,К; Д→К; Е→К. Путь из А в К. Ответ: 9 Решение: paths(A)=1; paths(Б)=1; paths(Г)=1; paths(В)=A+Б+Г=1+1+1=3; paths(Д)=Б+В=1+3=4; paths(Е)=Г=1; paths(К)=Г+В+Д+Е=1+3+4+1=9
Задача 15
Большой граф (11 узлов): A→Б,В,Г,Д; Б→В,Е; В→Г,Е,З; Г→Ж,З; Д→Ж; Е→И,З; Ж→З,Л,К; З→Л; И→Л; К→Л. Путь из А в Л. Ответ: 23 Решение: paths(A)=1; paths(Б)=1; paths(В)=A+Б=2; paths(Г)=A+В=1+2=3; paths(Д)=1; paths(Е)=Б+В=1+2=3; paths(Ж)=Г+Д=3+1=4; paths(З)=В+Г+Е+Ж=2+3+3+4=12; paths(И)=Е=3; paths(К)=Ж=4; paths(Л)=З+И+Ж+К=12+3+4+4=23
Разбор листа 5
Задача 16
Большой граф (11 узлов), идентичен задаче 11: A→Б,В,Г,Д; Б→В,Е; В→Г,Е,З; Г→Ж,З; Д→Ж; Е→И,З; Ж→З,К; З→Л; И→Л; К→Л. Путь из А в Л. Ответ: 19 Решение: paths(A)=1; paths(Б)=1; paths(В)=A+Б=2; paths(Г)=A+В=1+2=3; paths(Д)=1; paths(Е)=Б+В=1+2=3; paths(Ж)=Г+Д=3+1=4; paths(З)=В+Г+Е+Ж=2+3+3+4=12; paths(И)=Е=3; paths(К)=Ж=4; paths(Л)=З+И+К=12+3+4=19
Задача 17
Граф (латиница): A→B,C,D; D→C,E; C→B,E; B→F; E→F. Путь из А в F. Ответ: 6 Решение: paths(A)=1; paths(D)=A=1; paths(C)=A+D=1+1=2; paths(B)=A+C=1+2=3; paths(E)=D+C=1+2=3; paths(F)=B+E=3+3=6
Задача 18
Большой граф (11 узлов): A→Б,В,Г,Д; Б→В,Е; В→Г,З; Г→Ж,З; Д→Ж; Е→З,И,Л; Ж→З,Л,К; З→Л; И→Л; К→Л. Путь из А в Л. Ответ: 20 Решение: paths(A)=1; paths(Б)=1; paths(В)=A+Б=2; paths(Г)=A+В=1+2=3; paths(Д)=1; paths(Е)=Б=1; paths(Ж)=Г+Д=3+1=4; paths(З)=В+Г+Е+Ж=2+3+1+4=10; paths(И)=Е=1; paths(К)=Ж=4; paths(Л)=З+Е+Ж+И+К=10+1+4+1+4=20
Задача 19
Граф (латиница): A→D,C,E,B; D→C,E,G; C→E; B→E,F; E→F,G; F→G. Путь из А в G. Ответ: 12 Решение: paths(A)=1; paths(D)=A=1; paths(C)=A+D=1+1=2; paths(B)=A=1; paths(E)=A+D+C+B=1+1+2+1=5; paths(F)=B+E=1+5=6; paths(G)=D+E+F=1+5+6=12
Разбор листа 6
Задача 20
Граф: A→Б,В,Г,Д; Б→В,Е; В→Г,Е,К; Г→Ж,К; Д→Ж; Е→К; Ж→К. Путь из А в К. Ответ: 12 Решение: paths(A)=1; paths(Б)=1; paths(В)=A+Б=2; paths(Д)=1; paths(Г)=A+В=1+2=3; paths(Е)=Б+В=1+2=3; paths(Ж)=Г+Д=3+1=4; paths(К)=В+Г+Е+Ж=2+3+3+4=12
Задача 21
Большой граф (11 узлов), идентичен задачам 11 и 16: A→Б,В,Г,Д; Б→В,Е; В→Г,Е,З; Г→Ж,З; Д→Ж; Е→И,З; Ж→З,К; З→Л; И→Л; К→Л. Путь из А в Л. Ответ: 19 Решение: paths(A)=1; paths(Б)=1; paths(В)=A+Б=2; paths(Г)=A+В=1+2=3; paths(Д)=1; paths(Е)=Б+В=1+2=3; paths(Ж)=Г+Д=3+1=4; paths(З)=В+Г+Е+Ж=2+3+3+4=12; paths(И)=Е=3; paths(К)=Ж=4; paths(Л)=З+И+К=12+3+4=19
Задача 22
Граф (латиница): A→B,C,D; C→B,D,E,G; B→E; D→F; E→G; F→G. Путь из А в G. Ответ: 6 Решение: paths(A)=1; paths(C)=A=1; paths(B)=A+C=1+1=2; paths(D)=A+C=1+1=2; paths(E)=C+B=1+2=3; paths(F)=D=2; paths(G)=C+E+F=1+3+2=6
Задача 23
Большой граф (11 узлов), идентичен задаче 18: A→Б,В,Г,Д; Б→В,Е; В→Г,З; Г→Ж,З; Д→Ж; Е→З,И,Л; Ж→З,Л,К; З→Л; И→Л; К→Л. Путь из А в Л. Ответ: 20 Решение: paths(A)=1; paths(Б)=1; paths(В)=A+Б=2; paths(Г)=A+В=1+2=3; paths(Д)=1; paths(Е)=Б=1; paths(Ж)=Г+Д=3+1=4; paths(З)=В+Г+Е+Ж=2+3+1+4=10; paths(И)=Е=1; paths(К)=Ж=4; paths(Л)=З+Е+Ж+И+К=10+1+4+1+4=20
podschet-putej-na-grafe-trenazher-list-1.png
541.1 КБ
podschet-putej-na-grafe-trenazher-list-2.png
526.7 КБ
podschet-putej-na-grafe-trenazher-list-3.png
518.0 КБ
podschet-putej-na-grafe-trenazher-list-4.png
526.7 КБ
podschet-putej-na-grafe-trenazher-list-5.png
552.9 КБ
podschet-putej-na-grafe-trenazher-list-6.png
534.4 КБ