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

Теорема 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^\text{'})$, где $d(G^\text{'})$ — диаметр графа $G^\text{'}$, полученного из графа G заменой удаленного ребра цепью длинны 3;
# k=4, если удаляемое ребро инцидентно вершинам степени 2: $s(a)=s(b)=2.$

Теорема 3.28. Граф $T\_4(G)\; (T\_4^\text{'}(G))$ критический тогда и только тогда, когда является критическим граф G.

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

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

$k=d(G^\text{'})+1-s(a)$

где $a,\; b\; in\; H$ при $s(a)ge\; s(b)$,и граф $G^\text{'}$ получается из графа 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)$, ,
$Psi\_b=\; mathcal\{f\}\; V\_b,\; S\_2^\text{'}mathcal\{g\},\; V\_b=\; mathcal\{f\}\; a,\; b,...,\; m\; mathcal\{g\}$,

$S\_2^\text{'}=\; 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\_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)$, , $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^\text{'}=\; mathcal\{f\}\; b,c,f\; mathcal\{g\}$, $K\_2^\text{'}=\; mathcal\{f\}\; e\; mathcal\{g\}$, $K\_3^\text{'}=\; mathcal\{f\}\; a\; mathcal\{g\}$, $K\_4^\text{'}=\; 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^\text{'}$ также разбивается на два класса: $K\_1^\text{'}=\; mathcal\{f\}\; b,\; f\; mathcal\{g\}$ и $K\_5^\text{'}=\; mathcal\{f\}\; c\; mathcal\{g\}$. Если эти графы изоморфны, то $c=\; eta\; (1)$. Для установления соответствующих вершин графов $G\_a$, $G\_b$ строим таблицу (табл. 3.3) для полученного разбиения вершин.
Одинаковые столбцы указывают на то, что вершина 2 (вершина 6) может быть сопоставлена как вершине b, так и f. Получено два соответствия, $eta$ и $eta^\text{'}$, так как окрестности вершин 2 и 6 совпадают. Выбрав одно из них и проверив его на изоморфизм, делаем вывод, что рассматриваемые графы изоморфны (рис 3.36, в).

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

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

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