ОГЭ задание 9

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

itgravity

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

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

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

Categorize

Options (6)

Б-В-А

А-Б-Д-Е

Е-Ж-Д-Е

Д-Е-А

Д-Е-А-Б

Б-В-Д-Ж

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

существуют

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

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

Multiple Select

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

• А — В — С 

• В — С — Д — В

• С — В — Е 

• A — В — Д

Labeling

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

Drag labels to their correct position on the image

1

10

4

2

3

7

5

6

8

9

Labeling

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

Drag labels to their correct position on the image

1

1

6

1

3

2

1

11

10

4

Labeling

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

Drag labels to their correct position on the image

3

5

1

4

1

3

1

3

1

1

Labeling

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

Drag labels to their correct position on the image

1

1

0

1

1

1

2

3

5

1

Шпаргалка

Labeling

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

Drag labels to their correct position on the image

2

2

2

1

1

0

3

1

4

6

Labeling

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

Drag labels to their correct position on the image

2

1

1

1

1

6

2

5

3

1

Labeling

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

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

Drag labels to their correct position on the image

2

3

0

0

4

2

2

1

5

1

Labeling

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

Drag labels to their correct position on the image

4

2

2

3

0

1

5

1

0

2

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

Fill in the Blanks

Сколькими путями можно добраться из города А в М через Д?

Fill in the Blanks

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

Шпаргалка

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

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