Решение задач по графам

1.

ВЕРОЯТНОСТЬ
И СТАТИКТИКА
7 КЛАСС

2.

ОТВЕТЬТЕ НА ВОПРОСЫ:
1. Сформулируйте,
какой
путь
называют Эйлеровым? Что такое
Эйлеров граф?
2. Своими
словами
объясните
свойство Эйлерова графа про
количество нечётных вершин.
3. Какой
граф
ориентированным?
называют

3.

РАБОТАЕМ УСТНО:
Определите по рисунку, является ли граф эйлеровым.
3
2
2
2
Эйлеров граф может иметь
либо
две
нечётные
вершины, либо не иметь их
совсем.
3
Количество вершин в графе, изображённом на рисунке,
равно 2, поэтому граф является Эйлеровым.

4.

РАБОТАЕМ УСТНО:
На рисунке изображён граф, а в вариантах ответа — пути
для этого графа. Выбери все варианты ответа, в которых
указан эйлеров путь.
C
N
M-K-C-N-B-M
K
N-K-M-C-N-B
K-C-N-B-M-K-N
B
M
N-B-M-K-C-N-K

5.

РАБОТАЕМ УСТНО:
В некоторой Волшебной стране есть несколько озёр,
соединённых между собой реками. Говорят, что количество
рек, которые вытекают из каждого озера, равно 41,
количество рек, впадающих в каждое озеро, равно 41. Может
ли такое быть? Представьте задачу в виде ориентированного
графа.
В ориентированном графе сумма исходящих степеней всех
вершин равна сумме входящих степеней всех вершин и
равна числу рёбер.
Ответ: да.

6.

РАБОТАЕМ ПИСЬМЕННО:
На рисунке — схема дорог, связывающих города А, Б, В, Г,
Д, Е, Ж, К, Л. По каждой дороге можно двигаться только в
одном
направлении,
указанном
стрелкой.
Сколько
существует различных путей из города А в город Л?
Д
Б
И
В
А
Г
Ж
Е
Л
К

7.

А
Б
В
Д
И
В
Л
Л
И
Л
Д
Л
Д
Ж
Л
Л
Л
В
И
Л
Г
Ж
Е
Ж
Л
Л
К
И
Л
Ответ: 13.
Д
Л
Ж
Л
Это задание ОГЭ по
информатике
можно
решить с помощью графов.
Схематично отобразите все
возможные
варианты
путей
с
помощью
ориентированного графа.
Путь начинается в пункте
А и заканчивается в Л.

8.

РАБОТАЕМ ПИСЬМЕННО:
Между населёнными пунктами А, В, С, D, Е построены
дороги, протяжённость которых (в километрах) приведена в
таблице:
Определите длину кратчайшего
пути между пунктами А и E.
Передвигаться можно только по
дорогам,
протяжённость
которых указана в таблице.
А В
А
2
В 2
С
3
Д 1 3
Е
С Д Е
1
3 3
3 2
3
2

9.

Построим граф и подпишем на ребрах протяженность пути.
А В
А
2
В 2
С
3
Д 1 3
Е
Ответ: 6.
С Д Е
1
3 3
3 2
3
2
А
2
3
В
Д
3
С
2
Е
1
С
Е
Д
3
2
В
3
3
С
3
С
2
Е
2
Е

10.

РАБОТАЕМ ПИСЬМЕННО:
На схеме нарисованы дороги между
четырьмя населёнными пунктами A, B, C,
D и указаны протяжённости данных дорог.
Определите, какие два пункта наиболее
удалены друг от друга (при условии, что
передвигаться можно только по указанным
на схеме дорогам). В ответе укажите
кратчайшее расстояние между этими
пунктами.
A
9
B
7
6
4
C
8
D

11.

Заметим, что наиболее удалены друг от друга пункты A и D.
Найдём все варианты маршрутов из A в D и выберем самый
короткий.
A-B-D: 13 км.
A
A
9
B
A-C-D: 15 км.
A-B-C-D: 23 км.
9
7
A-C-B-D:
17
км.
B
6
C
7
4
Ответ:
13.
6
4
8
6
C
8
D
C
8
D
DB
4
D
D