Некоторые понятия и определения теории графов

В главе 1 мы дали понятие графа. Рассмотрим еще некоторые понятия и определения теории графов.

Отметим, что многие понятия, рассматриваемые в данной главе, не являются устоявшимися, и могут в различной литературе определяться неодинаково.

Пусть v ₁, v ₂,…, v_n, v_{n +1} - произвольная последовательность вершин орграфа.

Цепью называется любая последовательность дуг e ₁, e ₂,..., e_n, такая, что концевыми вершинами дуги e_i являются вершины v_i и v_{i +1}, то есть e_i =(v_i, v_{i +1}) или e_i =(v_{i +1}, v_i) для i =1,2,…, n.

Цепь, для которой e_i =(v_i, v_{i +1}) при всех i =1,2,…, n, называется путём.

Циклом называется цепь, у которой начальная и конечная вершины совпадают.

Контуром называется путь, у которого начальная и конечная вершины совпадают.

Цепь, путь, цикл или контур называются простыми, если они не содержат внутри себя циклов.

У графа, изображенного на рис. 3.1

- дуги (v ₂, v ₁), (v ₂, v ₂), (v ₃, v ₂), (v ₃, v ₄) образуют цепь, соединяющую вершину v ₁ с вершиной v ₄;

- дуги (v ₂, v ₂), (v ₂, v ₄), (v ₄, v ₃) образуют путь, соединяющий вершины v ₂ и v ₃;

- дуги (v ₃, v ₂), (v ₂, v ₄), (v ₃, v ₄) образуют цикл с начальной и конечной вершиной v ₃;

- дуги (v ₃, v ₂), (v ₂, v ₄), (v ₄, v ₃) образуют контур с начальной и конечной вершиной v ₃;

- цепь (v ₂, v ₁), (v ₃, v ₂), (v ₃, v ₄), (v ₄, v ₃) с начальной вершиной v ₁ и конечной v ₃ не является простой, так как содержит внутри себя цикл (v ₃, v ₄), (v ₄, v ₃).

Граф называется связным, если в нем для каждой пары вершин найдётся соединяющая их цепь.

Связный и несвязный граф представлен на рис.3.2.

Любой граф можно рассматривать как некоторую совокупность связных графов. Каждый из этих графов называется компонентом исходного графа.

Несвязный граф, изображённый на рис. 3.2, имеет два компонента.

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

Для связного графа, изображенного на рис. 3.2, разрезом является выделенная дуга e, так как её удаление увеличивает число компонентов до двух.

Пусть G =(V, E), V ¢Í V, тогда граф, множество вершин которого совпадает с V ¢, а множество дуг включает все дуги множества E с концевыми вершинами в V ¢, называется подграфом графа G, порождённым V ¢.

Пусть E ¢Í E, тогда граф, для которого множество дуг совпадает с E ¢, а множество вершин включает вершины, инцидентные дугам из E ¢, называется подграфом графа G, порождённым E ¢.

Граф называется полным,если любые две его вершины смежные.

Граф G называется пустым, если в нём нет рёбер.

Граф, который не содержит циклов, называется ациклическим.

Связный неориентированный ациклический граф называется деревом, множество деревьев называется лесом.

Если рёбра, составляющие дерево, заменить ориентированными дугами, то получим ориентированное дерево. Если из контекста ясно, о каком дереве идет речь, то в дальнейшем слово «ориентированное» будем опускать.

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

Покрывающим (остовным) деревом графа G называется дерево, являющееся подграфом графа G и содержащее все его вершины.

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

Обобщением графа является гиперграф.

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

Подобные объекты в математике известны давно, однако введение термина “гиперграф” связано с успешным рассмотрением на них ряда важных понятий и методов теории графов.

Упражнения:

1.Определить число рёбер в полном графе порядка n. Нарисовать примеры полных графов порядка 2, 3, 4, 5.

2.Определить число рёбер в покрывающем дереве графа порядка n.