Графы - основные определения

Базовые понятия теории графов

Определения

Определение:
Граф G —это пара множеств $G=(V,E)$, где $V(G)$ — непустое конечное множество элементов, называемых вершинами графа, а $E$ — множество пар элементов из $V$ (необязательно различных), называемых ребрами графа. $E={(u,v) : u,v\in V }$ — множество ребер графа $G$, состоящее из пар вершин $(u,v)$. Ребро $(u,v)$ соединяет вершины $u$ и $v$.

Неформально это можно понимать как набор вершин (точек) и соединяющих их отрезков (рёбер).

Определение:
Смежные вершины —это вершины, соединенны ребром

Определение:
Степень вершины $d(v)$ —это количество ребер, исходящих из вершины $v$

Определение:
Инцидентность —это для ребра $(a,b)$ вершины $a$ и $b$ называются инцидентными. И наоборот, для вершины $a$ любое ребро $(a, x)$ (или $(x, a)$) называется инцидентным данной вершине $a$.

Замечание: две вершины, соединенные ребром, называются именно смежными, инцидентными их назвать нельзя.

Пример графа

Например, в графе на рисунке степень вершины $2$ равна $4$, вершины $4$ и $5$ смежны. Всего в графе $7$ вершин и $9$ ребер, то есть $|V| = 7$ и $|E| = 9$.

Определение:
Кратные ребра —это ребра, которые соединяют одну и ту же пару вершин. Если две вершины соединены более чем одним ребром, говорят, что граф содержит кратные ребра.

Определение:
Петля —это ребро, которое соединяет вершину саму с собой

Определение:
Простой граф —это граф, который не содержит петель и кратных ребер.

Если не сказано ничего про наличие петель и кратных ребер, мы будем всегда считать, что граф простой.

Определение:
Взвешенный граф —это граф, каждому ребру которого присвоено некоторое вещественное число, называемое весом ребра. Иными словами, на множестве ребер задана функция $W : E \rightarrow \mathbb{R}$.

Определение:
Ориентированный граф —это граф, в котором каждое ребро имеет направление, то есть ребро уже не просто соединяет две вершины, а в этой паре выбрано начало и конец ребра.

На рисунке изображен неориентированный граф. Его легко сделать ориентированным, если задать направление для каждого ребра. В некоторых задачах бывает удобно рассматривать неориентированный граф как ориентированный, но в котором у каждого ориентированного ребра $(u, v)$ (ведет из $u$ в $v$) есть парное ребро $(v, u)$. Получаем, что по ребру можно перемещаться в обе стороны, то есть граф неориентированный.

Определение:
Связный граф —это граф, в котором из любой вершины можно по ребрам дойти до любой другой. Относится только к неориентированным графам.

English, please

• вершина — vertex;
• вершины — vertices;
• ребро — edge;
• граф — graph;
• степень — degree;
• петля — loop;

Виды графов

Приведенные множества графов пересекаются.

• Дерево — связный граф без циклов;
• Планарный граф — граф, который можно разложить на плоскости так, чтобы его ребра не пересекались в точках, отличных от вершин;
• Полный граф — граф, в котором каждая вершина соединена с каждой;
• Двудольный граф — граф, вершины которого можно разделить на два множества таких, что ребра соединяют только вершины из разных множеств.