Шаг 9.
Основные понятия теории графов.
Графы с атрибутами

    На этом шаге мы рассмотрим графы с атрибутами.

    Во многих случаях элементам (вершинам и ребрам) графа ставятся в соответствие различные данные - атрибуты (метки). Если в качестве атрибутов используются целые или вещественные числа, то такие графы называют взвешенными. Фактически, взвешенный граф - это функция, определенная на графе. В качестве атрибутов могут выступать и нечисловые данные, поэтому я буду называть графы с атрибутами помеченными, или атрибутированными (А-графами). Например, структурные формулы химических соединений представляются молекулярными графами - А-графами, вершины которых соответствуют атомам химической структуры, а ребра - валентным связям между атомами. Для вершин молекулярного графа определен, по крайней мере, атрибут "номер атома в периодической таблице элементов", для ребер - "тип валентной связи (одинарная, двойная, тройная и др.)"; могут использоваться дополнительные атрибуты, например, заряд атома.

    Для графов с атрибутами можно ввести усиленное определение изоморфизма: будем считать два А-графа изоморфными, если они изоморфны в обычном смысле, и, кроме того, изоморфное отображение сохраняет атрибуты (т.е. атрибуты соответствующих вершин и ребер в обоих графах совпадают).

Независимые множества и покрытия

    Независимое множество вершин (НМВ) - множество вершин графа, никакие две вершины которого не инцидентны.

    Максимальное независимое множество вершин (МНМВ) - НМВ, которое не содержится ни в каком другом НМВ.


    Замечание. В данном определении "максимальность" означает "нерасширяемость"; в общем случае граф может иметь несколько МНМВ различной мощности.

    Наибольшее независимое множество вершин - НМВ максимальной мощности.

    Мощность наибольшего НМВ (очевидно, это одно из МНМВ) называется вершинным числом независимости графа (а также неплотностью, числом внутренней устойчивости или числом вершинной упаковки графа); обозначение - a(G).

    Независимое множество ребер (НМР), или паросочетание - множество ребер графа, никакие два ребра которого не инцидентны.

    Мощность наибольшего паросочетания называется числом паросочетания графа; обозначение - n(G).

    Доминирующее множество вершин (ДМВ) - такое множество вершин графа, что каждая вершина графа либо принадлежит ДМВ, либо инцидентна некоторой вершине, принадлежащей ДМВ.

    Вершинное покрытие (ВП) - такое множество вершин графа, что каждое ребро графа инцидентно хотя бы одной вершине, принадлежащей ДМВ.

    Мощность наименьшего вершинного покрытия называется числом вершинного покрытия графа; обозначение - t(G).

    Доминирующее множество ребер (ДМР), или реберное покрытие - такое множество ребер связного графа, что каждая вершина графа инцидентна хотя бы одному ребру, входящему в ДМР.

    Мощность наименьшего ДМР называется числом реберного покрытия графа; обозначение - r(G).


Рис.1. Пример графа

    На рисунке обозначены реберное покрытии графа (пунктиром), МНМВ (белые вершины) и вершинное покрытие (черные вершины).

    Величины a(G), n(G), t(G) и r(G) являются инвариантами графа. Между этими инвариантами существует связь, устанавливаемая следующими леммами.

Лемма 1.
Множество S является наименьшим вершинным покрытием графа G=(V,E) тогда и только тогда, когда T=V(G)\S является наибольшим независимым множеством вершин графа.
Доказательство.
(=>)
  1. Докажем, что никакие две вершины, входящие в T, не инцидентны (т.е. T является НМВ). Допустим обратное: $(vi,vj)∈E(G), vi∈T, vj∈T. Но это означает, что ребро (vi,vj) не покрывается множеством S - противоречие с определением ВП.
  2. T является наибольшим НМВ в силу минимальности |S| и тождества |S| + |V(G)\S| = |V(G)|.
