Фундаментальные циклы, разрезы. Матрицы фундаментальных циклов, разрезов. (36)

 

Пусть G=<M,R> - неорграф, имеющий n вершин, m ребер и c компонент связности, Т – остов графа G, имеет υ^*(G)=n-c ветвей и υ(G)=m-n+c хорд. Если к лесу T добавить произвольную хорду υ_i, то в полученном графе найдется ровно один цикл C_i, который называется фундаментальным циклом графа G относительно хорды υ_i и остова T. Множество {C₁,..,C_m-n+c} называется фундаментальным множеством циклов. Мощность этого множества равна цикломатическому числу υ(G)=m-n+c.

Фундаментальное множество циклов можно задать с помощью матрицы фундаментальных циклов С=(a_ij), где . Т.к. каждый фундаментальный цикл содержит ровно одну хорду, то матрица С=(С₁|C₂), где С₁ – единичная матрица порядка υ(G).

Пусть G=<M,R> - неорграф, m={M₁,M₂} – разбиение множества М. Разрезом графа G по разбиению m называется множество всех ребер, соединяющих вершины из M₁ c вершинными из M₂. В связном графе любой разрез непуст.

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

Теорема: В связном неорграфе остовное дерево имеет по крайней мере одно общее ребро с любым из разрезов графа.

Теорема: В связном неорграфе любой цикл имеет любым разрезом четное число общих ребер.

 

Рассмотрим неорграф G с остовом Т. Пусть u₁,…,u_n-c – ветви остова Т. Удаляя из Т произвольную ветвь u_i получаем лес с (с+1) компонентой связности, т.е. каждое ребро u_i является разрезом остова Т по некоторому разбиению {М₁,М₂}. В графе G могут найтись еще ребра v_i1,…,v_ij (хорды Т), также являющиеся разрезами по {M₁,M₂}. Множество K_i={u_i,v_i1,…,v_ij} образует простой разрез, который называется фундаментальным разрезом графа G относительно ветви u_i остова Т. Множество {K₁,…,K_n-c} называется фундаментальным множество коциклов. Мощность этого множества равна корангу υ^*(G)=n-c. Фундаментальное множество коциклов можно задать матрицей K=(b_ij), где . Поскольку каждый фундаментальный разрез содержит одну ветвь, то матрица К=(K₁|K₂), где К₂ – единичная матрица порядка υ^*(G).

 

Раскраска графов. Планарные графы. (37)

 

Пусть G=<M,R> - неорграф без петель. Раскраской (вершин) графа G называют такое задание цветов вершинам G, что если [a,b] – ребро, то вершины a и b имеют различные цвета. Хроматическим числом χ(G) графа G называется минимальное число цветов, требующееся для раскраски графа G.

Раскраска ребер в мультиграфе G может быть определена с помощью раскраски вершин реберного мультиграфа L(G). Для произвольного неориентированного мультиграфа G=<M,U,P> реберным мультиграфом называется тройка L(G)=<U,M,P’>, где , и тогда и только тогда, когда в мультиграфе G вершина u является концом ребер u и v.

Неорграф G называется бихроматическим, если χ(G)=2. Неорграф G=<M,R> называется двудольным, если множество всех ребер графа G образует разрез графа G, т.е. для некоторого разбиения множества вершин {M₁,M₂} концы любого ребра принадлежат разным частям разбиения.

Теорема: Пусть G – неорграф без петель, имеющий хотя бы одно ребро. Тогда следующие условия эквивалентны:

1) G – бихроматический граф;

2) G – двудольный граф;

3) G не содержит циклов нечетной длины.

Следствие: Если G – лес, то χ(G)≤2.

 

Теорема: Для любого неорграфа без петель выполняется неравенство χ(G)≤deg(G)+1.

 

Алгоритм последовательной раскраски:

1) Произвольная вершина a₁ графа G принимает цвет 1.

2) Если вершины a₁,…,a_i раскрашены l цветами 1,2,…,l, l≤2, то новой произвольно взятой вершине a_i+1 припишем миимальный цвет, не использованный при раскраске вершин из множества {a_j|ρ(a_j,a_i+1)=1,j<i}.

 

Неорграф G называется планарным, если его можно изобразить на плоскости так, что никакие два ребра не будут иметь общих точек, кроме, может быть, общего конца этих ребер. Такое изображение графа называется плоским.

Рассмотрим операцию подразбиения ребра в графе G=<M,R>. После подразбиения ребра [a,b] из R получается граф G’=<M’,R’>, где , , т.е. ребро [a,b] заменяется на (a,b) -цепь длины два. Два графа называются гомеоморфными, если их можно получить из одного графа с помощью последовательности подразбиений ребер.

 

Критерий планарности (теорема Понтрягина-Куратовского): Граф G планарен тогда и только тогда, когда G не содержит подграфа, гомеоморфного K ₅ или K_3,3 (или подграфов, стягиваемых к K₅ или K_3,3, т.е. получаемых последовательным отождествлением связанных друг с другом вершин).

 

Теорема: Любой конечный граф может быть расположен в трехмерном пространстве без пересечения ребер.

Если G – планарный граф, то χ(G)≤4.

Толщина графа – минимальное количество плоскостей, в которых можно осуществить раскладку графа без пересечений.

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