Определение графа

Рассмотрим множество V, состоящее из соединенных некоторым образом точек. Элементы - вершины графа. Граф G=G(V) с множеством вершин V есть некоторое семейство сочетаний или пар вида

указывающие, какие вершины считаются соединенными.

В соответствии с геометрическим представлением графа каждая конкретная пара называется ребром (дугой) графа, и - концевые точки.

Можно определить понятие графа иначе, если представить себе некоторое множество точек плоскости V, называемых вершинами, и множество направленных отрезков E, соединяющих все или некоторые из вершин и называемых дугами. Т.е. математически граф G можно определить как пару множеств G=(V, E). Примерами графа может являться карта автомобильных или железных дорог, схемы соединения электрических цепей и т.п.

Можно считать, что множество направленных дуг E, соединяющих элементы множества V, отображают это множество само в себя. Поэтому можно считать граф заданным, если дано множество его вершин V и способ отображения Г множества V в V. Таким образом, граф G есть пара (V, Г), состоящая из множества V и отображения Г, заданного на этом множестве.

G=(V, Г). 2.1

Так, рис. 2.1 изображен граф, вершинами которого являются точки a, b, c, d, e, g, h, а дугами – отрезки (a, a), (c, b), (c,d), (c, e), (d, c), (d, d), (e, d), (g, h). Отображение приведенного графа будет определяться следующим образом: Г а={а}; Г b=Æ; Г с={b, d, e}; Г d={d,c}; Г е={d}; Г g={h}; Г h=Æ.

Рис. 2.1

Нетрудно видеть, что данное определение графа полностью совпадает с определением отношения на множестве.

Из сказанного можно определить, что графом G (V, E) называется совокупность двух множеств – непустого множества V (множества вершин) и множества Е его двухэлементных подмножеств множества V (Е – множество ребер).

В определении ребра можно принимать или не принимать во внимание порядок расположения двух его концов. Если этот порядок несуществен, т.е. если , то E есть неориентированное ребро, если же порядок существен, то D называют ориентированным ребром, и при этом v_i –начальная вершина, – конечная вершина.

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

неориентированный граф ориентированный граф

Рис. 2.2

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

Как в случае ориентированного, так и неориентированного ребра говорят, что ребро E=(v_i, v_j) инцидентно вершинам v _i и v_j, а также, что вершины v_i и v _j инцидентны ребру E. Две вершины, инцидентные одному ребру называются смежными. Вершина, не инцидентная никакому ребру, называется изолированной. Часто имеет смысл учитывать только неизолированные вершины.

Число инцидентных вершине u ребер называется степенью вершины и обозначается deg(u).

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

Наиболее важным случаем является полный граф G=(V, E), ребрами которого являются всевозможные пары () для двух различных вершин v _i и v_j из V. Полный граф с вершинами обозначается . На рис. 2.3 приведены полные графы и соответственно.

Рис. 2.3

В ориентированном полном графе имеются пары ребер, по одному в каждом направлении, соединяющие любые две различные вершины v_i и v_j. Ребра, у которых обе концевые точки совпадают L=(a, a) называются петлей.

(См. рис. 2.1 вершины “а”, “d”). Петля обычно считается неориентированной. Можно расширить полный граф до полного графа с петлями, добавляя петлю в каждой вершине.

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

Для каждого ориентированного графа существует обратный граф G ^*, получаемый изменением ориентации каждого из ребер графа G на противоположное.

Для каждого ориентированного графа существует также соотнесенный неориентированный граф G_u, ребрами которого являются ребра графа G, но уже без ориентации. Иногда удобно превратить неориентированный граф G в ориентированный граф G_d при помощи процесса удвоения, состоящего в замене каждого ребра G парой ребер с теми же вершинами и приписыванием им (ребрам) противоположных ориентаций.

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

Регулярные графы. Граф называется регулярным, или однородным, если все его вершины имеют одну и туже степень. Если степень каждой вершины равна k, то граф называют регулярным графом степени k. Например, полный граф n-го порядка есть регулярный граф степени k=n-1. Например, регулярные графы степени 3 называют кубическими, или 3-х валентными графами. В качестве примера на рис. 2.4 приведен кубический граф Петерсена.

Рис. 2.4

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

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

Подграфом G_A графа G=(V, Г) называется граф, в который входит лишь часть вершин графа G, образующих множество А, вместе с дугами, соединяющими эти вершины. Например, очерченная пунктиром область на рис. 2.1. Математически это записывается следующим образом:

G_A=(A, Г_А), 2.2

где 2.3

Частичным графом G_D по отношению к графу G=(V, Г) называется граф, содержащий только часть дуг графа G, т.е. определяемый условием

G_D=(V, D), 2.4

где

Например, если G=(V, Г) – карта автомобильных дорог России, тогда карта дорог Нижегородской области представляет собой подграф, а карта главных автомагистралей России – частичный граф.

Путем в графе G называют такую последовательность дуг d=(u₁, u₂, …u_k), в которой конец каждой предыдущей дуги совпадает с началом следующей. Путь d, последовательными вершинами которого являются вершины a, b, c, … m обозначается через d=(a, b, c, … m).

Длиной пути d=(u₁, u₂, … u_k) называют число l(d)=k, равное числу дуг, составляющих путь d. Иногда каждой дуге u_i приписывают некоторое число l(u_i), называемое длиной дуги. Тогда длина пути определяется как сумма длин дуг, составляющих путь

. 2.5

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

Контур – это конечный путь d=(v₁, v₂, … v_k), у которого начальная вершина х₁ совпадает с конечной v_k. При этом контур называется элементарным, если все его вершины различны (за исключением начальной и конечной, которые совпадают). Контур единичной длины, образованный дугой вида (а, а), называется петлей. Так, на рис. 2.1 (e, d, c, b) – путь, (с, e, d, c) – контур, (d, d) –петля.

Для неориентированного графа соответственно вводятся понятия цепи и цикла. Цепь (цикл) называется эйлеровой, если она проходит через все ребра по одному разу. Цепь (цикл) называется гамильтоновой, если она проходит через все вершины графа по одному разу.

Поиск по сайту: