Лемма о рукопожатиях. Путь по ребрам

Графы

Объекты и связи

1) Города и дороги

2) Перекрестки и улицы

3) Люди и родственные отношения

Объекты графа – вершины

Связь – ребро

Vertex – вершина

Edge – ребра (пары вершин)

Граф в котором есть кратные ребра называется мультиграфом

Полный граф – граф где есть ребро между любыми двумя вершинами

Есть граф, где N вершин, нет кратных ребер и петель. Сколько ребер в нем?

Ориентированный граф – где установлено направление движения на ребрах

2 делит нацело 6 и 4

Взвешенные графы

Ориентированность и взвешенность друг от друга не зависит

Степень вершины – количество ребер входящих в вершину

В ориентированном графе степень вершины = полустепень исхода + полустепень захода

Лемма о рукопожатиях

N человек встретились и пожали друг другу руки

Количество людей, сделавших нечетное количество рукопожатий четно

Количество человек с нечетной степенью вершины четно.

Путь по ребрам

Граф называется связанным если из любой вершины есть путь в любую другую вершину.

У этого графа 2 компоненты связности.

Мост - это ребро, при удалении которого увеличивается количество компонент связности

Точка сочленения

Цикл – это замкнутый путь по ребрам без повторения ребер