Определения

Срединный граф M(G) получается из графа G выполнением следующих операций:

• новая вершина вставляется в каждое ребро графа G;

• пары новых вершин соединяются ребрами в том случае, когда эти пары лежат на смежных ребрах графа.

Тотальный граф T(G) графа G строится следующим образом:

• вершины T(G) являются объединением множества вершин и ребер графа G;

• две вершины графа T(G) соединены ребром тогда и только тогда, когда соответствующие элементы графа G смежны или индидентны.

k-ой степенью G^k графа G=(V,E) является граф с тем же множеством вершин V(G) и ребром между двумя вершинами тогда и только тогда, когда между ними имеется путь длиной самое большее k.

2.3. Некоторые виды графов

2

Определения

.3.1. Регулярные графы

Граф будет r- регулярным (или регулярным степени r), если каждая его вершина имеет степень r.

Следствие леммы рукопожатий: не существует r-регулярный граф на п вершинах, если r u n оба нечётны. Справедливо следующее обратное утверждение: r регулярный граф на п вершинах существует тогда и только тогда, когда r или п чётны(или они четны оба).

Пример

r =4

n =12

Рис.2.3.1. Регулярные графы

2.3.2. Полные графы

Определения

Полным графом будет граф, каждая вершина которого соединена с другой вершиной точно одним ребром. Полный граф с m вершинами обозначается K_m. К_m является (m-1) – регулярным и имеет m(m-1) рёбер.

Пример

Рис.2.3.2. Примеры полных графов

2 .3.3. Двудольные графы

Двудольный граф – это граф, у которого вершины разделены на два подмножества А и В таким образом, что каждая дуга графа G соединяет одну вершину подмножества А и одну вершину подмножества В.

Заметим, что распределение вершин по подмножествам А и В для каждого двудольного графа может быть осуществлена несколькими способами.

Пример

Определения

Полным двудольным графом называется двудольный граф, у которого каждая вершина подмножества А соединена с каждой вершиной подмножества В только одним ребром. Полный двудольный граф с r и s вершинами имеет специальное обозначение K_rs .

При r=s завершенный двудольный граф называется сбалансированным.

Пример

Рис.2.3.4. Примеры полных двудольных графов (К_2,2 –сбалансированный двудольный граф)

2.3.4. Граф звезда

Определения

Граф звезда является деревом на (n+1) вершине, из которых одна является смежной n вершинам, а остальные вершины имеют степень 1. Граф звезда имеет специальное обозначение S_n.

Пример

Рис.2.3.5. Примеры графов звезда