Теория графов и мографов

Теория графов и мографов

Теорема 3.27. замена любого ребра (a, b)in Gкритического графа G на k вершинно непересекающихся простых цепей длинны 3 тогда и только тогда приводят к образованию критического графа T_3(G), когда k удовлетворяет одному из следующих условий:
# k=1, если удаляемое ребро является общим ребром двух циклов длинны 4;
# k=2, если s(a)=3, s(b)=2 и вершины a, b принадлежат циклу длинны 4;
# k=m+2-s(a), если s(a)>s(b) и m=d(G^'), где d(G^') — диаметр графа G^', полученного из графа G заменой удаленного ребра цепью длинны 3;
# k=4, если удаляемое ребро инцидентно вершинам степени 2: s(a)=s(b)=2.

Теорема 3.28. Граф T_4(G) (T_4^'(G)) критический тогда и только тогда, когда является критическим граф G.

Теорема 3.29. Граф T_5(g) критический тогда и только тогда, когда граф G критический.

Теорема 3.30. Если G — критический граф, то граф T_6(G) критический тогда и только тогда, когда подграф H содержит точку сочленения, и число добавляемых цепей определяется из условия

k=d(G^')+1-s(a)

где a, b in H при s(a)ge s(b),и граф G^' получается из графа G заменой цепи длинны 2 между вершинами a, b на цепь длинны 4.

Множество запрещенных графов вложения в n-куб является счетным.

При порождении запрещенных фигур необходимо проверить полученные графы на изоморфизм.Рассмотрим алгоритм установления изоморфизма между графами G_a, G_b, основанный на частотном разложении моделей Psi_a(G_a), Psi_b(G_b), построенных по этим графам.
# С помощью алгоритма, приведенного выше, выделяем полные подграфы в графах G_a, G_b. Выделенные подграфы образуют слова в соответствующих моделях Psi_a(G_a), Psi_b(G_b).
# Находим частотные разложения моделей Psi_a(G_a), Psi_b(G_b). Определяем равенство коэффициентов в разложениях. Если частотные разложения равны, то графы G_a, G_b изоморфны.Из равенства разложений тривиально определяем изоморфизм. Если частотные разложения не равны, то графы G_a и G_b изоморфны.Проиллюстрируем алгоритм на примере установления изоморфизма между графами G_a и G_b (рис. 3.35).Пункт 1 алгоритма выполняется тривиально, так как графы двудольные (полными подграфами являются ребра). Отсюда следует что моделиPsi_a и Psi_b соответственно совпадают с графами G_a и G_b:

Psi_a=(V_a, S_2), V_a=mathcal{f}alpha,eta,...,ximathcal{g},
S_2= mathcal{f} mathcal{f} alpha, eta mathcal{g},mathcal{f} alpha, delta mathcal{g}, mathcal{f} alpha, xi mathcal{g}, mathcal{f} eta, varepsilon mathcal{g}, mathcal{f} gamma, mu mathcal{g}, mathcal{f} gamma, xi mathcal{g}, mathcal{f} mu, varepsilon mathcal{g}, mathcal{f} varepsilon, delta mathcal{g}, mathcal{f} varepsilon, u mathcal{g},mathcal{f} u, eta mathcal{g}, mathcal{f} eta, xi mathcal{g} mathcal{g};
Psi_b= mathcal{f} V_b, S_2^'mathcal{g}, V_b= mathcal{f} a, b,..., m mathcal{g},

S_2^'= mathcal{f} mathcal{f} a, b mathcal{g},mathcal{f} a, c mathcal{g}, mathcal{f} a, d mathcal{g}, mathcal{f} a, e mathcal{g}, mathcal{f} b, f mathcal{g}, mathcal{f} c, g mathcal{g}, mathcal{f} d, g mathcal{g}, mathcal{f} e, k mathcal{g}, mathcal{f} f, m mathcal{g},mathcal{f} g, m mathcal{g}, mathcal{f} k, m mathcal{g} mathcal{g};
Частотные разложения моделей Psi_a и Psi_b имеют следующий вид: F ( Psi_a)=3 alpha^2 circ 2 eta^2 circ 2 gamma^2 circ 2 mu^2 circ 4 varepsilon^2 circ 2 delta^2 circ 2 u^2 circ 2 eta^2 circ 3 xi^2 circ alpha eta circ alpha delta circ alpha xi circ eta varepsilon circ gamma mu circ gamma xi circ mu varepsilon circ varepsilon delta circ varepsilon u circ u eta circ eta xi ,

F ( Psi_b)=4a^2 circ 2b^2 circ 2c^2 circ 2d^2 circ 2e^2 circ 2f^2 circ 3g^2 circ 2k^2 circ 3m^2 circ ab circ ac circ ad circ ae circ bf circ cg circ dg circ ek circ fm circ gm circ km .


Частотные разложения равны: F ( Psi_а)=F ( Psi_b). Графы G_a и G_b изоморфны. Для определения изоморфизма устанавливаем взаимно однозначное соответствие между буквами с одинаковыми спектрами частот: varepsilon longleftrightarrow alpha , mu longleftrightarrow b(e) , eta longleftrightarrow c(d) , u longleftrightarrow e(b) , delta longleftrightarrow d(c) , gamma longleftrightarrow f(k) , alpha longleftrightarrow g , eta longleftrightarrow k(b) , xi longleftrightarrow m .

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

Другой алкоритм определения изоморфизма графов заключается в последовательном разбиении классов вершин графа, каждый из которых состоит из вершин, имеющих равные степени, на основе подсчета количества ребер, связывающих рассматриваемую вершину с вершинами этих классов.
Рассмотрим два графа, G_a и G_b (рис. 3.36, а, б). Носитель графа G_a по значению степеней вершин разбивается на четыре класса: K_1= mathcal{f} 1,2,6 mathcal{g}, K_2= mathcal{f} 4 mathcal{g}, K_3= mathcal{f} 3 mathcal{g}, K_4= mathcal{f} 5 mathcal{g}. Носитель графа G_b также разбивается на четыре класса: K_1^'= mathcal{f} b,c,f mathcal{g}, K_2^'= mathcal{f} e mathcal{g}, K_3^'= mathcal{f} a mathcal{g}, K_4^'= mathcal{f} d mathcal{g}. Количество классов и их мощности совпадают: следовательно, графы G_a и G_b могут быть изоморфны, при этом изоморфизм eta отображает, очевидно, вершины 3, 4, 5, в a, e, d соответственно: a= eta (3), e= eta (4), d= eta (5).
Определим количество связей вершин 1, 2, 6 в графе G_a и вершине b, c, f в графе G_b с вершинами выделенных классов. для этого построим двумерную таблицу (табл. 3.2), каждой строке которой взаимно однозначно соответствует выделенный класс, столбцу - вершина, а на пересечении (i, j) указывается количество связей j-й вершины с вершинами i-го класса.

Анализируя таблицу замечаем, что класс K_1 разбивается на два класса: K_1= mathcal{f} 2, 6 mathcal{g} и K_5= mathcal{f} 1 mathcal{g}; класс K_1^' также разбивается на два класса: K_1^'= mathcal{f} b, f mathcal{g} и K_5^'= mathcal{f} c mathcal{g} . Если эти графы изоморфны, то c= eta (1). Для установления соответствующих вершин графов G_a, G_b строим таблицу (табл. 3.3) для полученного разбиения вершин.
Одинаковые столбцы указывают на то, что вершина 2 (вершина 6) может быть сопоставлена как вершине b, так и f. Получено два соответствия, eta и eta^' , так как окрестности вершин 2 и 6 совпадают. Выбрав одно из них и проверив его на изоморфизм, делаем вывод, что рассматриваемые графы изоморфны (рис 3.36, в).

§ 3.7 Раскраска вершин и ребер графа.Характеризация реберности


Раскраской вершин графа G= в k цветов (или k-раскраской) называется разбиение носителя V графа G, при котором каждое подмножество

V_i igg( igcup_{i=1}^k V_i=V, V_ia cap V_ib=oslash, i_a, i_b = 1,2,...,k igg)

не содержит ни одной пары смежных вершин. Каждому подмножеству сопоставляется цвет, в который окраширают все элементы этого подмножества. Вершины, окрашенны в один цвет, будем называть соцветными.
Хроматическим числом h(G) графа G называется минимальное число n, для которого граф имеет n-раскраску.

Wikimedia Foundation. 2010.


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»