4. Деревья
Деревья являются наиболее простейшим и распространенным классом графов. Деревья были введены Г. Кирхгофом, который применил их к анализу электрических цепей.
Деревом называется конечный связный граф без циклов, имеющий не менее двух вершин. Любая фиксированная вершина дерева называется корнем. Любой граф без циклов называется ациклическим или лесом. Таким образом, компонентами леса являются деревья. На рисунке 4.1.1 изображены все различные деревья с шестью вершинами.
Следующие определения дерева равносильны и содержат их наиболее характерные свойства.
Теорема 4.1.1. Пусть граф с вершинами. Следующие характеристические свойства деревьев равносильны:
1) связен и не содержит циклов.
2) Любые две вершины соединены единственной простой цепью.
3) связен, но утрачивает это свойство после удаления любого ребра.
4) связен и имеет ребер.
5) не содержит циклов и имеет ребер.
6) не содержит циклов, но добавление ребра, соединяющего любые две несмежные вершины, приводит к появлению ровно одного простого цикла.
Доказательство. Схема доказательства:
От противного. Пусть существуют две цепи (рис. 3.1.2). Тогда – простой цикл. Противоречие.
Для любых двух вершин существует единственная простая цепь, следовательно, граф связен. Предположим, что некоторое ребро не является мостом. Тогда в графе концы и этого ребра связаны некоторой цепью. Само ребро – вторая цепь. Противоречие.
Индукция по числу вершин . При . Пусть для всех графов с числом вершин меньше . Тогда удалим из графа ребро , которое является мостом. Так как удаленное ребро является мостом, то получим две компоненты связности и . По индукционному предположению
От противного. Пусть имеется цикл с вершинами, ребрами. Остальные вершин имеют инцидентные им ребра, которые связывают их с циклом. Следовательно, , что противоречит условию .
Граф без циклов, следовательно, его компоненты – деревья. Пусть их . Имеем:
По ранее доказанному . Для любых двух вершин и существует единственная простая цепь . Соединяя две несмежные вершины этой цепи, получаем единственный простой цикл.
От противного. Пусть граф не является связным и вершины принадлежат разным компонентам связности графа. Тогда добавление к графу ребра не приводит к образованию цикла. Противоречие.
Следствие 4.1.1. Любое дерево имеет по крайней мере две висячие (концевые) вершины.
Доказательство. Пусть – степенная последовательность дерева. Тогда по лемме о рукопожатиях имеем: и все . Следовательно, хотя бы два числа из степенной последовательности равны .
Источник
1. Деревья. Характеризация дерева.
Деревом называется связный граф, не содержащий циклов. Любой граф без циклов называется ациклическим (или лесом). Таким образом, компонентами леса являются деревья. Существует несколько вариантов определения дерева; некоторые из них отражены в следующей теореме.
Теорема 10.1. Для (n, m)--графа G следующие утверждения эквивалентны:
1) G — дерево;
2) G — связный граф и m = n – 1;
3) G — ациклический граф и m = n – 1;
4) любые две несовпадающие вершины графа G соединяет единственная простая цепь;
5) G — ациклический граф, обладающий тем свойством, что если, какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.
1) 2) Воспользуемся индукцией по n. При n = 1 утверждение тривиально. Пусть n > 1, e EG. В дереве G нет циклов, следовательно, согласно утверждению 4.5, граф G – e имеет ровно две компоненты T1 и T2, каждая из которых есть дерево. Пусть дерево Ti является (ni, mi)-графом, i = 1, 2. По индуктивному предположению верно равенство
mi = ni – 1 (1)
Далее имеем m = m1 + m2 + 1 = (n1 – 1) + (n2 – 1) + 1 = (n1 + n2 ) – 1 = n – 1.
2) 3) Граф G связен и m = n – 1. Нужно доказать, что в G нет циклов. Пусть, напротив, в графе G есть цикл и пусть e — ребро этого цикла. Тогда граф G – e связен (по утверждению 4.5) и имеет n – 2 ребра, что противоречит теореме 4.6. Следовательно, G — ациклический граф.
3) 4) Пусть k — число компонент графа G. Пусть, далее, компонента Ti является (ni, mi)-графом. Так как Ti — дерево, то верно равенство (1). Теперь имеем n – 1 = m = m1 + m2 +…+ mk = (n1 – 1) + (n2 – 1) +…+ (nk – 1) = (n1 + n2 + …+ nk) – k = n – k, т. е. k = 1. Итак, G — связный граф и потому любые несовпадающие вершины и соединены в нем простой цепью. Если бы в G были две несовпадающие простые (u, v)-цепи, то согласно утверждению 4.1в их объединение содержало бы цикл. Следовательно, каждые две вершины соединены единственной простой цепью.
4) 5) Пара несовпадающих вершин, принадлежащих одному циклу, соединена по меньшей мере двумя простыми цепями. Следовательно, граф G ациклический. Пусть u и v — две его несмежные вершины. Присоединим к графу G ребро e = uv. В G есть простая (u, v)-цепь, которая в G + e дополняется до цикла. В силу утверждения 4.1г этот цикл единственный (иначе в G после выбрасывания e из G + e оставался бы цикл).
5) 1) Нужно доказать, что граф G связен. Если бы вершины u и v принадлежали разным компонентам графа G, то граф G + uv не имел бы циклов, что противоречит утверждению 5 теоремы. Итак, G связен и потому является деревом.
Следствие 10.2. В любом дереве порядка n 2 имеется не менее двух концевых вершин.
Пусть d1, d2, …, dn — степенная последовательность дерева. Тогда d1 + d2 +…+ dn = 2n – 2 (лемма о рукопожатиях) и все di > 0. Следовательно, хотя бы два числа из последовательности степеней вершин равны 1.
Теорема 10.3. Центр любого дерева состоит из одной или из двух смежных вершин.
Доказательство проведем индукцией по числу вершин дерева. Очевидно, что концевые вершины дерева T являются центральными только для T = K1 или T = K2. Пусть T — дерево порядка n > 2. Удалив из T все концевые вершины, получим дерево T’, в котором по предположению индукции центр состоит из одной или из двух смежных вершин. Заметим, что для любой вершины дерева ее эксцентриситет всегда равен расстоянию до некоторой висячей вершины. Тогда эксцентриситет каждой вершины в T’ на единицу меньше ее эксцентриситета в дереве T. Следовательно, центры деревьев T и T’ совпадают.
Пусть H — остовный подграф произвольного графа G. Если в каждой компоненте связности графа G графом H порождается дерево, то H называется остовом (или каркасом) графа G. Очевидно, что в каждом графе существует остов: разрушая в каждой компоненте циклы, т. е. удаляя лишние ребра, придем к остову. Остов в графе легко найти с помощью поиска в ширину.
Следствие 10.4. Число ребер произвольного (n, m)- графа G, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно , где — число компонент связности графа G.
Если (n1, m1)-граф H является одной из компонент графа G, то для превращения ее в остовное дерево нужно удалить m1 – (n1 – 1) подходящих ребер. Суммируя по всем k компонентам, получим требуемое.
Число (G) = m – n + k называется цикломатическим числом графа G. Очевидно следствие
Следствие 10.5. а) граф является лесом тогда и только тогда, когда (G) = 0; б) граф G имеет единственный цикл тогда и только тогда, когда (G) = 1; с) граф, в котором число ребер не меньше, чем число вершин, m n, содержит цикл.
Очевидно, что число остовов в Kn равно числу помеченных деревьев порядка n. В 1897 г. А. Кэли показал, что число помеченных деревьев порядка n равно n n –2 .
Источник
Деревья, их свойства. Характеристические числа графов. Сети
Дерево – это связный ациклический граф.
Граф G является деревом тогда и только тогда, когда любые 2 его вершины связаны единственной простой цепью.
Граф G является деревом с n вершинами тогда и только тогда, когда у него ровно n-1 ребро.
Лес из k деревьев – это несвязный ациклический граф, содержащий ровно k компонент связности.
Лес с n вершинами, состоящий из k деревьев, содержит ровно n—k ребер.
Остов графа G – это подграф графа G, который является деревом.
Концевая вершина дерева – вершина, локальная степень которой равна 1. Концевое ребро – ребро инцидентное концевой вершине.
Назовем концевые вершины дерева Т вершинами типа 1.
Удалим из дерева Т все концевые ребра. Получим дерево Т1. Его концевые вершины назовем вершинами типа 2 (для исходного дерева Т). Продолжаем процесс, пока не останутся вершины максимального типа. Их может быть 1 или 2.
Центрами деревьев являются вершины максимального типа и только они. Все диаметральные цепи проходят через центры и имеют длину 2k–2, если центр 1; 2k–2, если центра 2.
Корнем дерева называется любая помеченная вершина.
Если в дереве определен корень, все ребра графа можно ориентировать (от корня). Причем, ребро (a, b) ориентируется от a к b, если цепь, связывающая корень с вершиной а не проходит через вершину b, и наоборот.
Ветвью вершины а называется подграф, порожденный множеством В(а) – вершин, связанных с корнем цепями, проходящими через вершину а.
Характеристические числа графа – это цикломатическое число, число внутренней устойчивости и число внешней устойчивости.
Цикломатическое число графа G находится по формуле:
Здесь – число ребер графа G; – число вершин; – число компонент связности.
, то граф не имеет циклов, то есть является деревом или лесом;
, то граф имеет ровно 1 цикл.
Число внутренней устойчивости графа G обозначается – это максимальное число несмежных вершин графа.
Множеством внешней устойчивости графа G (внешне устойчивым множеством) называется любое множество вершин Q такое, что из каждой вершины множества хотя бы одна дуга ведет в вершину множества Q. Если граф неориентированный, то число внешней устойчивости ищется для канонически соответствующего ориентированного графа.
Число внешней устойчивости графа G обозначается – это мощность минимального внешне устойчивого множества.
Сетью называется любой частично-ориентированный граф S, некоторые вершины которого помечены.
Некоторые помеченные вершины называются входными полюсами, другие – выходными полюсами. Непомеченные вершины называются внутренними. Простая цепь, связывающая входной и выходной полюс будет называться цепью.
Если сеть содержит k входных и n выходных полюсов, то она называется (k, n)-полюсником.
Двухполюсной сетью называется сеть, являющаяся (1, 1)-полюсником.
Пусть дана частично ориентированная двухполюсная сеть. Пусть для каждого ребра сети определена пропускная способность ребра .
Потоком в сети называется пара объектов , где – некоторая ориентация неориентированных ребер сети, f = f(e), функция значения потока на ребре е, которая удовлетворяет следующим условиям:
где – множество ребер выходящих из вершины ,
где – множество ребер входящих в вершину .
Если – входной полюс сети, а – выходной полюс, то
Величиной потока в сети назовем число . Очевидно, что величина потока в сети зависит и от ориентации ребер , и от задания функции f(e), то есть является величиной переменной.
Сечением в сети называется совокупность ребер, при удалении которых сеть становится несвязной. Сечение называется простым, если при удалении из него хотя бы одного ребра, оно перестает быть сечением.
Для каждого ребра простого сечения найдется цепь, проходящая только через это ребро простого сечения.
Если эта цепь идет в направлении этого ребра, то оно называется прямым, если против направления ребра, то обратным. Неориентированные ребра цепи всегда прямые.
Пропускной способностью сечения W называется сумма W(c) пропускных способностей его прямых ребер.
Теорема Форда-Фалкерсона
Максимальная величина потока в сети равна минимальной пропускной способности его простых сечений.
Источник