Плоские графы. Эйлеровы графы. Гамильтовы графы. Орграфы

Пусть дано непустое множество X, состоящее из элементов, называемых точками (x ₁, x ₂, …), и на X задано множество отношений T, позволяющих установить соответствие между каждым элементом множества X и некоторым его подмножеством. Каждая пара точек x_i, x_j множества X, между которыми установлено отношение из множества T, называется ребром.

Определение 1. Непустое множество X и множество отношений T называется графом и обозначается G(X,T). Граф называется конечным, если множество X конечно.

С геометрической точки зрения граф G(X,T) представляет собой непустое множество точек (вершин) и множество отрезков (ребер), концы которых принадлежат данному множеству точек. При изображении графов ребра могут быть прямолинейны или криволинейны, длины ребер и расположение вершин произвольно. На следующих рисунках изображен один и тот же граф.

Ребра графа обозначают парой вершин (x ₁, x ₂).

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

Пример 1. Рассмотрим граф

Вершины x ₁, x ₄, x ₅ - изолированные (точка пересечения диагоналей не принадлежит графу). Граф может не иметь ребер. Тогда он состоит из изолированных точек.

Пример 2. Граф

состоит только из изолированных точек.

Определение 3. Две вершины называются смежными, если они соединены ребром, два различных ребра смежные, если они имеют общую вершину.

Определение 4. Ребро и любая из его вершин называются инцидентными.

Определение 5. Ребро графа G(X,T), у которого начальная и конечная вершины совпадают, называется петлей.

Пример 3. Рассмотрим граф

На рисунке ребро (x ₃, x ₃) является петлей.

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

Существуют различные способы задания конечного графа G(X,T). Пусть x ₁, x ₂, …, x_n - вершины графа, l ₁, l ₂, …, l_m - ребра графа.

Определение 6. Матрицей смежности называется матрица А_nn, у которой элемент a_ij равен количеству ребер, соединяющих вершины x_i и x_j.

Определение 7. Матрицей инцидентности называется матрица В_nm, у которой элемент b_ij равен 1, если вершина x_i инцидентна ребру l_j, и равен 0 в противном случае.

Пример 4. Для графа

матрицы смежности и инцидентности имеют вид

Графы можно задавать списками пар вершин, соединенных ребрами, или заданием для каждой вершины множества смежных вершин.