В данном разделе рассматриваются различные частные случаи графов и водятся
операции над графами и их элементами. Заметим, что не все из используемых
обозначений операций над графами являются традиционными и общепринятыми.
| Определение |
|---|
| Граф, состоящий из одной вершины, называется тривиальным. |
|
Граф, состоящий из простого цикла с k вершинами, обозначается Ck. |
Пример
C3 — треугольник.
| Определение |
|---|
| Граф, в котором каждая пара вершин смежна, называется полным. |
Полный граф с р вершинами обозначается Кр, он имеет максимально возможное число ребер:
Полный подграф (некоторого графа) называется кликой (этого графа).
| Определение |
|---|
Двудольный граф (или биграф, или четный граф) — это граф G(V,E),
такой что множество V разбито на два непересекающихся множества
V1 и V2 (V1
 V2 = V) & ( V1 &
V2 =  ), причем всякое ребро из Е
инцидентно вершине из V1 и вершине из V2
(то есть соединяет вершину из V1 с вершиной из
V2). Множества V1 и V2
называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V1 и V2, то он называется полным двудольным графом. Если |V1| = m и |V2| = n, то полный двудольный граф обозначается Km,n. |
Пример
На рис. 9 приведена диаграмма графа К3,3.
| Теорема |
|---|
| Граф является двудольным тогда и только тогда, когда все его простые циклы имеют четную длину. |
Доказательство
Необходимость. От противного.
Пусть G(V1, V2; Е) — двудольный граф, и
v1, v2,..., v2k+1, v1 —
простой цикл нечетной длины. Пусть v1 
V1, тогда v2
V2, v3
V1, v4
V2, ..., v2k+1
V1.
Имеем: v1, v2k+1
V1 и (v1, v2k+1)
E, что противоречит двудольности.
Достаточность. Не ограничивая общности, можно считать, что G — связный
граф, поскольку каждую компоненту связности можно рассматривать отдельно.
Разобьем множество V на V1 и V2
с помощью следующей процедуры:
|
Вход: граф G(V, E). Выход: Множества V1 и V2 — доли графа. select v
V { произвольная вершина }V1: = v { в начале первая доля содержит v, ... } V2: =
{ ... а вторая пуста }for u
V \ {v} doif d (v, u) — четно then V1: = V1
{u} { в первую долю }else V2: = V2
{u} { во вторую долю }end if end for |
Далее от противного. Пусть есть две вершины в одной доле, соединенные ребром. Пусть для определенности u, w
V2, и (u, w)
Е.
Рассмотрим геодезические <v, u> и <v, w> (здесь v — та произвольная вершина, которая использовалась в алгоритме построения долей графа). Тогда длины | <v, u> | и | <v, w> | нечетны. Эти геодезические имеют общие вершины (по крайней мере, вершину v). Рассмотрим наиболее удаленную от v общую вершину геодезических <v, u> и <v, w> и обозначим ее v' (может оказаться так, что v = v'). Имеем: | <v', u> | + | <v', w> | = | <v, u> | + <v, w> | - 2 | <v, v'> | — четно, и v', ..., u, w, ..., v' — простой цикл нечетной длины, что противоречит условию. Если же u, w
V1, то длины | <v, u> | и | <v, w> | четны и аналогично имеем: v', ..., u, w, ..., v' — простой цикл нечетной длины.
Если в графе ориентировать все ребра, то получится орграф, который называется направленным.
| Определение |
|---|
| Направленный орграф, полученный из полного графа, называется турниром. |
| Отступление | Название “турнир” имеет следующее происхождение. Рассмотрим спортивное соревнование для пар участников (или пар команд), где не предусматриваются ничьи. Пометим вершины орграфа участниками и проведем дуги от победителей к побежденным. В таком случае турнир в смысле теории графов — это как раз результат одно-кругового турнира в спортивном смысле. |
|---|
Если в орграфе полустепень захода некоторой вершины равна нулю (то есть d+(v) = 0), то такая вершина, в которую не приходят дуги, называется источником, если же нулю равна полустепень исхода (то есть d-(v) = 0), то вершина, из которой дуги не исходят, называется стоком.
| Определение |
|---|
| Направленный орграф с одним источником и одним стоком называется сетью. |
Введем следующие операции над графами:
1. Дополнением графа G(V1, E1)
(обозначение — 
G1
(V1, E1)) называется граф
G2 (V2, E2),где
Дополнение содержит те же вершины и только те ребра, которых нет в исходном графе.
2. Объединением графов G1(V1,
E1) и G2 (V2, Е2)
(обозначение — G1(V1,
Е1)
G2(V2, Е2),
при условии V1 & V2 = ,
Е1 & Е2 = )
называется граф G(V,E), где
Объединение содержит все вершины и ребра исходных графов и состоит из нескольких компонент.
Пример
K3,3 = C3
C3.
3. Соединением графов G1(V1,
E1) и G2(V2, E2)
(обозначение – G1(V1, E1) +
G2(V2, Е2),
при условии V1 & V2 = ,
Е1 & Е2 = )
называется граф G(V, E), где
Соединение содержит все вершины и ребра исходных графов и все ребра, соединяющие каждую вершину одного графа с каждой вершиной другого.
Пример
Кm, n =
Km +
Кn.
4. Удаление вершины v из графа G1 (V1, E1) (обозначение — G1(V1, E1) - v, при условии v
V1) дает граф G2(V2, E2), где
Из графа удаляется вершина и все инцидентные ей ребра.
Пример
C3 - v = К2.
5. Удаление ребра е из графа G1(V1, E1) (обозначение — G1(V1, E1) - е, при условии e
Е1) дает граф G2(V2, E2), где
Пример
K2 - е =
K2
6. Добавление вершины v в граф G1(V1, E1) (обозначение — G1(V1, E1) + v, при условии v
V1) дает граф G2(V2, E2), где
Пример
G+v = G
K1
7. Добавление ребра е в граф G1(V1, E1) (обозначение — G1(V1, E1) + e, при условии е
E1) дает граф G2(V2, E2), где
8. Стягивание подграфа А графа G1(V1, E1) (обозначение — G1(V1, E1)/A, при условии А
V1) дает граф G2(V2, E2), где
Пример
K4/ C3 = K2.
9. Размножение вершины v графа G1(V1, E1) (обозначение — G1(V1, E1) 
v, при условии А
V1, v
V1, v'
V1) дает граф G2(V2, E2), где
Пример
К2 v = С3.
Граф, состоящий из одной вершины, называется
Граф, в котором каждая пара вершин смежна, называется
Направленный орграф с одним источником и одним стоком называется
Направленный орграф, полученный из полного графа, называется
Граф G(V,E), множество V которого разбито на два непересекающихся множества V1 и V2 , причем всякое ребро из Е инцидентно вершине из V1 и вершине из V2, называется
Граф, состоящий из простого цикла с k вершинами, обозначается
Полный граф с р вершинами обозначается
Полный двудольный граф обозначается
Удаление вершины v из графа G1(V1,E1) обозначается
Добавление вершины v в граф G1(V1,E1) обозначается
Добавление ребра е в граф G1(V1,E1) обозначается
Размножение вершины v графа G1(V1,E1) обозначается
Дополнением графа G(V1,E1) называется
Объединением графов G1(V1,E1) и G2(V2,Е2) называется
Соединением графов G1(V1,E1) и G2(V2,E2) называется
Размножение вершины v графа G1(V1, E1) дает
Удаление вершины v из графа G1 (V1, E1) дает