Задания на Графы

Задачи на графы

Б

Д

Вершина

А

Г

В

Ребро

Графы. Примеры

Задача 1 Сколько путей от п. А до п. Д?

Б

А = 1

Б = 1

В = Г = 1+1=2

Д =1+2+2 = 5

Ответ: 5

1

Д

5

А

2

1

Г

2

В

Сколько путей от п. А до п. Е?

Б

2

Е

Б

1

Е

5

Д

Д

А

6

1

3

А

1

Г

1

1

1

1

В

Г

1

В

2+1+1+1 = 5

1+3+1+1 = 6

Задача 2 Сколько путей от п. А до п. Д. если нужно миновать п. Б?

Б

А = 1

В = Г = 1

Д = 1+ 1= 2

Ответ: 2

Д

2

А

1

1

1

Г

В

2 Сколько путей от п. А до п. Е. если нужно миновать п. Г ?

1 Сколько путей от п. А до п. Е. если нужно миновать п. В ?

Б

1

Е

Б

2

Е

Д

3

2

Д

А

4

1

А

1

Г

1

В

Г

1

В

1+2 = 3

2+1+1 = 4

Задача 3 Сколько путей от п. А до п. Д. Если надо проходить только через п. В?

Б

А = 1

В = Г = 2

Д = 2+ 2= 4

Ответ: 4

Д

1

4

А

2

2

1

Г

В

2 Сколько путей от п. А до п. Е. Если надо проходить только через п. Д?

1 Сколько путей от п. А до п. Е. Если надо проходить только через п. В?

Б

2

Е

Б

1

Е

Д

6

Д

А

6

2

2

А

1

Г

2

3

3

1

В

Г

1

В

2+2+2 = 6

3+3 = 6

1 Сколько существует различных путей из города А в город З?

2 Сколько существует различных путей, ведущих из города А в город М и НЕ проходящих через город Г?

3 Сколько существует различных путей, ведущих из города А в город М и проходящих через город В ?

3( * ) Сколько существует маршрутов из А в К, проходящих через один из пунктов Д или И, и не проходящих через оба этих пункта одновременно?

5