Двудольные графы

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

Теорема Кёнига. Граф является двудольным тогда и только тогда, когда в нем нет циклов нечетной длины.

Планарные графы

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

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

Теорема о числе граней (формула Эйлера). Количество граней в любой плоской укладке планарного графа, имеющего n вершин, m ребер и k компонент связности, равно .

Следствие 1. Если в планарном графе n вершин, , и m ребер, то .

Следствие 2. Если в планарном графе n вершин, , m ребер и нет циклов длины 3, то .

Следствие 3. В любом планарном графе имеется вершина степени не более 5.

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

Теорема Понтрягина–Куратовского). Граф планарен тогда и только тогда, когда у него нет подграфа, являющегося подразбиением графа или графа .

Операция стягивания ребраопределяется следующим образом. Вершины a и b удаляются из графа, к нему добавляется новая вершина c и она соединяется ребром с каждой вершиной, с которой была смежна хотя бы одна из вершин . Граф G называется стягиваемым к графу H, если H можно получить из G последовательностью операций стягивания ребер.

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

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

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

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

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

Рис. 5.

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