Дерево свойства дерева единственность пути существование висячей вершины

§3 Деревья и их свойства.

Т.1(о весячей вершине)/ во всяком конечном дереве с числом вершин n>1 существует висячая вершина.

Найдется вершина v степени

Возьмем произвольную вершину дерева

Случай 2: v –не висячая к этой вершине будет смежная с вершиннойv. т.е. vv ` не

т.к. граф цикла не имеет то каждый раз происходит переход в новую нерассматриваемую вершину т.к. граф конечен то и просмотр вершин конечен то рано или поздно попадет висячая вершина.

Двигаясь от вершины v в обратном направлении находим хотя бы еще одну висячую вершину.

Т.2/ для (n,m) графа следующ утверждения эквивалентны:

G-дерево
G – связный граф и m=n-1
G – ациклический граф и m=n-1
любые два несовпадающие вершины графа G соединят единственная простая цепь.
G- ациклический граф обладающий некоторыми свойствами что если любые две не смежные вершины соеденить ребром то получ граф имеет ровно один цикл.

Док –во: 1 2 док во от противного дано: G- дерево док-ть: m=n-1 воспользуемся теоремой о висячей вершине пусть висячей вершиной является вершина v будем выполнять просмотр дерева начиная с висячей вершины v , при просмотре добовляем каждый раз одно ребро и одну вершину т.к. циклов нет вершины каждый раз разные выполнив просмотр всего дерева получаем чтд 2 3 дано G – связен m=n-1 док-ть: G – не имеет циклов док-во: случай первый kКол-во ребер кол-во вершин граф имеет к=1 связный компонент т.е. связен чтд 4 5 дано: граф G, две вершины. доказать: если любые две не смежные вершины соеденить ребром то получ граф имеет ровно один цикл. док-во: пусть граф G имеет цикл => найдется две вершины соеденяемые по меньшей мере двумя простыми цепями это противоречит условию => циклов в графе нету соеденим вершины u и v ребром по условию они соеденены цепью => получим цикл не трудно видеть этот цикл будет единственным т.к. убрав ребро мы получили бы что в графе еще есть ребра но граф ациклический. 5  дано: G- ациклич если любые 2 не смежные вершины соединить ребром то получается равно 1 цикл док-ть: G-дерево т.е. требуется док-ть связность графа k>1 возьмем две вершины и соеденим их ребром но не получим цикла чтд Остов графа G=(V,E) пусть Н – суграф графа G суграф Н называют остовым графом G если на каждом связном компоненте порождается дерево В случае связного графа G остов называют каркасом покрывающим деревом или стягивающим графом G=(V,E) – это (n,m) – граф Т.(о циклическом ранге)/ Число ребер которые необходимо удалить в произвольном графе G для получения остова не зависит от последовательности их удаления и равно гдеk – число связанных компонентов. (m- число ребер n- число вершин) Док – во: а) G – связен тогда k=1 тогда остов есть дерево которое будет содержать n вершин и n-1 ребер тогда m-(n-1)= m-n+1= б) G – не связен имеет k>1 связных компонетов => m_i – кол-во ребер в i связный компоненте n_i – кол-во вершин =>чтд. Свойство дерева

Циклический ранг любого дерева равен нулю. Число — циклич ранг или цикломатическое число.

Т.(о центре дерева)/ Центр любого дерева состоит из одной вершины или двух смежных вершин Док-во: G=(V,E) – это (n,n-1) – граф(дерево) Случай 1 n=1 ●- это граф вершина. центр состоит из одной вершины теорема выполняется Случай 2 n=2 —это граф звено в этом случае центр состоит из двух вершин Случай 3 n>2 По теореме о висячей вершине в дереве есть хотя бы одна висячая вершина. Удалим в дереве все висячие вершины вместе с инцидентными ребрами. Не трудно видеть что в полученном дереве эксцентриситеты оставшихся вершин уменьшается на единицу. И соотношение между эксцентриситетами сохранится. Центр останется таким же как в исходном графе. Процесс удаления всяческих вершин пока не останется одна вершина или две вершины соединенные ребром тогда все сводится к первому или второму случаю. Т.е. центр состоит из одной вершины или двух смежных. Чтд Т.(Кэли)/ Число помеченных деревьев порядка n равно ( Кэли для доказательства использовал отобрадение функций) (Кергоф при док-ве этой теоремы использовал последовательности для чисел от 1 до n из множества причем числа могли повторятся.) Док- во: Подсчитаем число различных таких последовательностей. n – способов поставить на первое место любое число столькоже на второе и тд Док – во Прюфера: Далее доказывается взаимнооднозначное соответствие м/у последовательностями указанного вида и помеченными деревьями. Имеется дерево Т пометим его вершины от 1 до n Выберем в дереве вершину с наименьшим номером пусть это b₁ с ней смежная некоторая вершина а₁ Возьмем ребро e₁=b₁a₁ и рассмотрим дерево Т-e₁ полученное дерево обозначим Т₁ В этом дереве проделываем ту же процедуру выбор вершины с наименьшим номером и т д продолжая процедуру получим: — две вершины соединенных ребром выпишем: Каждому дереву (помеченному) соответствует единственная числовая последовательность построенная таким образом для каждой последn-2 соответствует единичное дерево. Чтд Ориентированное дерево. А— предок B…K – потомки вершины А С,В – непосредственный потомок вершины А(сын) D,E,F – сын для В В – непосредственный предок F для К непосредственный отец О./ Ориентированный деревом называется симметрический орентированный граф G(V,E) В катором одна вершина не имеет предков а все остальные вершины имеют только по одному непосредственному предку. Вершиныназывается корнем дерева Бинарным деревом называется ордерево в котором каждая вершина имеет не более двух непосредственных потомков. Полным бинарным деровом называется бинарн дерево в котором каждая вершина не является листом(лист-висячая вершина дерева) имеет ровно два непосредственных потомка. Взвешенный граф В реальный задачах часто приходится использовать дополнительную информацию (стоимость проезда расстояние между объектами электроники и т д ) это (n,m)-граф Взвешанным графом назыв пару (G,W) где G-граф а W-функция которая каждому ребру ставит в соотношение число— называемое весом ребрагде Весом графа называют суммарный вес его ребер Рассмотрим связный неор граф остов лин веса тогда, остовом является суграф являющийся деревом Для данного взвешенного графа нужно найти остов минимального веса что: Применяется для проектирование дорог создание электроники.

Выберем — ребро минимального строим дерево Т₁(2 вершины a и bи ребро)
На некотором шаге имеем дерева Т_k (имеем k+1 вершин) если k+1k а другой не принадлежит Т_k выбирается ребро наименьшего веса, если же k+1=n то остов по строению.

Читайте также: Во саду дерева цветет

i	e_i	W(e_i)
1	2.5	1
2	2.1	1
3	5.3	1
4	1.4	2
5	2.7	3
6	4.6	9
Р_остов=17

Источник

Важнейшие классы графов

Деревом называется связный граф , не имеющий циклов. В графе без циклов, таким образом, каждая компонента связности является деревом. Такой граф называют лесом .

P_<n data-lazy-src=

Из теоремы 2 «Маршруты, связность, расстояния» следует, что во всяком дереве, в котором не меньше двух вершин, имеется вершина степени 1. Такие вершины называют висячими вершинами , или листьями . В действительности легко доказать, что в каждом дереве не меньше двух листьев, а цепь »/> — пример дерева, в котором точно два листа.

В следующих двух теоремах устанавливаются некоторые свойства деревьев.

Теорема 1. Граф с вершинами и ребрами является деревом тогда и только тогда, когда он удовлетворяет любым двум из следующих трех условий:

m=n-1

(1) связен;
(2) не имеет циклов;
(3) .

Первые два условия вместе составляют определение дерева. Покажем, что выполнение любых двух из условий (1)-(3) влечет за собой выполнение третьего.

(1) и (2) $\Rightarrow$ (3). Индукция по числу вершин. При n=1 утверждение очевидно. При $n\ge 2$ в дереве имеется хотя бы один лист. Если из дерева удалить лист, то снова получится дерево, так как циклов не появится, а связность, очевидно, сохранится. В этом новом дереве n-1 вершин и, по предположению индукции, n-2 ребра. Следовательно, в исходном дереве было n-1 ребро.

(2) и (3) $\Rightarrow$ (1). Пусть в графе, не имеющем циклов, n-1 ребро, а его компонентами связности являются G_<1 data-lazy-src= ,G_\ldots G_»/>, причем состоит из вершин, $i=1\ldots k$ . Каждая компонента является деревом, поэтому, как доказано выше, число ребер в равно n_-1 , а всего ребер в графе $\suml_<i=1 data-lazy-src=$ ^\left(n_ -1\right) =n-k=n-1″/>. Значит, k=1 и граф связен.

Читайте также: Сад огород цветы деревья

(1) и (3) $\Rightarrow$ (2). Рассмотрим связный граф с n-1 ребром. Если бы в нем был цикл, то, удалив любое цикловое ребро, мы получили бы связный граф с меньшим числом ребер. Можно продолжать такое удаление ребер до тех пор, пока не останется связный граф без циклов, то есть дерево. Но ребер в этом дереве было бы меньше, чем n-1 , а это противоречит доказанному выше.

Теорема 2. Если — дерево, то

в любая пара вершин соединена единственным путем;
при добавлении к любого нового ребра образуется цикл;
при удалении из любого ребра он превращается в несвязный граф .

Существование пути между любыми двумя вершинами следует из связности дерева. Допустим, что в некотором дереве существуют два различных пути, соединяющих вершины и . Начальные отрезки этих путей совпадают (оба пути начинаются в одной и той же вершине ). Пусть — последняя вершина этого совпадающего начала, а после в одном пути следует вершина y_<1 data-lazy-src= »/>, а в другом — вершина y_<2 data-lazy-src= »/>. Рассмотрим ребро $\left(x,y_<1 data-lazy-src=$ \right)»/>. Если его удалить из графа, то в оставшемся подграфе вершины »/> и будут соединимыми — соединяющий их маршрут можно построить так: взять отрезок первого пути от y_<1 data-lazy-src= »/> до и к нему присоединить отрезок второго от до , взятый в обратном порядке. Но это означает, что ребро $\left(x,y_<1 data-lazy-src=$ \right)»/> не является перешейком. Однако из теоремы 4 «Маршруты, связность, расстояния» следует, что в дереве каждое ребро является перешейком. Этим доказано утверждение 1). Утверждения 2) и 3) следуют из 1).

Отметим, что единственный путь , соединяющий две вершины дерева, всегда простой (если путь не является простым, в нем обязательно содержится цикл).

Источник