Типы графов

Разбить на страницы

Показывать лекцию целиком

Граф G = (X, A) называют полным, если для любой пары вершин х_i и х_j в X существует ребро (х_i, х_j) в неориентированном графе

G=(X,A)

т. е. для каждой пары вершин графа ,а).

Граф ,б).

(рис 5.1) а – полный граф; б – симметрический граф; в – антисимметрический граф; г – полный симметрический;

Антисимметрическим называется такой граф, для которого справедливо следующее условие: если $$дуга (х_{i}, х_{j}) \in A$$, то во множестве A нет противоположно ориентированной дуги, т. е. ( $$х_{j}, х_{i}) \notin A$$ (,в). Очевидно, что в антисимметрическом графе нет петель.

В качестве примера можно рассмотреть граф, являющийся моделью некоторой группы людей: вершины графа интерпретируют людей, а дуги – их взаимоотношения. Так, если в графе дуга, нарисованная от вершины х_i к вершине х_j, означает, что х_i является другом или родственником х_j, тогда данный граф должен быть симметрическим. Если дуга, направленная от х_i к х_j, означает, что вершина х_j подчинена вершине х_i, то такой граф должен быть антисимметрическим.

Комбинируя определения полного и симметрического графов и полного и антисимметрического графов, получили следующие определения:

граф ,г). Очевидно, что в полном симметрическом графе каждая вершина имеет петлю;

граф G =(X, A), имеющий для каждой пары вершин (х_i, х_j) только одну дугу, называется полным антисимметрическим или турниром.

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

(рис 5.2) Граф типа “дерево”: а – неориентированное дерево, б – ориентированное дерево

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

Граф ).

(рис 5.3) Планарный граф

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

(рис 5.4) Непланарные графы

Неориентированный граф G = (X, A) называют двудольным, если множество его вершин X может быть разбито на такие два подмножества X^а и X^b, что каждое ребро имеет один конец в X^а, а другой в X^b (,а).

Ориентированный граф ,б,в).

Двудольный граф $$G=(X^{а} \cup X^{b}, A)$$ называют полным, если для любых двух вершин $$х_{i} \in X^{а}$$ и $$х_{j}\in X^{b}$$ существует ребро ,г).

(рис 5.5) Двудольные графы: а, б, в – двудольные графы; г – полный двудольный граф

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

Теорема о двудольности

Граф G = (X, A) является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.

Доказательство

1. Необходимость. Поскольку множество X разбивается на две части X^а и X^b, то $$X^{а} \cup X^{b} = X$$ и $$X^{а} \cap X^{b} = \varnothing$$.

Пусть существует цикл нечетной длины х_i1, х_i2, ...,х_{i q}, х_i1. Без потери общности допустим, что $$х_{i1} \in X^{а}$$. Согласно определению одна из двух следующих друг за другом вершин этого цикла должна принадлежать множеству X^а, а другая – множеству X^b, тогда имеем: $$х_{i2} \in X^{b}, х_{i3} \in X^{а}$$ и т. д. Следовательно, $$х_{ik} \in X^{а}$$, если k – нечетное, и $$х_{ik} \in X^{b}$$, если k – четное.

Мы предположили, что длина цикла нечетная. Поэтому из соотношения $$х_{i q } \in X^{а}$$ следует, что $$х_{i1} \in X^{b}$$. Это противоречит исходному условию, поскольку $$X^{а} \cap X^{b} = \varnothing$$ и вершина не может принадлежать одновременно как X^a, так и X^b.

Для большей ясности можно рассмотреть цикл нечетной длины для графа, изображенного на :

(рис 5.6) Построение цикла

х₁---х₃--- х₅--- х₄--- х₂--- х₁

X^а X^b X^а X^b X^а X^b.

Поочередно помечая вершины, мы видим противоречие: вершина $$Х_{1} \in X^{а}$$ и согласно определению должна принадлежать X^b, следовательно, рассматриваемый граф не является двудольным.

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

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

Будем продолжать эту операцию до тех пор, пока не будет сделано следующее:

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

2) для каждой помеченной вершины х_i все вершины из множества Г⁺¹(х_i) помечены, но существуют другие, еще не помеченные вершины;

3) некоторая вершина, например х_ik, которая была уже помечена каким-то знаком ( "+" или "–" ), может быть помечена теперь (со стороны другой вершины) знаком, противоположным приписанному вершине х_ik.

В случае 1 все вершины , помеченные знаком "+", отнесем к множеству X^a, а помеченные знаком "–" – к множеству X^b. Поскольку все ребра соединяют вершины, помеченные противополож-ными знаками, то граф является двудольным.

