3.1.4. Примеры графов. Операции над графами

Рассмотрим некоторые важные типы графов.

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

Вполне несвязный граф обозначают Nn.

Заметим, что у вполне несвязного графа все вершины изолированы.

Определение. Простой граф, в котором любые две вершины смежны, называется полным. Полный граф обозначают Кn.

Пример 74.

Заметим, что для полного графа выполняется равенство , где m – число ребер, n – число вершин графа.

Определение. Граф, у которого все вершины имеют одну и ту же локальную степень n, называется регулярным (или однородным) степени n.

Регулярные графы степени 3 называются кубическими (или трехвалентными).

Пример 75.

Известным примером кубического графа является граф Петерсона (рис. 29).

Среди регулярных графов особенно интересны так называемые платоновы графы – графы, образованные вершинами и ребрами пяти правильных многогранников – Платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра.

Пример 76.

На рис. 30 приведен граф, соответствующий кубу.

Определение. Допустим, что множество вершин графа G можно разбить на два непересекающихся подмножества V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-нибудь вершиной из V2, тогда данный граф называется двудольным.

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

Определение. Если в двудольном графе каждая вершина из V1 соединена с каждой вершиной из V2, то граф называется полным двудольным.

Обозначение. Кm. n

Заметим, что граф Кm. n имеет ровно m + n вершин и mn ребер.

Пример 77.

На рис. 31 изображены двудольные графы.

Определение. Объединением графов называется граф

Определение. Пересечением графов , где , называется граф

Определение. Соединением графов G1 и G2 является новый граф, у которого V=V1ÈV2 , а множеством ребер являются все ребра первого и второго графа и ребра, соединяющие между собой каждую вершину первого графа с первой вершиной второго графа.

Определение. Граф называется связным, если его нельзя представить в виде объединения двух графов, и несвязным в противном случае.

Очевидно, что всякий несвязный граф можно представить в виде объединения конечного числа связных графов – каждый из таких связных графов называется компонентой связности графа.

Определение. Связный регулярный граф степени 2 называется циклическим графом. Обозначается Сn (рис. 32).

Определение. Соединение графов N1 и Cn-1 (n?3) называется колесом с n вершинами. Обозначается Wn (рис. 32).

Пример 78.

Определение. Дополнением простого графа G называется простой граф с множеством вершин V(G), в котором две вершины смежны тогда и только тогда, когда они не смежны в исходном графе.

Обозначение.

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

Определение. Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Подграф называется собственным, если он отличен от самого графа.

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 3.1.4. Примеры графов. Операции над графами:

  1. Тема 3. Операции над понятиями
  2. 1.4. Логические операции с понятиями. Операции над классами (объемами понятий)
  3. Операции над понятиями (классами)
  4. Булевы операции над вопросами
  5. Логические операции над вопросами
  6. 12.2. ОПЕРАЦИИ НАД СЛУЧАЙНЫМИ СОБЫТИЯМИ
  7. 1.5.Векторы. Основные операции над векторами.
  8. Линейные операции над векторами в координатах.
  9. Операции над множествами.
  10. Операции над событиями.
  11. §1. Высказывания и операции над ними
  12. §4. Алгебра предикатов. Логические операции над предикатами
  13. Операции над графами
  14. 1.2. Операции над множествами. Диаграммы Эйлера-Венна
  15. 1.6. Операции над бинарными отношениями