В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

2) =ь- 3) Граф С связен и т = п — 1. Нужно доказать, что в С пет циклов. Пусть, напротив, в графе С есть цикл и пусть е — ребро этого цикла. Тогда граф С вЂ” е связен (лемма 4.8) и имеет п — 2 ребра, что противоречит теореме 4.9. Следовательно, 6 — ациклическнй граф. 3) ~ 4) Пусть й — число компонент графа С. Пусть, далее, компонента Т; является (иь т,)-графом. Так как Т; — дерево, то верно равенство (1). Теперь имеем п — 1 = т = т~+ те+... + т, = =(п1 — 1)+(пг 1)+...

+(Пь — 1) = =(п1 +... + п„) — к = и — к, т. е. й 1. Итак, С вЂ” связный граф и потому любые не- совпадатощие вершины и и о соединены в нем простой цепью. Если бы в 6 были две несовпадающие простые (и, о)-цешц то согласно утверждению 4.3 их обьедппеиие содержало бы цикл. Следовательно, каждые две вершипы соединены единственной простой цепью.

4) -ь. 5) Пара иесовпадающих вершин, принадлеигащкх одпому циклу, соединена по меньшей мере двумя простыми цепями. Следовательно, граф 6 ациклический. Пусть и и о — две его несмежные вершины, Присоединим к графу 6 ребро е = ио. В С есть простая (и, о)-цепь, которая в 6+ е дополняется до цикла. В силу утверждения 4.4 этот цикл единственный. 5) =~- 1) Нужно доказать, что граф 6 связен. Если бы вершипы и и о принадлежали разным компонептам графа 6, то граф С+ ио пе имел бы циклов, что противоречит утверждению 5). Итак, 6 связея и потому является деревом.

<1 Следствие 13.2. В любом дереве порядка п~2 имеется не менее двух кониевььх вершин. 1> Пусть Ын дг, ..., д„ (2) — степенная последовательность дерева. Тогда и ~~.", А = 2 (и — 1) Ззг (лемма о рукопоигатиях) и все 4) О. Следовательно, хотя бы два числа из последоватольиости (2) равны 1. 0 Пусть Н вЂ” остовпый подграф произвольного графа С.

Если па каждой области связности графа 6 графом Н порождается дерево, то Н называется остовом (или каркасом) графа С. Очевидно, что в каждом графе существует остов: разрушая в каждой компопепте циклы, т. е. удаляя лишние ребра, придем к остову. Остов в графе легко найти с помощью поиска в ширину. Следствие 13.3. Число ребер произволыгого графа 6, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно т(6) — ~6~+ й(6), где т(6) и й(6) — число ребер и число компонент графа 6 соответственно. Если (пн пг1)-граф Н является одной из компонент графа С, то для превращения ее в остовное дерево нужно удалить т~ — (п1 — 1) подходящих робер. Суммируя по всем й(6) компопептам, получим требуемое.

З 55 Число т(6) = т(6) — ~С~ + й(С) называется циклическим ранголв (или уикломатическизг числозв) графа С. Число т*(6)= ~6~ — й(С) робер любого остова графа 6 называется коуиклзческилс ранголг графа С. Таким образом, т(6)+ т*(6) = т(6). Очовндны трн следствия 13А — 13.6. С л о д с т в и е 13А. Граф С является лесом тогда и только тогда, когда т(6) =О. С л едет вне 13.5. Граф С имеет единственный цикл тогда и только тогда, когда т(6) = 1, С л едет в не 13.6. Граф, в которозг число ребер не меньше, чем число вершин, содержит цикл. В гл. 111 окажутся полезными утверждения 13.7, 13.8.

Утверждение 13.7. Всякий аииклический подграф произвольного графа С содержится в некотором остове графа С. Пусть Н вЂ” ациклический подграф в С. Очевидно, что достаточно рассмотреть ситуацию, в которой Н вЂ” остовный подграф и С связен. Если теперь Н не является остовом, то он несвязен. Пусть А — одна из ооластей связности графа Н. В графе С есть такое ребро аЬ, что а ~и А, Ь ~ )тН~А. Граф Н + аЬ вЂ” ациклический остовный подграф графа С, имеющий меньше, чем Н, компонент.

Повторяя аналогичное построение, доберемся до дерева, т. е. до остова, содержащего граф В. 0 Утверждение 13.8. Если Я и Т вЂ” два остова графа С, то для любого ребра е~ графа Я существует такое ребро ез графа Т, что граф Я вЂ” в~+ее также является остоволь ~' Ие ограничивая общности, будем считать граф С связным. Граф Я вЂ” е~ имеет ровно две области связности; пусть это будут А и В. Поскольку граф Т связен, то в нем существует ребро ег, один из концов которого входит в А, а другой — в В.

