Двудольные (четные) графы

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

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

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

Рис. 3.18. Двудольный граф – сеть Петри

На рисунке 3.18 представлена сеть Петри, изображенная так, как это принято в теории сетей Петри, включающая 5 позиций и 4 перехода.

С точки зрения теории графов, приведенная сеть Петри это ориентированный двудольный мультиграф, т.к. допускает существование кратных дуг, в котором все множество вершин можно поделить на два подмножества: подмножество позиций и подмножество переходов . Каждая дуга направлена от элемента одного подмножества к элементу другого подмножества. На этих подмножествах определено отношение инцидентности .

Для двудольных графов справедлива следующая теорема: граф является двудольным, если все его циклы имеют четную длину.

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

Пример.

Проверить двудольность данных графов.

Рис. 3.19

Для решения задачи проще всего использовать вышеприведенную теорему о четной длине циклов двудольного графа. Граф 3.19а не является двудольным, так как имеет циклы нечетной длины. Граф 3.19b двудольный, так как все его циклы имеют четную длину. На рисунке 3.19c тот же граф представлен в традиционном для двудольных графов виде – с разделенными множествами вершин.

Планарность графов

Говорят, что граф укладывается на плоскости, т.е. является планарным или плоским, если его можно нарисовать так, что его ребра будут пересекаться лишь в концевых точках – вершинах. Изображение планарного графа на плоскости называется планарной укладкой. Определение планарности графов имеет большое практическое значение. Достаточно привести задачу разводки печатных плат, когда необходимо избежать пересечения проводников в местах, не предназначенных для соединений. Если изобразить места указанных соединений как вершины графа, то возникнет задача построения графа с непересекающимися ребрами. Важно отметить, что интерес представляет именно возможность построения графа с непересекающимися ребрами. Например, граф на рис. 3.20а изображен так, что его ребра пересекаются. Однако этот граф планарен, так как его легко перерисовать нужным образом (рис.3.20с).

На рис. 3.20 приведены примеры планарных графов, а на рис. 3.21 два основных непланарных графа, и , соответственно, которые обычно называют графами Куратовского.

Рис. 3.20. Планарные графы

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

Рис. 3.21. Непланарные графы (графы Куратовского)

Теорема. Граф планарен тогда и только тогда, когда он не содержит в качестве подграфа графа или .

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

Сети

Одним из частных случаев графовых представлений является сеть. Сеть можно представить как систему, транспортирующую некий продукт из одной точки в другую. Примером может служить система нефтепроводов, где нефть течет из одних точек к другим. Используя такую концепцию, сеть можно представить как ориентированный граф, дуги которого передают продукт от одной вершины к вершине. Обычно, на этот граф наложены естественные ограничения. В частности:

· граф не содержит петель, так как это противоречит задаче транспортировки продукта;

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

· граф должен быть связным.

Необходимыми элементами сети являются, по крайней мере, две вершины и , называемые обычно источником и стоком. Локальная степень вершины по входным дугам равна нулю, так что в источник ничто не втекает. Локальная степень вершины по выходным дугам равна нулю, так что из стока ничего не вытекает. Источники и стоки часто называют входными и выходными полюсами сети.

Определение. Сеть –это ориентированный граф , имеющий выделенные вершины – входные и выходные полюсы сети, такие, что локальные степени входных полюсов по входящим дугам и локальные степени выходных полюсов по выходящим дугам равны нулю.

Вершины, отличные от полюсов, называются внутренними вершинами сети. Ребро, инцидентное хотя бы одному полюсу, называется полюсным ребром.

Определение. –полюсником называется сеть с полюсами, разбитыми на два класса: входных и выходных полюсов.

Наибольший интерес представляют сети (1,1), называемые обычно двухполюсными сетями.

Будем называть цепью простую цепь между полюсами сети. Обозначим входной и выходной полюсы цепи символами и . Полюсные ребра образуют входную и выходную звезды, пересечение которых состоит из сквозных ребер (оно может быть пустым), инцидентных обоим полюсам.

Пример. На рис.3.21 приведена двухполюсная сеть, в которой входным полюсом (источником) является вершина , а выходным полюсом (стоком) – вершина . Направленные ребра и образуют входную звезду , ребра и образуют выходную звезду .