Неориентированный граф. Путь в графе. Цикл в графе. Степень вершины. Теорема о сумме степеней вершин графа. Полный граф; формула количества рёбер в полном графе.

Теория графов - это область математики, особенностью которой является геометрический подход к изучению объектов. Теория графов и алгоритмы на графах находят широкое применение в программировании. Понятие графа и понятие отношения – это равнообъёмные понятия. Теория графов предоставляет очень удобный язык для описания программных моделей. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы. Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок.

Первая работа по теории графов принадлежит Л Эйлеру (1736год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

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

Точки называются вершинами, или узлами графа, линии –ребрами.

Пусть дан граф G(V,Х), где V={V₁, V₂…}-множество его вершин, а Х (V₁, V₂) –его ребра.

Если элементы из Х рассматривать как неупорядоченные пары, то граф называется неориентированным, а пары называются рёбрами. Если же элементы из E рассматривать как упорядоченные, то граф ориентированный, а пары — дуги.

Если ребро графа G соединяет две его вершины, то говорят, что это ребро им инцидентно.

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

Два ребра называются смежными, если они имеют общую вершину.

На рис

- вершины V={А,В,С}

- ребра Х={ х₁, х_2, х_{3 ,} х_{4 ,}х₅}

-смежные вершины – А и В, А и С.

- вершинам А и С инцидентно ребро х₃

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

Граф G(V,E) может иметь ребра с одинаковыми парами вида Х (V,W).

Такие ребра называются кратными, или параллельными.

На рис кратные ребра х₁(А,В) и х₂(А,В)

Количество одинаковых пар вида х(V,W) называется кратностью ребра (V,W).

На рис ребро АС имеет кратность, равную 3, а ребро АВ- кратность, равную 2.

2. Число ребер инцидентных вершине А, называется степенью этой вершины и обозначается deg(A)(от англ. степень).

Если вершине инцидентна петля, то она даёт вклад в степень, равный двум, так как оба конца приходят в эту вершину.

На рис deg(A)=5, deg(В)=2, deg(С)=3

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

Граф, состоящий из изолированных вершин, называется нулевым графом. Для нуль-графа Х=Ø.

Вершина графа, имеющая степень, равную 1, называется висячей

Теорема:

В графе G(V,E) сумма степеней всех его вершин - число четное, равное удвоенному числу ребер графа:

где n=V-число вершин, m=X-число ребер графа.

Вершина называется четной, если её степень – четное число.

Вершина называется нечетной, если её степень – нечетное число.

На рис вершина В-четная , а вершины А и С – нечетные.

Теорема:

Число нечетных вершин любого графа – четно.

Следствие: Невозможно начертить граф с нечетным числом нечетных вершин.

4. Граф, в котором не построены все возможные ребра, называется неполным графом

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

Полный граф определяется только своими вершинами

Если полный граф имеет n вершин, то он будет иметь

ребер.

на рис полный граф

.

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

На рис а) Неполный граф, б) пунктирными линиями изображено дополнение графа до полного.

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

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

Число ребер маршрута называется длиной пути

Цепью называется путь, в котором нет повторяющихся рёбер.

Простой цепью называется путь без повторения вершин.

Путь называется циклом, если он замкнут, и рёбра в нём не повторяются.

Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом.

Расстоянием между двумя вершинами называется минимальная длина из всех возможных путей между этими вершинами при условии, что существует хотя бы один такой путь