Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 22
Текст из файла (страница 22)
4.11 изображены граф с гамильтоновым циклом (рис. 4.11, а) и циклически связный граф, в котором нет гамильтонова цикла (рис. 4.11, б). В последнем, чтобы пройти через вершины А, В, С, гамильтонов цикл должен содержать все лежащие на этих сторонах ребра. Но тогда он не проходит через расположенную в центре треугольника вершину О. Иногда можно построить проходящую через все вершины графа простую цепь с началом и концом в различных заданных вершинах о', оч~б. Такая цепь тоже называется гамильтоновой.
4.3. ИЕКОТОРЫЕ КЛАССЫ ГРАФОВ И ИХ ЧАСТЕЙ Дерево и лес. Неориентированное дерево — это связный неориентированный граф без циклов, а значит, без петель и кратных ребер. Несвязный (неориентированный) граф без циклов называется лесом; связные компоненты леса являются деревьями.
Любая часть леса или дерева также нс имеет циклов, т. е. являстся лесом или деревом, Любая цепь в таком графе является простой. Иначе она содержала бы цикл. Теорема 4.2. Любые две вершины дерева о' и о" связаны одной и только одной цепью. 109 Действительно, пусть 1 ~ и Ц вЂ” две различные цепи с началом о' и концом о". Тогда в цепи 1а есть хотя бы одно ребро е, не принадлежащее цепи Еь Если какая-либо из инцидентных ребру е вершин не лежит на 1.ь то соседнее ребро цепи 1,, имеющее концом эту вершину, также не. принадлежит цепи Еь Таким образом, можно, если это понадобится, расширить участок цепи Еа, состоящий из не принадлежащих цепи Л1 ребер, пока в обоих концах этого участка не окажутся вершины, лежащие на цепи Ь, (встречи с этой цепью обязательно произойдут, ведь в обоих концах цепи 1, расположены вершины о' и о", лежащие также и на цепи 1.~).
Между этими вершинами, отличающимися друг от друга, так как в дереве О нет циклов, лежит участок цепи Еь не имеющий с построенным ранее участком цепи Еа общих вершин, кроме концов (участок цепи 1.з вообще не имеет с цепью 1., общих вершин, кроме концов). Тогда из обоих этих участков составляется цикл, которого не может быть в дереве 6. П Верно и обратное: если любые две вершины графа 0 связаны единственной цепью, этот граф является деревом. Действительно, из простого цикла всегда можно составить две непересекающиеся простые цепи с одними и теми же началом и концом.
Концевые вершины и ребра. Вершина о графа 0 называется концевой, или висячей, если ее степень р(о) равна единице. Инцидентное концевой вершине ребро также называется концевым. Если конечное дерево состоит более чем из одной вершины, оно имеет хотя бы две концевые вершины и хотя бы одно концевое ребро. Действительно, пусть о — вершина дерева 6. Так как она связана с другими вершинами, из нее выходит хотя бы одно ребро.
Если другой конец о' этого ребра не является концевой вершиной, из него выходит еще одно ребро. Из другого его конца о" выходит еше одно ребро и т. д. Таким образом, строится цепь, проходящая все время через новые вершины. Иначе часть этой цепи оказалась бы циклом. Так как наше дерево конечно, процесс построения этой цепи должен закончиться, причем последнее ее ребро и одна из инцидентных ей вершин являются концевыми. Если о — концевая вершина, она является и второй концевой вершиной дерева.
Если же вершина о — не концевая, из нее выходит еше хотя бы одно ребро. Начиная с него, можно построить цепь, идущую из о в другую сторону, и в конце ее найти другую концевую вершину. ИО Дерево с корнем; ветви. Пусть в дереве 6 отмечена вершина о,. Эту вершину называют корнем дерева 6, а само дерево — деревом с корнем. В таком дереве можно естественным образом ориентировать ребра.
Вершину о' ребра (о', о") можно соединить единственной цепью (. с корнем ом Если эта цепь не содержит ребра (о', о"), в последнее вводится ориентация от о' к о"„ в противном случае — от о" к о'. Такая ориентация согласована с ориентацией того же ребра, определенной через вершину о". Действительно, если цепь |. не содержит ребра (о', о"), то, добавив это ребро, мы получим единственную цепь Т.', связывающую оь и о" и проходящую через рассматриваемое ребро. Если же цепь Ь содержит ребро (о', о"), то, отбросив его, мы получим цепь Т.', связывающую о, и о" и не содержащую этого ребра. Ориентированное таким образом дерево с корнем называется ориентированным деревом.
В нем все ребра имеют направление от корня (рис. 4.12). Если изменить направления всех ребер ориентированного дерева на противоположные (к корню), получится ориентированный граф, который тоже называют ориентированным деревом, а иногда сетью сборки. В каждую вершину ориен- тированного дерева (за исклю- Риа ед2 чением корня) входит только одно ребро, т. е. эта вершина является концом одного и только одного ребра. Действи. тельно, такое ребро является последним в цепи, связывающей рассматриваемую вершину с корнем, а эта цепь единственна. В корень не входит ни одно ребро, все инцидентные корню ребра связывают его со своими вторыми концами, значит, корень является их началом.
Любое дерево можно ориентировать, выбрав в качестве корня любую его вершину. Это доказывает, что в ко н е ч н о м д е р е в е число вершин на единицу б ол ьш е числа реб е р. Пусть о — вершина дерева 6 с корнем оь, В(о) — мно жество всех вершин, связанных с корнем цепями, проходящими через вершину о (т.е. имеющими ребра, инцидентные о). Это множество порождает подграф 6(о), который называется ветвью вершины о в дереве с корнем оы Как 111 подграф дерева, т.
е. графа без циклов, 6(п) тоже не имеет циклов; любые вершины о', п"с В(о) связаны в этой ветви маршрутом, составленным нз участков цепей 1. (о') и 1.(о") от корпя са до этих вершин, начинающихся в вершине о. Нужно только доказать, что эти участки целиком погружены в 6(с), но это справедливо, так как в кагкдую вершину такого участка ведет цепь из корня о„являющаяся начальным участком соответствующей цепи 1.(о') или 1.(о") и проходящая через вершину и, Таким образом, ветвь 6(о) связпа и сама является деревом.
Рассмотрим 6(о) как дерево с корнем о. Для любой вершины с'я6(с) связывающая ее с о цепь 1.(п, и')— это конец цепи 1.(по, и'), связывающей в дереве 6 эту вершину с корнем па, Следовательно, последнее ребро втой цепи, входящее в вершину и' в исходном дереве 6 и в его ветви 6(п), ориентируется в обоих этих деревьях с корнем одинаково, так что вершина и' является его концом. Типы вершин и центры деревьев. Пусть дано конечное дерево 6.
Назовем его концевые вершины вершинами типа 1. Отметим, что если дерево имеет более двух вершин, то среди них есть неконцевые вершины. Действительно, пусть с~ и оз — концевые вершины. Они должны быть связаны цепью. Если эта цепь состоит из одного ребра, то о, и и, не связаны ни с какими другими вершинами, что противоречит связности дерева; если же эта цепь состоит из двух или более ребер, то она проходит через вершины степени большей или равной двум, т.е. неконцевые вершины Удалим из дерева 6 все вершины типа 1 и ннцидентные им концевые ребра. Останется связный граф 6' без циклов, т.е дерево. Действительно, для любых вершин о', о"я 6' связывающая их в дереве 6 цепь 1.(о', и") не может проходить через концевые ребра и целиком лежит в 6'.
Дерево 6' также имеет концевые вершины, которые' будем называть вершинами типа 2 в дереве 6. Аналогично определяются вершины типов 3, 4 и т.д, Легко видеть, что в конечном дереве 6 имеготся вершины лишь конечного числа типов, причем число вершин максимального типа равно единице или двум, так как в соответствующем дереве каждая вершина является концевой. Каждая вершина дерева 6, кроме концевых, имеет соседей иа единицу меньшего типа.
Действительно, в дереве 6~ь-'>, определяющей предыдущий тип, она не была концевой, а в 6еп стала. Значит, при построении этого дерева были 112 удалены некоторые инцидентные этой вершине концевые ребра дерева 6М-П и другие их концы — соседние с рассматриваемой вершиной вершины типа А — 1. Остальные инцидентные рассматриваемой вершине ребра, кроме, мо>кет быть, одного, были удалены раньше, и соответствующие им соседние вершины имеют меньший тип. Одно же инцидентное ребро остается, ес- Х ли только рассматриваемая вершина — пе единственная, 1 имеющая максимальный Ю г у тип. Другой конец этого реб.
9 ра — вершина старшего типа, если тип рассматривае- 3 мой вершины немаксимальиый, и вершина того же Ряс. 4.!з типа — в противном случае (рис. 4.13, цифры у вершин означают их типы). Теорема 4.3. Центрами дерева являются вершины максимального типа й и только они.
Любая цепь Ь с началом в вершине оа максимального типа идет последовательно по вершинам уменьшающихся типов. Ее первое ребро (о,, в~) ведет либо в вершину в~ ранга А, либо в вершину меньшего типа. Следующие ребра (вь о>), (пь о>) н т.д. уже обязательно ведут в вершины меньшего типа, так как единственная соседняя вершина большего или равного типа — это вершина, инцидентная уже использованному ребру.
Таким образом, для длины 1 цепи Е с началом в вершине максимального типа Й имеем: 1(А)(й, если есть еще одна вершина типа й; 1(Ь)~й — 1, если такая вершина единственна. Так как у каждой вершины дерева есть хотя бы одна соседняя, тип которой на 1 меньше, то из вершины максимального типа й можно построить путь длины й — !.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
