Тривиальные и полные графы

Граф, состоящий из одной вершины, называется тривиальным. Граф, состоящий из простого цикла с 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 ₂ , Е₂) рис. 3.6.1, где

V ₂ : = V ₁ & Е₂ : = Ø Е₁ : = { e Î V ₁ ´ V ₁ ê e Ï Е₁ }

G₁ØG

Рис 3.6.1 Дополнение

Объединением графов G ₁ ( V ₁ , Е₁) и G ₂ ( V ₂ , Е₂) (обозначение - G ₁ È G ₂ , при условии V ₁ Ç V ₁ = Æ, Е₁ Ç Е₂ = Æ) называется граф G(V,E), рис. 3.6.3

V : = V ₂ È V ₁ & Е : = Е₁ Ç Е₂

Рис. 3.6.3 Объединение графов

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 }

7. Стягивание подграфа А графа G ₁ ( V ₁ , Е₁) (обозначение - G ₁ ( V ₁ , Е₁) / А, при условии А Ì V ₁) даёт граф G ₂ ( V ₂ , Е₂), где

V₂ : = (V₁ \ A) È {v} &

E₂ : = E₁ \ { e = (u,w) ê u Î A Ú w Î A } È { e = (u,v) ê u Î Г ( А ) \ А }