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).