(<=)
  1. Докажем, что каждое ребро G инцидентно хотя бы одной вершине S (т.е. S является ВП). Допустим обратное: $(vi,vj)∈E(G), vi∉S, vj∉S. Но это значит, что vi∉T, vj∉T - противоречие с определением НМВ.
  2. Аналогично доказательству (=>).
Следствие 1 леммы 1.
Для любого графа G=(V,E) сумма числа вершинного покрытия и вершинного числа независимости постоянна и равна количеству вершин G: t(G)+a(G)=|V(G)|.
Лемма 2.
Если граф G=(V,E) не имеет изолированных вершин, то сумма его числа паросочетания и числа реберного покрытия постоянна и равна количеству вершин G: n(G)+r(G)=|V(G)|.
Доказательство.
  • Пусть C - наименьшее реберное покрытие G, содержащее r(G) ребер. Рассмотрим подграф GC графа G, образованный множеством ребер C и инцидентными вершинами G; по определению покрытия в него входят все вершины G. Поскольку C является наименьшим, GC состоит из одной или большего количества компонент, каждая из которых является деревом (действительно, в противном случае можно было бы "выбросить" из них кольцевые ребра и получить покрытие меньшей мощности). По теореме 2 количество ребер в каждой компоненте GSi графа GC на единицу меньше количества вершин: |E(GCi)| = |V(GCi)| - 1. Просуммировав эти равенства для всех i, получим: |E(GC)| = |V(GC)| - p, где p - количество компонент в , следовательно, p = |V(G)| - r(G). С другой стороны, если взять по одному ребру из каждой компоненты GC, получим некоторое паросочетание, следовательно, n(G) < p = |V(G)| - r(G) и n(G) + r(G) < |V(G)| (*).
  • Пусть M - наибольшее паросочетание G, содержащее n(G) ребер. Рассмотрим множество U вершин графа G, не покрытых М. Из определения паросочетания следует, что |U| = |V(G)| - 2*|M| = |V(G)| - 2*n(G). Множество U является независимым (действительно, если бы две произвольные вершины U "связывались" ребром, то можно было бы добавить это ребро M и получить паросочетание большей мощности). Поскольку G по условию не имеет изолированных вершин, для каждой вершины, входящей в U, существует ребро, покрывающее ее. Обозначим множество таких ребер через S. Множества M и S не пересекаются, поэтому |M ∪ S| = |M| + |S| = n(G) + |U| = |V(G)| - n(G). Объединение M и S является реберным покрытием графа по определению, следовательно, r(G) < |M ∪ S| = |V(G)| - n(G) и r(G) + n(G) < |V(G)| (**).
Из неравенств (*) и (**) следует результат леммы.

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

Теорема 1 (минимаксная теорема Кёнига).
Если граф G является двудольным, то t(G) = n(G) (без доказательства).
Определение.
Cовершенное паросочетание (l-фактор) - паросочетание, покрывающее все вершины графа.

    Пусть X - произвольное подмножество вершин графа G=(V,E). Обозначим через G(X) множество вершин G, инцидентных вершинам X.

Теорема 2 (теорема о свадьбах).
Если G - двудольный граф с долями P1 и P2, то G имеет совершенное паросочетание тогда и только тогда, когда |P1| = |P2| и, по крайней мере, одно из Pi (i=1..2) обладает тем свойством, что для любого X ⊆ Pi выполняется неравенство |X| < |G(X)| (без доказательства).

    Название теоремы связано со следующей "несерьезной" задачей: определить, возможно ли "переженить" группу юношей и девушек так, чтобы все остались довольны. Если допустить, что все "симпатии" взаимны (предположение, прямо скажем, нереалистичное), то задача сводится к нахождению совершенного паросочетания в двудольном графе, вершины одной из долей которого соответствуют юношам, другой - девушкам, и две вершины связаны ребром тогда и только тогда, когда юноша и девушка нравятся друг другу.

    На следующем шаге мы рассмотрим задачу нахождения кратчайших путей.




Предыдущий шаг Содержание Следующий шаг