Элементы теории графов

36. Некоторые основные понятия

Во многих прикладных задачах изучаются системы связей между раз­личными объектами. Объекты называются вершинами и отмечаются точ­ками или кружочками, а связи между вершинами — отрезками, соеди­няющими пары точек, и эти отрезки называются ребрами. Рассмотрение таких систем и приводит к понятию графа.

Граф представляет собой непустое конечное множество вершин V и множество ребер Е, оба конца которых принадлежат множеству V. Обо­значать граф будем G(V, Е) = (V, Е), V ^ 0, Е С V х V.

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

Вершины, которые не принадлежат ни одному ребру, называются изо­лированными.

Обозначать вершины будем буквами щ, г>2, г>з,..., v_n, т.е. V = {щ, v₂,...,v_n}.

Пусть t>i, V2 — вершины, е = (щ, и2) — соединяющее их ребро. Тогда вершина щ и ребро е инцидентны. Вершина г>2 и ребро е также инцидент­ны. Два ребра, инцидентные одной вершине, называются смежными. Две вершины, инцидентные одному ребру, также называются смежными.

Число вершин графа G обозначим р, а число ребер обозначим q p:p(G) = |F|; q:q(G) = \E\.

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

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

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

Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Степень графа еще называют его валентностью и обозначают d(v). Вершина графа, для которой d(v) = 0, является изолированной, для которой d(v) = 1 — висячей.

Вершина называется нечетной, если d{v) — нечетное число. Вершина называется четной, если d(v) — четное число. Степень каждой вершины полного графа на единицу меньше числа его вершин.

В графе G(V, Е) сумма степеней всех его вершин — число четное, рав¬ное удвоенному числу ребер графа. Число нечетных вершин любого графа четно. Во всяком графе с п вершинами, где п 2, всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.

Если в графе с п вершинами (п ^ 2) в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени п — 1.

38. Маршруты, цепи, циклы

Маршрутом в графе называется чередующаяся последовательность вершин и ребер, в которой любые два соседних элемента инцидентны:

Vo, V\, V\, б2, V2, ...,e_k, Vk-

Если Vo = Vk, то маршрут замкнут, в противном случае открыт.

Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью. В цепи vq, е\, щ, е%, т>2, •••> Ог> щ вершины Vo и щ называются кон­цами цепи, т. е. цепь концами vq и щ соединяет вершины Vq и щ. Цепь, соединяющая вершины vq и щ, обозначается (vq, щ). Очевидно, что если есть цепь, соединяющая вершины Vo и щ, то есть и простая цепь, соеди­няющая эти вершины. Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Число циклов в графе G(V, Е) обозначается z(G). Граф без циклов называется ациклическим.

Длиной маршрута называется количество ребер в нем (с повторени­ями). Если маршрут Af = Vq, е\, щ, б2, г>2,..., е*, щ, то длина маршрута М равна к, обозначается \М\ = к.

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

Две вершины графа называются связными, если существует соеди­няющая их простая цепь. В противном случае две вершины называются несвязными.

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

40. Ориентированные графы

Если элементу множества Е графа G(V, Е) — упорядоченные пары, то граф называется ориентированным или орграфом.

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

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

Степенью выхода вершины орграфа называется число выходящих из вершины ребер.

Степенью входа вершины орграфа называется число входящих в вер­шину ребер.

В орграфах в зависимости от сочетания степеней входа и выхода для данной вершины рассматриваются три случая.

Изолированной вершиной называется вершина, у которой и степень входа и степень выхода равны 0.

Источником называется вершина, степень выхода которой положи­тельна, а степень входа равна 0.

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

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

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

Замкнутый путь в ориентированном графе называется ориентирован­ным циклом или контуром.

Длиной пути называется число ребер в этом пути.

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

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

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

Мультиграфом называется граф, в котором пара вершин соединяется несколькими различными ребрами. Для ориентированного мультиграфа вершины Vj и Vj могут соединяться несколькими ребрами в каждом из направлений.