Графы: основные понятия — Дискретная математика

Основные понятия графа

Граф — это математическая структура, состоящая из множества вершин (узлов) и множества рёбер (связей), соединяющих эти вершины.

Граф обозначается как G = (V, E), где V — множество вершин, а E — множество рёбер.

Виды графов

: рёбра не имеют направления.
: каждое ребро имеет направление.
: граф с вершинами, но без рёбер.
: каждая пара вершин соединена рёбром.

Элементы графа

: элемент множества V.
: упорядоченная или неупорядоченная пара вершин.

Степень вершины

Степень вершины — количество инцидентных ей рёбер. Обозначается deg(v).

Свойства степени

Сумма степеней всех вершин равна удвоенному числу рёбер: $\sum_{v \in V} deg(v) = 2 |E|$ .

Маршруты и цепи

Маршрут — последовательность вершин, где каждая следующая связана с предыдущей рёбрами. Цепь — маршрут, в котором все вершины различны.

Связность графа

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

Подграфы

Подграф — часть исходного графа, включающая подмножество вершин и рёбер.

Изоморфизм графов

Два графа называются изоморфными, если их можно преобразовать друг в друга путём переименования вершин.

Пример задачи

Даны два графа G1 и G2. Определить, являются ли они изоморфными.

$G_1 = (\{a, b, c\}, \{ab, bc, ca\})$

$G_2 = (\{x, y, z\}, \{xy, yz, zx\})$

Решение

Переформулируем вершины одного графа через другой:

$a \rightarrow x$

$b \rightarrow y$

$c \rightarrow z$

Получаем, что графы совпадают после переименования вершин, следовательно, они изоморфны.