Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6. Типы графов

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

Рис. 1,5. (а) Симметрический граф. (б) Антисимметрический граф. (в) Полный Симметрический граф. (г) Полный антисимметрический граф.

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

Граф называется симметрическим, если в множестве дуг А для любой дуги существует также противоположно ориентированная дуга

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

На рис. 1.5(a) показан симметрический граф, а на рис. 1.5 (б) - антисимметрический граф.

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

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

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

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

Доказательство. Необходимость. Поскольку X разбивается на две части то

Пусть существует цикл нечетной длины без потери общности, допустим, что Поскольку (согласно определению) одна из двух следующих друг за другом вершив этого цикла должна принадлежать а другая то имеем Следовательно, если к — нечетное, и если к — четное. Мы предположили, что длина цикла нечетная. Поэтому из соотношения следует, что Это противоречит (1.13), поскольку и вершина не может одновременно принадлежать как так и

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

Берем уже помеченную вершину и помечаем все вершины из множества знаком, противоположным тому, который присвоен вершине

Будем продолжать эту операцию до тех пор. пока или

(i) все вершины не будут помечены, а знаки, приписанные им, согласованы (иными словами, любые две вершины, соединенные ребром, помечены противоположными знаками), или

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

(iii) для каждой помеченной вершины все вершины из множества уже помечены, но существуют другие, еще не помеченные вершины.

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

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

Случай (iii) означает, что между помеченной и не помеченной вершинами не существует ребра, т. е. что граф распадается на две или больше частей, и каждая из них может тогда рассматриваться отдельно. Итак, в конце концов приходим к случаю (i) Теорема доказана.

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

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

Граф называется планарным, если он может быть нарисован на плоскости (или сфере) таким образом, что произвольные две дуги графа не пересекаются друг с другом. На рис. 1.6(a)

показан полный граф а на рис. полный двудольный граф которые, как известно, являются непланарными [1, 3].

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

Эти два графа играют важную роль в теории планарных графов и известны как графы Куратовского.

<< Предыдущий параграф Следующий параграф >>
Оглавление