Рис. 1.4. (а) Граф. (б) Остовный подграф, (в) Порожденный подграф, (г) Подграф.

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

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

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

Граф G = (Z, А) называют полным, если для любой пары вершин Xi ш Xj в X существует ребро (х,-, x) в G = {X, А), т. е. для каждой пары вершин графа G должна существовать по край-

В оригинале используется термин частичный подграф .- Прим. ред,.

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

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

Граф {X, А) называется симметрическим, если в множестве дуг А для любой дуги (Xj, Xf) существует также противоположно ориентированная дуга (х), а:,).

Антисимметрическим графом ) называется такой граф, для которого справедливо следующее условие: если (г,-, Xj) 6 Л. то в множестве А нет противоположно ориентированной дуги, т. е. {xj, Xt) $ Л. Очевидно, что в антисимметрическом графе нет петель.

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

Рассмотрим следующий пример: множество вершин графа представляет группу людей, дуга, направленная от вершины Xt к вершине X), означает, что Xi является другом или родственником х^; тогда данный граф должен быть симметрическим. С другой стороны, если дуга, направленная от Xj к Xj, означает, что вершина Xf подчинена вершине xi, то такой граф должен быть антисимметрическим.

) Применяется также термин чнаправленнай граф .- Прим. ред.

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

Неориентированный граф G = (X, А) называют двудольным, если множество его вершин X может быть разбито на такие два подмножества Z и Х*, что каждое ребро имеет один конец в а другой в Х*. Ориентированный граф G называется двудольным, если его неориентированный двойник G - двудольный граф. Легко доказать следующее утверждение.

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

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

Х'[]Х>> = Х ш Х'[\Х'=0. (1.13)

Пусть существует цикл нечетной длины Xi, Xi, . . ., Xi , Xt, и, без потери общности, допустим, что Хц g Поскольку (согласно определению) одна из двух следующих друг за другом вершив этого цикла должна принадлежать а другая Х*, то имеем Xi 6 Х*, Xi 6 X и т. д. Следовательно, Xf 6 X , если к - нечетное, и Xjjj g Х*, если к - четное. Мы предположили, что длина цикла нечетная. Поэтому из соотношения х,- 6 Х следует, что xt € X. Это противоречит (1.13), поскольку X (] Х' = 0 и вершина не может одновременно принадлежать как Х , так и X

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

Берем уже помеченную вершину и помечаем все вершины из множества Г (х^) знаком, противоположным тому, который присвоен вершине Xj.

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

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

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