Глава 2.Ненаправленные графы, часть 1. Простые графы (графы) Способы задания графа Основные способы задания графов графический

• Название: Простые графы (графы) Способы задания графа Основные способы задания графов графический
• Анкор: Глава 2.Ненаправленные графы, часть 1.doc
• Дата: 04.09.2018
• Размер: 1.28 Mb.
• Имя файла: Глава 2.Ненаправленные графы, часть 1.doc
• Тип: Глава; #24055
• страница: 5 из 14

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

2

Определения

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




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

Следствие леммы рукопожатий: не существует r-регулярный граф на п вершинах, если run оба нечётны. Справедливо следующее обратное утверждение: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 –сбалансированный двудольный граф)