Теорема
Ребро а графа Gявляется мостом тогда и только тогда, когда а не принадлежит ни к одному циклу графа.
Примеры
a
Рис.2.6.3.
Ребро разрезаe Рис.2.6.4.
Разрывающее множество реберa,b,c
Класс сложности
Нахождение числа реберной связности λ(G) относится к классуNP-тяжелых.
2.6.2. Вершинная связность
Определения
Граф Gназываетсяk-вершинносвязным, если κ(G) k.
В графе может существовать вершина, удаление которой вместе с инцидентными ей ребрами разъединяет оставшиеся вершины. Такая вершина называется точкой сочленения илиразделяющей точкой.
Граф, содержащий точку разделения, будет разделимым.Граф без точек сочленения называетсядвусвязным илинеразделимым.
Максимальный двусвязный подграф графа является двусвязной копонентойилиблоком.
Пример
Класс сложности
Нахождение числа вершинной связности κ(G) относится к классуNP-тяжелых.
Вершинно-реберная связность
Определение
Вершинно-реберным разделяющим множеством связного графаGназывается множество вершин и ребер (содержащее хотя бы одну вершину и одно ребро) графаG, при удалении которых получается либо несвязный граф, либо одновершинный граф.
Меры
κγ(G) –число вершинно-реберной связности, равное наименьшему числу элементов вершинно-реберного разделяющего множества.
Класс сложности
Нахождение числа вершинно-реберной связности κγ(G) относится к классуNP-тяжелых.
Следствие 2
Теорема Следствие 1
Для любого связного графа Gλ(G)>1 κ(G) κλ(G) λ(G).
Для любого связного графа G, если λ(G)=1, то κλ(G) либо не определено, либо κλ(G)> λ(G).
Для полного графа Kn(n 3) λ(Kn)= κ(Kn)= κλ(Kn)=n-1 .
Следствие 3
Для цикла Cn(n 3) λ(Cn)= κ(Cn)= κλ(Cn)=2
2.7. Деревья. Каркасные деревья.
Множество фундаментальных циклов
Определения
Граф Gназываетсядеревом, если он связан и не содержит циклов.
Существует несколько эквивалентных определений дерева.
Теорема
Пусть G(V,E) будет деревом с |V| =n. Тогда следующие определения эквивалентны:
Gявляется деревом, если он связан и не содержит циклов.
Gявляется деревом, если он не содержит циклов и имеетn-1 ребер.
Gявляется деревом, если он связан и раждое ребро является ребром разреза (мостом).
Gявляется деревом, если две любые вершиныGсоединены между собой точно одним путем.
Gявляется деревом, если граф не имеет циклов, но добавление одного ребра создает ровно один цикл.
Примеры
Рис.2.7.1.
Деревья
Определения
Вершины дерева степени 1 являются его листьями.
Граф без циклов будет лесом.Лес состоит из деревьев.
Иногда удобно рассматривать одну из вершин как специальную вершину. Такая вершина называется корнемдерева. Дерево с такой вершиной являетсякорневым деревом.
Определения
Пусть G= (V,E) будет простым графом.Каркасное дерево дляGбудет деревомT=(V,E1) с множеством вершинVи множеством реберE1E.
Примеры
Теоремы
Теорема 1
Каждый связной граф имеет по меньшей мере одно каркасное дерево.
Теорема
Кирхгоффа (Matrix-Tree Theorem)
Пусть G=(V,E),n=|V(G)|,V(G)= {v1,…,vn}, будет простым графом.Матрица Лапласа размераn nопределяется следующим образом:
где deg(vi) – степень вершиныvi.
Редуцированной матрицей ЛапласаLi,j(G) будет матрица размера (n-1)= (n-1) будет матрица, полученная из матрицы Лапласа удалениемi-ой строки иj-го столбца.
Тогда число каркасных деревьев графа G=(V,E) равно
(-1)i+j detLi,j(G),
где detLi,j(G) – детерминант редуцированной матрицы ЛапласаLi,j(G).
Редуцированная матрица Лапласа получается из матрицы Лапласа вычеркиванием 6-го столбца и 6-ой строки (для уменьшения числа вычислений берутся столбец и строка с наибольшим числом ненулевых элементов).