Граф Н = Я вЂ” е~ + ез связен и число ребер в нем такое же, как в дереве Я. Следовательно, он сам является деревом. Итак, Н вЂ” остов гра- фа С.0 Очевидно, что два предыдущих утверждения об остовах (13.7 и 13.8) сохраняются для произвольного псевдо- графа. Докажем еще следующую теорему. Теорема 13.9. Центр любого дерева состоит из одной или из двух смежных вершин. ~> Очевидно, что концевые верпшпы дерева Т являются цептральпымн только для Т = К~ нли Т = Кг. Пусть Т вЂ” дерево порядка и ) 2. Удалив из Т все концевые воршины, получим дорево Т .

Очевидно, что эксцонтриситет Т на единицу меныпе эксцентриситета дерева Т н что центры деревьев Т н Т' совпадают. Далее доказательство легко проводится индукцией по числу вор,,а з 14. Матричная теорема Кирхгофа Как уже отмечалось, в каждом графе имеется остов. В общем случае остов определен неоднозначно, Естественно возникает вопрос: как много остовов в графе? Очевидно, что при ответе на этот вопрос достаточно ограничиться случаем связного графа.

В связном графе остовом служит любое остовное дерево, т. е. остовный подграф, являющийся доревом. Число остовов в связном графе определяется в неявной форме следующей теоремой. Теорема Кирхгофа (1847 г). Число остовных деревьев в связном графе 6 порядка и ) 2 рав>ю алгебраическому дополненшо л>обого элемента матрицы Кирхгофа В(6). Доказательство опирается на следующую лемму.

Лемма 14.1. Пусть Н вЂ” (т+1, >п)-граф, 1 — матрица инцидентности какой-либо его ориентации, ЛХ вЂ” произвольный минор порядка ль матрио,ы 1. Тогда: 1) если Н вЂ” дерево, то ЛХ = ~ 1; 2) если Н не является деревом, то М = О. С. Доказательство л ем мы. Прежде всего заметим, что можно произвольно менять нумерации вершин и ребер графа Н, от этого рассматриваомый минор может лишь изменить знак. Пусть а — вершина, соответствующая строке матрицы 1, не вошедшей в минор М.

Если граф Н не является деревом, то он иесвязен. Пусть К = (1, 2, ..., )с) — его область связности, не содержащая верпшны а. С помощью подходящей перенумерацнп ребер графа Н матрицу 1 приведем к клеточно-диагональному виду 1 = с(>ад (1>, Хг), гдо 1> — матрица инцидентности компоненты Н(К). Минор ЛХ содер>кит всо первые )с строк матрицы 1, сумма которых равна нулевой строке. Следовательно, Л1 = О. Пусть теперь Н вЂ” дерево. Заново перонумеруем вершины н ребра графа Н следу>ощнм образом.

Одной пз концевых вершин о, отличных от вершины а, а также ребру, инцпдентному вершине о, присвоим номер 1. Далее рассмотрим дерево Т> = Н вЂ” о. Если его порядок болыпе 1, то одной пз его концевых вершин и, отличных от а, а такнзе инцпдептпому ей ребру присвоим помер 2. Рассмотрим дерево Тг= Т~ — и. Итерируя этот процесс, получим новые нумерации вершин и ребер дерева В, причем вершина а будет иметь номер гп+ 1. Матрица 1 при этом примет вид + 1 О ...

+ т ... о (Здесь и в дальнейшем символом в будут обозначаться те элементы или блоки матрицы, значения которых пе влияют па ход рассуясдени1ь) Минор М, остающийся после удаления последней строки этой матрицы, равен ~1. < Еще один факт, используемьш при доказательстве теоремы Кирхгофа,— формула Бппз — Коши, которую мы приведем без доказательства. Пусть А и  — и Х т- и гп Х и-матрицы соответственно, С = АВ и и ~ пг. Минор порядка и матрицы В назовем соответствующим минору порядка и матрицы А, если мнонгества номеров строк первого из них и номеров столбцов второго совпадают. Формула Би из — Коши. Определитель матрицы С равен сумме произведений каждого минора порядка и матрицы А на соответствующий минор матрицы В.

с Доказательство теоремы Кнрхгофа. Пусть 1 — матрица инцидентпости какой-либо ориентации (и, т)-графа 6. Согласно утверясденнзо 6.4 верно равенство В (6) = 11'. (1) Поскольку 6 — связный граф, то тп > и — 1. Бели В— подматрица, остающаяся после удаления из В(6) последних строки и столбца, а С вЂ” подматрпца, остающаяся после удаления из 1 последней строки, то в силу (1) В = = ССт.

Алгебраическое дополнение А элемента, занимающего в матрице В(6) позицию (и, и), равно де~В. Из формулы Бина — Коши теперь следует, что А. равно сумме квадратов всех миноров порядка п — 1 матрицы С. Согласно ломме 14.1 каждый такой минор М равен ь1, если остовный подграф графа 6, ребра которого соответствуют столбцам, вопгедшпм в М, является деревом, и нулю в противном случае. Следовательно, Л„„равно числу остоиных деровьев в графе 6.

Характеристики

Список файлов лекций