Тема 7.4 Двудольные и изоморфные графы.

Графы, которые отличаются только нумерацией вершин, называются изоморфными.

У изоморфных графов матрицы совпадают при применении к ним элементарных алгебраических операций.

На графах изоморфизм возможно представить как функцию: пусть G1(V1 E1 ) и G2(V2 E2) изоморфные графы, тогда существует функция Н-биекция, сохраняющая смежность

H: V1®V2 и e1=(vi vj)ÎE1? e2=(h(vi ) h(vj))ÎE2

e2=(vi vj)ÎE2? e1=(h-1 (vi ) h-1(vj))ÎE1

Теорема: изоморфизм графов есть отношение эквивалентности.

Доказательство: 1. рефлексивность- h тождественная функция

2. симметричность- т.к. h: V1®V2-биекция, то h-1 :V2®V1 тоже биекция

3. транзитивность- h: G1®G2 & f: G2®G3?h°f: G1®G3

Числовая характеристика, сохраняющаяся при изоморфизме, называется инвариат.

У изоморфных графов все инварианты совпадают, но это не является признаком изоморфизма графов, т.е. при совпадении всех инвариантов мы не можем утверждать об изоморфности данных графов.

Для определения изоморфизма между орграфами G и Gможно предложить следующий алгоритм.

Шаг 1. Если число вершин и число дуг, соответственно, совпадают для орграфов, то переходим к шагу 2. Иначе орграфы не изоморфны.

Шаг 2. Для каждой вершины орграфов определяем пары чисел, равные полустепеням захода и исхода. Если каждой такой паре орграфа G найдется аналогичная пара орграфа G, то переходим к шагу 3. Иначе орграфы не изоморфны.

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

Если некоторой паре орграфа G соответствует не одна аналогичная пара орграфа G, то этой вершине орграфа G ставим в соответствие поочередно вершины орграфа G с аналогичной парой чисел.

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

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

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

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

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

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

Паросочетание называется совершенным (из множества v в множество w), если число ребер в нем совпадает с числом вершин в подмножестве c.

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

Теорема Холла. Для того, чтобы в двудольном графе существовало совершенное паросочетание, необходимо и достаточно, чтобы для любого подмножества S из множества V выполнялось условие [S]