ОГЭ задание 9

Графы
количество путей

itgravity

В ориентированном графе рёбрам всегда присвоены направления. В таком графе нельзя передвигаться по вершинам в любом направлении.

Например, путь А — В — E — A существует, а A — Е — В — А нет, т. к. нет пути из А в Е и из В в А.

Ориентированныйграф

Categorize

Options (6)

Б-В-А

А-Б-Д-Е

Е-Ж-Д-Е

Д-Е-А

Д-Е-А-Б

Б-В-Д-Ж

Определи, какие пути существуют в графе.

существуют

не существуют

Количество путей

Multiple Select

Каких путей не существует?

• А — В — С 

• В — С — Д — В

• С — В — Е 

• A — В — Д

Labelling

На рисунке схема дорог, связывающих города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

Drag labels to their correct position on the image

1

3

4

6

2

10

5

9

8

7

Labelling

Заполни количество путей в каждый из городов и определи итоговое количество путей из А в К.

Drag labels to their correct position on the image

3

10

1

4

6

11

1

1

1

2

Labelling

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

Drag labels to their correct position on the image

3

3

4

1

5

3

1

1

1

1

Labelling

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

Drag labels to their correct position on the image

5

3

1

2

1

1

1

0

1

1

Шпаргалка

Labelling

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

Drag labels to their correct position on the image

0

1

2

4

2

1

2

6

1

3

Labelling

Сколько будет различных путей из города А в город H, после того как дорогу от D до G закроют на ремонт?

Drag labels to their correct position on the image

6

1

1

5

1

3

2

1

1

2

Labelling

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

Мы рассмотрим ещё один вариант решения этой задачи. Сначала посчитаем пути до Г.

Drag labels to their correct position on the image

2

1

1

2

4

2

3

5

0

0

Labelling

Теперь оставим только вес вершины Г. Остальные меняем на 0. И считаем пути от Г до Ж.

Drag labels to their correct position on the image

2

2

1

0

5

4

1

0

3

2

форс-мажор: не получается сделать на компьютере
делаем на бумаге

Fill in the Blanks

Fill in the Blanks

Шпаргалка

Домашнее задание до 30 апреля 23:59
Яндекс.Учебник

Коды доступа у классного руководителя