Рассмотрим граф на б. Пометим знаком "+", например, вершину х₁. Найдем отображение Г⁺(х₁) = { х₄, х₅ }. Вершины х₄ и х₅ пометим знаком "–". Отображение Г⁺(х₄, х₅) = = { х₂, х₃ }, помечаем вершины х₂ и х₃ знаком "+". Г⁺(х₂, х₃) = = { х₄, х₅, х₆ }. Оставшуюся непомеченной вершину х₆ помечаем знаком "–". Таким образом, получили два подмножества вершин X^a = { х₁, х₂, х₃ } и X^b = { х₄, х₅, х₆ } и показали, что рассматриваемый граф является двудольным.

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

В графе на в, пометки были начаты знаком "+" с вершины х ₂. Г⁺(х₂) = { х₄ }. Вершина х₄ помечается знаком "–". Г⁺(х₄) = { х₃ }. Вершина х₃ помечается знаком "+". $$Г^{+}(х_{3}) = \varnothing$$.

В графе остались непомеченные вершины, но если перейти к неориентированному двойнику этого графа, то процедура пометок легко выполняется и множество вершин разбивается на два подмножества Х^a= { х₁, х₂, х₃ } и Х^b= { х₄, х₅, х₆ }, тем самым исходный граф является двудольным.

В случае 3 вершина х_ik должна быть помечена знаком "+" на некотором маршруте (например, М₁), состоящем из вершин х_i1, х_i2, ..., х_ik ; причем знаки маршрут М₁ можно выбрать таким:

М₁: х₁ -> х₃ -> х₅ -> х₄ -> х₂.

"+" "-" "+" "-" "+"

Аналогично знаком "-" вершина х_ik помечается вдоль некоторого маршрута М₂. Например,

М₂: х₁ -> х₄ -> х₆ -> х₂.

"+" "-" "+" "-"

Пусть x^* – предпоследняя (последней является х_ik ) общая вершина маршрутов М₁ и М₂. Если вершина x^* помечена знаком "+", то участок от x^* до х_ik маршрута М₁ должен быть четным, а участок от x^* до х_ik маршрута М₂ должен быть нечетным. Если же вер-шина x^* помечена знаком "-", то участок маршрута М₁ будет нечетным, а маршрута М₂ – четным. Следовательно, цикл, состоящий из участка маршрута М₁, от x^* до х_ik, и соответствующего участка маршрута М₂, от х_ik до x^*, имеет нечетную длину. Это противоречит предположению, что граф не содержит циклов нечетной длины, и, значит, случай 3 невозможен.

В рассматриваемом примере x^* = х₄. В маршруте М₁ длина участка от х₄ до х₂ равна 1, а в маршруте М₂ длина участка от х₄ до х₂ равна 2, что в сумме составляет нечетное число, следовательно, граф содержит цикл нечетной длины и не является двудольным.

Страницы:

G=(X,A)

т. е. для каждой пары вершин графа ,а).

Граф ,б).

(рис 5.1) а – полный граф; б – симметрический граф; в – антисимметрический граф; г – полный симметрический;

граф ,г). Очевидно, что в полном симметрическом графе каждая вершина имеет петлю;

(рис 5.2) Граф типа “дерево”: а – неориентированное дерево, б – ориентированное дерево

Граф ).

(рис 5.3) Планарный граф

(рис 5.4) Непланарные графы

Ориентированный граф ,б,в).

(рис 5.5) Двудольные графы: а, б, в – двудольные графы; г – полный двудольный граф

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

Теорема о двудольности

Граф G = (X, A) является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.

Доказательство

Для большей ясности можно рассмотреть цикл нечетной длины для графа, изображенного на :

(рис 5.6) Построение цикла

х₁---х₃--- х₅--- х₄--- х₂--- х₁

X^а X^b X^а X^b X^а X^b.

Будем продолжать эту операцию до тех пор, пока не будет сделано следующее:

М₁: х₁ -> х₃ -> х₅ -> х₄ -> х₂.

"+" "-" "+" "-" "+"

Аналогично знаком "-" вершина х_ik помечается вдоль некоторого маршрута М₂. Например,

М₂: х₁ -> х₄ -> х₆ -> х₂.

"+" "-" "+" "-"

Занятие пройдено

Предыдущее занятие Занятие пройдено Следующее занятие

Вернуться к учебному плану

Теорема о двудольности

Теорема о двудольности

Купить дополнительную попытку

Вы действительно хотите купить ещё одну попытку для прохождения тестирования?

Успешно!

Напишите нам, если у вас есть вопросы

Уважаемые пользователи ИНТУИТ!

Уважаемые пользователи ИНТУИТ!

Добро пожаловать на обновлённый сайт НОУ «ИНТУИТ»!