Теория графов

1. Теория графов

2.

Примеры применения графов в реальной жизни

3.

Примеры применения графов в реальной жизни

4.

Примеры применения графов в реальной жизни

5.

Примеры применения графов в реальной жизни

6.

Примеры применения графов в реальной жизни

7.

Примеры применения графов в реальной жизни

8.

Граф – конечное множество вершин и множество ребер
1
2
a
b
g
e
3
c
4
d
5

9.

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

10.

Первая теорема теории графов
Сумма степеней всех вершин равна удвоенному числу ребер
в графе

11.

Задача
Найти максимальное число ребер в простом графе, если у
него n вершин

12.

Задача
Найти максимальное число ребер в простом графе, если у
него n вершин
Решение:
M – число ребер
2 ∗