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

1.

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

2.

ЭЙЛЕРОВ ГРАФ.
ПРЕДСТАВЛЕНИЕ ОБ
ОРИЕНТИРОВАННЫХ
ГРАФАХ

3.

ЭЙЛЕРОВ ГРАФ
Давайте ещё раз вспомним, что такое путь в графе?
Путём в графе от вершины А до
вершины
B
назовём
такую
последовательность рёбер графа, в
которой каждые два соседних ребра
имеют общую вершину.
A
F
C
D
E
AD - DB или AC - CD - DB.
K
B

4.

ЭЙЛЕРОВ ГРАФ
Эйлеровым путём в графе называется путь, который
обходит все рёбра связного графа по одному разу.
Граф, в котором существует эйлеров путь, называется
эйлеровым графом.
Другими словами, граф, который можно нарисовать, не
отрывая карандаша от бумаги и проводя каждое ребро один
раз, называется эйлеровым.

5.

ПРИМЕР
Граф на рисунке можно нарисовать, проводя карандашом по
следующему пути: C - K - M - B - C - A - B. Это не
единственный возможный путь.
C
K
Найдите и другие
такие пути.
A
B
M

6.

Важное
условие
существования
эйлерова графа связано с наличием
определённого количества нечётных
вершин.
Леонард Эйлер в процессе решения
задачи
о
Кёнигсберских
мостах
сформулировал и доказал теорему.
Если в графе существует путь,
проходящий через все рёбра ровно по
одному разу, то в этом графе не
больше двух вершин нечётной степени.

7.

То есть,
Эйлеров граф может иметь либо две
нечётные вершины, либо не иметь
их совсем.
C
K
B
M
A
Давайте проверим!

8.

ПРЕДСТАВЛЕНИЕ ОБ
ОРИЕНТИРОВАННЫХ
ГРАФАХ
Ранее мы говорили про
пути в графе. Но иногда
важную
роль
играет
и
направление этого пути.

9.

Рассмотрим пример. Одноклассники Авдеев, Борисов,
Варахтин, Гринько, Данилевский и Еремин устроили турнир
по настольному теннису и решили играть каждый с каждым.
Турнир ещё не закончен; на графе отмечено, кто с кем
сыграл.
А
Хорошо видно, кто с кем играл, но не
видно, кто выиграл, а ведь это самое
интересное. Можно ли ввести в граф
дополнительную
информацию
о
результатах встреч?
Б
Е
Д
Г

10.

Ничьих в настольном теннисе не бывает, значит, каждая
встреча закончилась победой одного игрока. Вместо ребер
нарисуем стрелки. Каждая стрелка ведет от победителя к
проигравшему.
А
Ребра получили направления —
теперь это направленные ребра. В
неориентированном графе у ребра
два конца, а в ориентированном у
каждого ребра есть начало и конец.
Б
Е
Д
Г

11.

ОРИЕНТИРОВАННЫЙ
ГРАФ
Граф
называется
ориентированным,
направление каждого ребра.
C
K
B
A
N
если
указано
C
K
неориентированный
граф
ориентированный
граф
B
A
N

12.

Число рёбер, входящих в вершину, называют входящей
степенью вершины, а число рёбер исходящих —
исходящей степенью вершины.
C
K
B
A
N
Например,
входящая
степень вершины B равна
2, а исходящая - 0.
Определите входящие и
исходящие степени для
каждой вершины.

13.

В ориентированном графе сумма исходящих
степеней всех вершин равна сумме входящих
степеней всех вершин и равна числу рёбер.
C
K
Давайте проверим!
B
A
N

14.

ПРИМЕР
1
В турнире по теннису участвовали пять человек: Коля, Лёва,
Миша, Никита и Олег. Стрелка направлена от победителя к
проигравшему. Распределите места игроков: кто занял
первое место, второе и так далее.

15.

ПРИМЕР
2
В городе Энске предложили ввести одностороннее дорожное
движение. Рассмотрите граф, который его задает. Здесь
перекрестки обозначены буквами. Удобна ли такая схема
движения? Объясните почему.
А
Г
Ж
Б
Д
З
В
Е
И

16.

ПРИМЕР
3
Придумайте способ нарисовать одним росчерком (не отрывая
карандаш от бумаги и не проводя одну линию дважды):
а) ряд звёздочек
б) эмблему олимпийских игр
в) домики