Тема 2.2. Основные понятия теории графов

Графы. Основные определения. Элементы графов. Виды графов и операции над ними.

Методические указания по теме 2.2:

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

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

множества V (Е — множество ребер).

Соединения между узлами графа называются ребрами. Если узлы графа не нумерованы, то ребра являются неориентированными. У графа с нумерованными узлами ребра ориентированы. Ребрам могут быть присвоены определенные веса или метки. Число вершин графа A обозначим р, а число ребер – q:

p: = p (A): = | V |, q: = = q (A): = | E |;

Более простое определение графа - совокупность точек и линий, в которой каждая линия соединяет VÍдве точки. Для ориентированного графа E _x - конечный набор ориентированных ребер. Ребром может быть прямая или кривая линия. Ребра не могут иметь общих точек кроме вершин (узлов) графа. Замкнутая кривая в E может иметь только одну точку из множества V, а каждая незамкнутая кривая в E имеет ровно две точки множества V. Если V и E конечные множества, то и граф им соответствующий называется конечным. Граф называется вырожденным, если он не имеет ребер. Параллельными ребрами графа называются такие, которые имеют общие узлы начала и конца. Если ребро соединят две вершины, то говорят, что оно им инцидентно; вершины, соединенные ребром называются смежными. Две вершины, соединенные ребром, могут совпадать; такое ребро называется петлей. Число ребер, инцидентных вершине, называется степенью вершины. Если степень вершины равна 0, то получается изолированная графа. Если два ребра инцидентны одной и той же паре вершин, они называются кратными; граф, содержащий кратные ребра, называется мультиграфом.

Пусть v₁, v₂ — вершины, е = (v₁, v₂) — соединяющее их ребро. Множество вершин, смежных с вершиной v, называется множеством смежности вершины v и обозначается Г⁺(v).

Часто рассматриваются следующие родственные графам объекты:

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

2. Если элементом множества Е может быть пара одинаковых (не различных)элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом).

3. Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мулътиграфом.

4. Если элементами множества Е являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества Е называются гипердугами, а граф называется гиперграфом.

5. Если задана функция Е: V ® М и/или F: Е® М, то множество М называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа.

Виды графов и операции над ними:

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

Граф G'(V', Е') называется подграфом графа G(V, Е) (обозначается G' Ì G), если V' Ì V и/или Е' Ì Е. Если V' = V, то G ' называется остовным подграфом G. Если V' Ì V & Е' Ì Е & (V' ¹ V Ú Е' ¹ Е), то граф G ' называется собственным подграфом графа G. Подграф G'(V', Е') называется правильным подграфом графа G(V,Е), если G ' содержит все возможные ребра G.

Маршрутом в графе называется чередующаяся последовательность вершин и ребер в которой любые два соседних элемента инцидентны. Это определение подходит также для псевдо-, мульти- и орграфов. Для «обычного» графа достаточно указать только последовательность вершин или только последовательность ребер.Если v₀ = v_k, то маршрут замкнут, иначе открыт. Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью. В цепи v₀, e₁, v₁, e₂, v₂,…,e_k, v_k,вершины v₀ и v_k, называются концами цепи. Говорят, что цепь с концами и и v соединяет вершины и и v. Цепь, соединяющая вершины и и v, обозначается (и, v). Очевидно, что если есть цепь, соединяющая вершины и и v, то есть и простая цепь, соединяющая эти вершины.

Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Число циклов в графе G обозначается z(G). Граф без циклов называется ациклическим.

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

Два графа G₁(V₁, Е₁) и G₂(V₂, Е₂) изоморфны (обозначается G₁ ~ G₂), если существует биекция h: V₁ ® V₂, сохраняющая смежность: e₁ = (u, v) Î E₁ Þ e₂ = (h(u), h(v)) Î E₂,

e₂ = (u, v) Î E₂ Þ e₁ = (h^-1(u), h^-1(v)) Î E_1.Изоморфизм графов есть отношение эквивалентности.

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

Граф, состоящий из одной вершины, называется тривиальным. Граф, состоящий из простого цикла с k вершинами, обозначается С_k.

Граф, в котором каждая пара вершин смежная, называется полным. Полный граф с р вершинами обозначается К_р, он имеет максимально возможное число ребер. Полный подграф (некоторого графа) называется кликой (этого графа).

Двудольный граф (или биграф, или четный граф) — это граф G(V,Е), такой что множество V разбито на два непересекающихся множества V₁ и V₂ (V₁ È V₂ = V& V₁ Ç V₂) причем всякое ребро из Е инцидентно вершине из V₁ и вершине из V₂ (то есть соединяет вершину из V₁ с вершиной из V₂). Множества V₁ и V₂ называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V₁ и V₂, то он называется полным двудольным графом. Если | V₁ | = m и | V₁ | = п, то полный двудольный граф обозначается K_m,n Если в графе ориентировать все ребра, то получится орграф, который называется направленным. Направленный орграф, полученный из полного графа, называется турниром.

Название «турнир» имеет следующее происхождение. Рассмотрим спортивное соревнование для пар участников (или пар команд), где не предусматриваются ничьи. Пометим вершины орграфа участниками и проведем дуги от победителей к побежденным. В таком случае турнир в смысле теории графов — это как раз результат однокругового турнира в спортивном смысле.Если в орграфе полустепень захода некоторой вершины равна нулю (то есть d+(v) = 0), то такая вершина называется источником, если же нулю равна полу степень исхода (то есть d-(v) = 0), то вершина называется стоком. Направленный орграф с одним источником и одним стоком называется сетью.

Над графами можно выполнять следующие операции:

1. Дополнением графа G₁(V₁, Е₁) называется граф G(V₂, Е₂), где V₂: = V₁ & Е₂: = Ø Е₁: = {e Î V₁ ´ V₁ ê e Ï Е₁} G₁ØG
Объединением графов G₁(V₁, Е₁) и G₂(V₂, Е₂) (обозначение - G₁ È G₂, при условии V₁ ÇV₁ = Æ, Е₁ ÇЕ₂ = Æ) называется граф G(V,E), V: = V₂ È V₁ & Е: = Е₁ ÇЕ₂

2. Соединением графов G₁(V₁, Е₁) и G₂(V₂, Е₂) (обозначение - G₁(V₁, Е₁) + G₂(V₂, Е₂), при условии V₁Ç V₂ называется граф G(V,E), где V: = V₁Ç V₂& E: = Е₁ È Е₂ È { e = (v₁, v₂) êv₁ Î V₁ & v₂ Î V₂ }

3. Удаление вершины v из графа G₁(V₁, Е₁) (обозначение - G₁(V₁, Е₁) – v, при условии vÎV₁) даёт граф G₂(V₂, Е₂), где V₂: = V₁ \ { v } & E₂: = E₁ \ { e = (v₁, v₂) ê v₁ = v Ú v₂ = v }

4. Удаление ребра e из графа G₁(V₁, Е₁) (обозначение - G₁(V₁, Е₁) – e, при условии e Î E₁) даёт граф G₂(V₂, Е₂), где V₂: = V₁ & E₂: = E₁ \ {e}

5. Добавление вершины v в граф G₁(V₁, Е₁) (обозначение - G₁(V₁, Е₁) + v, при условии v Ï V₁) даёт граф G₂(V₂, Е₂), где V₂: = V₁ È { v } & E₂: = E₁

6. Добавление ребра e в граф G₁(V₁, Е₁) (обозначение - G₁(V₁, Е₁) + v, при условии e Ï E₁) даёт граф G₂(V₂, Е₂), где V₂: = V₁ & E₂: = E₁ È {e}