Графы. Основные понятия. Виды графов

1.

Основные понятия

2.

Граф – это геометрическая фигура, состоящая из
точек, которые могут быть соединены линиями.
Точки называются вершинами графа, линии рёбрами графа.

3.

Виды графов
Неориентированный граф –
это граф, в котором у рёбер не
указано направление
Ориентированный граф – это
граф, рёбра которого имеют
направление (линия со стрелкой)
Взвешенный граф – это граф,
рёбра которого имеют вес
(дополнительную информацию)

4.

Виды графов
Изоморфные графы

5.

Графы. Основные понятия
Кратные рёбра
Изолированная
вершина
Петля
Граф, в котором есть кратные рёбра, называется
мультиграф

6.

Графы. Основные понятия
Количество ребер, выходящих из одной вершины,
называют степенью этой вершины
Будем считать, что петля выходит из вершины
дважды

7.

Вершина, имеющая чётную степень, называется
чётной вершиной, соответственно, вершина,
имеющая нечётную степень, называется нечётной
вершиной
Граф называется связным, если из любой
его вершины в любую другую можно
пройти по ребрам графа

8.

Теорема
Количество ребер графа равно половине суммы
степеней его вершин

9.

Теорема
Количество вершин нечётной степени любого графа
всегда чётно

10.

Виды графов
Граф называется полным, если любые две его
вершины соединены ребром

11.

Количество рёбер полного графа
Пусть полный граф имеет n вершин, тогда число
ребер равно:
n n 1
1
2