Графы. Основные определения

Тема: Графы, основные определения. Операции над графами.

Основные понятия теории графов

Графы возникли в восемнадцатом столетии, когда известный математик, Леонард Эйлер, пытался решить теперь уже классическую задачу о Кенигсбергских мостах. В то время в городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголь и друг с другом так, как показано на рисунке.

Задача состоит в следующем: осуществить прогулку по городу таким образом, чтобы, пройдя ровно по одному разу по каждому мосту, вернуть­ся в то же место, откуда начиналась прогулка. Решая эту задачу, Эйлер изобразил Кенигсберг в виде графа, отождествив его вершины с частями города, а ребра — с мостами, которыми связаны эти части.

Эйлеру удалось доказать, что искомого маршрута обхода города не существует.

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

ПРИМЕР

G(V, E),   V = {a, b, c, d},   E = {(a, b), (a, c),(a, d), (d, c)}.

Граф можно изобразить  диаграммой следующим образом:

Вершины  изобразить точками и кружками; ребра изобразить  линиями.

Число вершин обозначается  p(G) = |V|.

Число ребер графа   q(G) = |E|.

Пусть v и u вершины графа,  e = (v, u) это ребро графа, тогда вершина v и ребро e u называются инцидентными, вершина u и ребро e так же инцидентные.

Два ребра инцидентные одной вершине называются смежными.

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

Степенью или валентностью вершины называется количество ребер инцидентности этой вершины d(V).

Минимальная степень графа (G).

Максимальная степень графа (G).

Регулярным графом  степени k называется граф, степени всех вершин которого равны k .

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

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

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

Кратными ребрами называется ребра инцидентные одной и той же паре вершин.

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

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

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

Маршрутом в графе  называется  последовательность   вершин  и ребер  v₀ v₁ v₂ v₃ …v_n.

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

Маршрут, в котором все вершины различны, называется простой цепью.

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

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

Расстоянием между вершинами u и v  называется длина кратчайшей цепи d(u, v).

Кратчайшая цепь, соединяющая вершины называется геодезическая.

Диаметром графа G называется длина длиннейшей геодезической цепи.

Орграф.

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

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

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

Ребра при изображении ориентированных графов представляют стрелками.

Ребро ориентированного графа называется дугой.

Если вершины  u  и  v определяют дугу, то  вершина  u  называется антицидентом вершины  v.

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

Будем обозначать соответственно эти степени для некоторой вершины v  и .

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

Путем  v₀ v₁…v_n,  где v_i   антицендент v_i+1..

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

Граф, в котором нет контура, называется безконтурным.

Подграфы.

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

        Пусть       –   некоторое    подмножество    множества    вершин    графа  и пусть – множество всех ребер графа G, концевые вершины которых входят в . Тогда граф  называется вершинно-порожденным подграфом графа G. Обозначим через  некоторое подмножество множества ребер графа G и пусть  есть множество всех вершин графа G, инцидентных ребрам из . Тогда граф  называется реберно-порожденным подграфом  графа G.

 Рисунок 14.3.

        На рис. 14.3 изображены вершинно-порожденный подграф , представленного на рис. 11.1 (множество вершин ), и реберно–порожденный подграф  того же графа G (того же графа G ( множество ребер ).

ОПЕРАЦИИ  НАД  ГРАФАМИ.

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

        Пересечением графов  и  называется граф , множество вершин которого , а множество ребер .

      Кольцевой суммой графов  и  называется граф , порожденный на множестве ребер , т. е. на множестве ребер, присутствующих либо в , либо в , но не принадлежащих их пересечению