Дискретная математика. Основные понятия и определения графа и его элементов

Впервые понятие «граф» ввел в 1936 г. венгерский математик Денни Кёниг. Но первая работа по теории графов принадлежала перу великого Леонарда Эйлера и была написана еще в 1736 г.
С помощью графов изображаются схемы различных дорог, линии воздушных сообщений, газопроводов, теплотрасс, электросетей, а также микросхемы, дискретные многошаговые процессы, системы различных бинарных отношений, химические структурные формулы и другие диаграммы и схемы.
Без графов сложно анализировать классификации в различных науках.

Графом G = (V, X) называется пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек
Точки называются вершинами, или узлами, графа, линии — ребрами графа.

Примеры графов:
со смежными вершинами полный

Примеры графов:
со смежными ребрами с петлей

Пусть дан граф G = (V, X), где V = {V, W, ...} — конечное непустое множество его вершин, Х(V, W) — его ребра.
Если ребро графа G соединяет две его вершины V и W (т.е. (V, W) ∈ X), то говорят, что это ребро им инцидентно.
Две вершины графа называются смежными, если существует инцидентное им ребро.
Если граф G имеет ребро X(V, К), у которого начало и конец совпадают, то это ребро называется петлей.
Два ребра называются смежными, если они имеют общую вершину.

Записать:
смежные вершины:
смежные ребра:

Граф G ( V, X) может иметь ребра с одинаковыми парами вида X(V, W). Такие ребра называются кратными, или параллельными.
На рис. кратными являются , например, ребра х1(А,В) и х2(А,В).
Вершинам А и В инцидентны
ребра х1, х2. Количество
одинаковых пар вида х(V,W)
называется кратностью ребра (К, W).
На рис. ребро АС имеет кратность, равную 3, а ребро АВ — кратность, равную 2.

Число ребер, инцидентных вершине А, называется степенью этой вершины и обозначается deg(A) (от англ. degree — степень).
Если вершине инцидентна петля, она дает вклад в степень, равный двум, так как оба конца приходят в эту вершину.
На рис. вершина А имеет степень,
равную 1, вершина С-4,вершина D-2.
Записывается это в виде:
deg (A) = 1, deg (С) = 4,
deg (D) = 2.

Граф G4 содержит четыре вершины:
V= (A,В, С, D)
и шесть ребер Х= {р, q, r, s, t, и}.
Записать, чему равна
степень вершин:
deg (A) =
deg (В) =
deg (С) =
deg (D) =

Вершина графа, имеющая степень, равную нулю, называется изолированной.
Граф, состоящий из изолированных вершин, называется нуль-графом. Для нуль-графа Х= 0.
Вершина графа, имеющая степень, равную 1, называется висячей.
На рисунке:
вершины А, В, Е, G, Н
— висячие,
вершина N – изолированная
deg (N) = 0
N

Теорема 2.1.
В графе G(V,X) сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа:
где n = |V| — число вершин; m = |Х| — число ребер графа.
Вершина называется четной (нечетной), если ее степень – четное (нечетное) число.

Теорема 2.2. Число нечетных вершин любого графа — четно.
Следствие. Невозможно начертить граф с нечетным числом нечетных вершин.

Граф G называется полным, если любые две его различные вершины соединены одним и только одним ребром.
Таким образом, полный граф
определяется только своими
вершинами.
Пусть число вершин полного
графа n. Тогда степень любой вершины, очевидно, равна deg( V) = n - 1, а число ребер равно числу сочетаний из n по 2, т.е.

Дополнением графа G(V, X) называется граф
с теми же вершинами V, что и граф G, и имеющий те и только те ребра X’, которые необходимо добавить к графу G, чтобы он стал полным.
Очевидно, что граф с кратными ребрами не имеет дополнения. Например:
Очевидно, что дополнением полного графа будет нуль-граф, и наоборот.

Если все пары (Vi ,Vj) во множестве X являются
упорядоченными, т.е. кортежами длины 2, то граф называется ориентированным, орграфом, или направленным.
В таком случае ребра принято изображать стрелками.

Началом ребра называется вершина, указанная в кортеже первой, концом — вторая вершина этой пары (графически она указана стрелкой).
Ребра ориентированного графа имеют определенные фиксированные начало и конец и называются дугами.

Дуги орграфа называются кратными, если они имеют одинаковые начальные и конечные вершины, т.е. одинаковые направления. Например, кратны дуги u(V2, V3) и t(V2, V3)

Последовательность попарно инцидентных вершин Vi1 ,Vi2, ..., Vik неориентированного графа, т.е. последовательность ребер неориентированного графа, в которой вторая вершина предыдущего ребра совпадает с первой вершиной следующего, называется маршрутом.
Число ребер маршрута называется длиной маршрута.
Если начальная вершина маршрута совпадает с конечной, то такой маршрут называется замкнутым или циклом.

Расстоянием между двумя вершинами называется минимальная длина из всех возможных маршрутов между этими вершинами при условии, что существует хотя бы один такой м
Обозначается как d( V1V2) (от лат. distantio — расстояние) d( V1V2) = min| V1…..V2 |.
В маршруте одно и то же ребро может встретиться несколько раз. Если ребро встретилось только один раз, то маршрут
называется цепью.