Сколько ребер имеет дерево содержащее n вершин

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

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

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

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

Случай 1: v – висячая

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

Рассмотрим вершину v `

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

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

Пусть G=(V,E) – это (n,m) –граф

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

G – связный граф и m=n-1

G – ациклический граф и m=n-1

любые два несовпадающие вершины графа G соединят единственная простая цепь.

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

1 2 док во от противного

воспользуемся теоремой о висячей вершине пусть висячей вершиной является вершина v

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

2 3 дано G – связен m=n-1 док-ть: G – не имеет циклов

случай первый k<n вершин содержит цикл который содержит цикл

вне цикла: n-k вершин и n-k ребер

всего ребер: k(n-k)=n

т.е. m=n-1 не выполняется т.е. противоречит

случий 2 k=n n=m –ребер входит в цикл а это противоречит условию: m=n-1

3  4 дано: G ациклический и m=n-1докозать: любые две не совпадающие вершины соединяет единственная простая чепь.

Докажем что цепь единственна

Чтобы докозать что такая цепь существует надо док-ть что граф связан

К- связный компонент

Кол-во ребер

кол-во вершин

граф имеет к=1 связный компонент т.е. связен

дано: граф G, две вершины.

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

пусть граф G имеет цикл => найдется две вершины соеденяемые по меньшей мере двумя простыми цепями это противоречит условию => циклов в графе нету соеденим вершины u и v ребром по условию они соеденены цепью => получим цикл не трудно видеть этот цикл будет единственным т.к. убрав ребро мы получили бы что в графе еще есть ребра но граф ациклический.

5  дано: G- ациклич если любые 2 не смежные вершины соединить ребром то получается равно 1 цикл

т.е. требуется док-ть связность графа

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) – граф(дерево)

●- это граф вершина.

центр состоит из одной вершины

—это граф звено

в этом случае центр состоит из двух вершин

По теореме о висячей вершине в дереве есть хотя бы одна висячая вершина. Удалим в дереве все висячие вершины вместе с инцидентными ребрами.

Не трудно видеть что в полученном дереве эксцентриситеты оставшихся вершин уменьшается на единицу. И соотношение между эксцентриситетами сохранится. Центр останется таким же как в исходном графе.

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

Т.(Кэли)/ Число помеченных деревьев порядка n равно ( Кэли для доказательства использовал отобрадение функций) (Кергоф при док-ве этой теоремы использовал последовательности для чисел от 1 до n из множества причем числа могли повторятся.)

Подсчитаем число различных таких последовательностей.

n – способов поставить на первое место любое число столькоже на второе и тд

Док – во Прюфера:

Далее доказывается взаимнооднозначное соответствие м/у последовательностями указанного вида и помеченными деревьями.

Имеется дерево Т пометим его вершины от 1 до n

Выберем в дереве вершину с наименьшим номером пусть это b₁ с ней смежная некоторая

вершина а₁ Возьмем ребро e₁=b₁a₁ и рассмотрим дерево Т-e₁ полученное дерево обозначим Т₁ В этом дереве проделываем ту же процедуру выбор вершины с наименьшим номером и т д продолжая процедуру получим:

— две вершины соединенных ребром выпишем: Каждому дереву (помеченному) соответствует единственная числовая последовательность построенная таким образом для каждой последn-2 соответствует единичное дерево.

Ориентированное дерево.

А— предок

B…K – потомки вершины А

С,В – непосредственный потомок вершины А(сын)

В – непосредственный предок

F для К непосредственный отец

О./ Ориентированный деревом называется симметрический орентированный граф G(V,E)

В катором одна вершина не имеет предков а все остальные вершины имеют только по одному непосредственному предку. Вершиныназывается корнем дерева

Бинарным деревом называется ордерево в котором каждая вершина имеет не более двух непосредственных потомков.

Полным бинарным деровом называется бинарн дерево в котором каждая вершина не является листом(лист-висячая вершина дерева) имеет ровно два непосредственных потомка.

Взвешенный граф

В реальный задачах часто приходится использовать дополнительную информацию (стоимость проезда расстояние между объектами электроники и т д )

это (n,m)-граф

Взвешанным графом назыв пару (G,W) где G-граф а W-функция которая каждому ребру ставит в соотношение число— называемое весом ребрагде

Весом графа называют суммарный вес его ребер

Рассмотрим связный неор граф остов лин веса тогда, остовом является суграф являющийся деревом Для данного взвешенного графа нужно найти остов минимального веса что:

Применяется для проектирование дорог создание электроники.

Выберем — ребро минимального строим дерево Т₁(2 вершины a и bи ребро)

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

Теория графов – деревья

Деревья – это графики, которые не содержат ни одного цикла. Они представляют иерархическую структуру в графической форме. Деревья относятся к простейшему классу графов. Несмотря на их простоту, они имеют богатую структуру.

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

дерево

Связный ациклический граф называется деревом. Другими словами, связный граф без циклов называется деревом.

Края дерева известны как ветви . Элементы деревьев называются их узлами . Узлы без дочерних узлов называются листовыми узлами .

Дерево с ‘n’ вершинами имеет ‘n-1’ ребер. Если у него есть еще одно ребро, превышающее ‘n-1’, то это дополнительное ребро, очевидно, должно соединиться с двумя вершинами, что приводит к образованию цикла. Затем он становится циклическим графом, что является нарушением для графа дерева.

Пример 1

График, показанный здесь, является деревом, потому что у него нет циклов, и он связан. Он имеет четыре вершины и три ребра, т. Е. Для ‘n’ вершин ‘n-1’ ребер, как указано в определении.

дерево

Примечание. Каждое дерево имеет как минимум две вершины первой степени.

Пример 2

Дерево 1

В приведенном выше примере вершины «a» и «d» имеют степень один. А две другие вершины ‘b’ и ‘c’ имеют второй уровень. Это возможно, потому что для того, чтобы не формировать цикл, в диаграмме должно быть как минимум два отдельных ребра. Это не что иное, как два ребра со степенью один.

Несвязный ациклический граф называется лесом. Другими словами, непересекающаяся коллекция деревьев называется лесом.

пример

Следующий график выглядит как два подграфа; но это один несвязный граф. На этом графике нет циклов. Отсюда ясно, что это лес.

лес

Охватывающие деревья

Пусть G – связный граф, тогда подграф H в G называется остовным деревом в G, если –

H это дерево
H содержит все вершины G.

Остовное дерево T неориентированного графа G является подграфом, который включает в себя все вершины G.

пример

Охватывающие деревья

В приведенном выше примере G является связным графом, а H является подграфом G.

Ясно, что граф H не имеет циклов, это дерево с шестью ребрами, которое на единицу меньше общего числа вершин. Следовательно, H – остовное дерево группы G.

Circuit Rank

Пусть «G» связный граф с «n» вершинами и «m» ребрами. Остовное дерево ‘T’ группы G содержит (n-1) ребер.

Следовательно, количество ребер, которые нужно удалить из ‘G’, чтобы получить остовное дерево = m- (n-1), которое называется рангом схемы G.

Эта формула верна, потому что в остовном дереве вам нужно иметь ребра n-1. Из «m» ребер вам нужно сохранить «n – 1» ребер в графе.

Следовательно, удаление ребер n – 1 из m дает ребра, которые нужно удалить из графа, чтобы получить остовное дерево, которое не должно образовывать цикл.

пример

Посмотрите на следующий график –

Circuit Rank

Для графика, приведенного в примере выше, у вас есть m = 7 ребер и n = 5 вершин.

Тогда ранг цепи

пример

Пусть ‘G’ – связный граф с шестью вершинами, а степень каждой вершины равна трем. Найдите звание цепи «G».

По сумме теоремы о степени вершин

Схема ранг = | E | – (| V | – 1)

Теорема Кирхгофа

Теорема Кирхгофа полезна для нахождения числа связующих деревьев, которые могут быть сформированы из связного графа.

пример

Теорема Кирхгофа

Матрица «А» заполняется так, как если между двумя вершинами есть ребро, то она должна быть задана как «1», иначе «0».

Дерево (теория графов)

Дерево — это связный ациклический граф. [1] Связность означает наличие путей между любой парой вершин, ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.

Ориентированное (направленное) дерево — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями. [2]

Формально дерево определяется как конечное множество одного или более узлов со следующими свойствами:

существует один корень дерева
остальные узлы (за исключением корня) распределены среди $m\geq 0$ непересекающихся множеств , и каждое из множеств является деревом; деревья называются поддеревьями данного корня

Содержание

Связанные определения

Степень узла — количество исходящих дуг (или, иначе, количество поддеревьев узла).
Концевой узел (лист, терминальная вершина) — узел со степенью 1 (то есть узел, в который ведёт только одно ребро; в случае ориентированного дерева — узел, в который ведёт только одна дуга и не исходит ни одной дуги).
Узел ветвления — неконцевой узел.
Уровень узла — длина пути от корня до узла. Можно определить рекурсивно:

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

Дерево с отмеченной вершиной называется корневым деревом.
- -й ярус дерева — множество узлов дерева, на уровне от корня дерева. на вершинах: $u \prec v$ , если вершины и различны и вершина лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной .
- корневое поддерево с корнем — подграф
  
  Термин двоичное дерево (оно же бинарное дерево) имеет несколько значений:
  - Абстрактная структура данных, используемая в программировании. На двоичном дереве основаны такие структуры данных, как двоичное дерево поиска, двоичная куча, красно-чёрное дерево, АВЛ-дерево, фибоначчиева куча и др.
  N-арные деревья
  
  N-арные деревья определяются по аналогии с двоичным деревом. Для них также есть ориентированные и неориентированные случаи, а также соответствующие абстрактные структуры данных.
  - N-арное дерево (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят N+1.
  - N-арное дерево (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят N.
  Свойства
  - Дерево не имеет кратных рёбер и петель.
  - Любое дерево с вершинами содержит ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда , где — число вершин, — число рёбер графа.
  - Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственной простой цепью.
  - Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.
  - Любое дерево является двудольным графом. Любое дерево, множество вершин которого не более чем счётное, является планарным графом.
  - Для любых трёх вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину.
  Подсчёт деревьев
  - Число различных деревьев, которые можно построить на нумерованных вершинах, равно верна следующая асимптотика
  Кодирование деревьев
  
  Дерево можно кодировать наборами из нулей и единиц. Рассмотрим, например, укладку дерева на плоскости. Начиная с какой либо вершины, будем двигаться по ребрам дерева, сворачивая в каждой вершине на ближайшее справа ребро и поворачивая назад в концевых вершинах дерева. Проходя по некоторому ребру, записываем при движении по ребру в первый раз и при движении по ребру второй раз (в обратном направлении). Если — число рёбер дерева, то через шагов мы вернемся в исходную вершину, пройдя по каждому ребру дважды. Полученная при этом последовательность из и (код дерева) длины позволяет однозначно восстанавливать не только само дерево , но и его укладку на плоскости. Произвольному дереву соответствуют несколько таких кодов. В частности, из этого способа кодирования вытекает следующая грубая оценка на число деревьев с вершинами:
  
  $t_n\le T_n< 2^<2n>» width=»» height=»» /></p> <h2>Что такое граф? Определения и примеры</h2> <p>Связный неориентированный ациклический граф называется деревом , множество деревьев называется лесом . В связном неориентированном графе <img decoding=$ существует по крайней мере один путь между каждой парой вершин; отсутствие циклов в означает, что существует самое большее один такой путь между любой парой вершин в . Поэтому, если — дерево , то между каждой парой вершин в существует в точности один путь . Рассуждение легко обратимо, и поэтому неориентированный граф будет деревом тогда и только тогда, если между каждой парой вершин в существует в точности один путь . Так как наименьшее число ребер, которыми можно соединить вершин, равно и дерево с вершинами содержит в точности ребер, то деревья можно считать минимально связными графами. Удаление из дерева любого ребра превращает его в несвязный граф , разрушая единственный путь между по крайней мере одной парой вершин.
  
  Особый интерес представляют остовные деревья графа , то есть деревья, являющиеся подграфами графа и содержащие все его вершины. Если граф несвязен, то множество, состоящее из остовных деревьев каждой компоненты называется остовном лесом графа. Для построения остовного дерева (леса) данного неориентированного графа , мы последовательно просматриваем ребра , оставляя те, которые не образуют циклов с уже выбранными.
  
  Во взвешенном графе часто интересно определить остовное дерево ( лес ) с минимальным общим весом ребер, то есть дерево ( лес ), у которого сумма весов всех его ребер минимальна. Такое дерево называется минимумом оставных деревьев или минимальное остовное дерево . Другими словами, на каждом шаге мы выбираем новое ребро с наименьшим весом (наименьшее ребро ), не образующее циклов с уже выбранными ребрами; этот процесс продолжаем до тех пор, пока не будет выбрано $\left| V \right| - 1$ ребер, образующих остовное дерево . Этот процесс известен как жадный алгоритм .
  
  Жадный алгоритм может быть выполнен в два этапа. Сначала ребра сортируются по весу и затем строится остовное дерево путем выбора наименьших из имеющихся в распоряжении ребер.
  
  Существует другой метод получения минимума остовных деревьев , который не требует ни сортировки ребер, ни проверки на цикличность на каждом шаге, — так называемый алгоритм ближайшего соседа . Мы начинаем с некоторой произвольной вершины в заданном графе. Пусть — ребро с наименьшим весом, инцидентное ; ребро включается в дерево . Затем среди всех ребер, инцидентных либо , либо , выбираем ребро с наименьшим весом и включаем его в частично построенное дерево . В результате этого в дерево добавляется новая вершина , например, . Повторяя процесс, ищем наименьшее ребро , соединяющее , или с некоторой другой вершиной графа. Процесс продолжается до тех пор, пока все вершины из не будут включены в дерево , то есть пока дерево не станет остовным.
  
  Наихудшим для этого алгоритма будет случай, когда — полный граф (то есть когда каждая пара вершин в графе соединена ребром); в этом случае для того, чтобы найти ближайшего соседа, на каждом шаге нужно сделать максимальное число сравнений. Чтобы выбрать первое ребро , мы сравниваем веса всех $\left| V \right| - 1$ ребер, инцидентных вершине , и выбираем наименьшее; этот шаг требует $\left| V \right| - 2$ сравнений. Для выбора второго ребра мы ищем наименьшее среди возможных $2(\left| V \right| - 2)$ ребер (инцидентных или ) и делаем для этого $2(\left| V \right| - 2) - 1$ сравнений. Таким образом, ясно, что для выбора -го ребра требуется $i(\left| V \right| - i) - 1$ сравнений, и поэтому в сумме потребуется
  
  $\sum\limits_<i = 1>^ <\left| V \right| - 1> <[i(\left| V \right| - i) - 1] = \frac<1><6>\left| V \right|^3 + O(\left| V \right|^2 )>» /></p> <h4>Клики</h4> <p>Максимальный полный подграф графа <img decoding=$ называется кликой графа ; другими словами, клика графа есть подмножество его вершин, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством. Например, на рис. 12.3 показан граф и его клики.
  
  Клики графа представляют «естественные» группировки вершин, и определение клик графа полезно в кластерном анализе в таких областях, как информационный поиск и социология.
  
  Изоморфизм
  
  Два графа называются изоморфными , если существует взаимно однозначное соответствие $f:V_A \to V_B$ , такое, что $(v,w) \in E_A$ тогда и только тогда, если $(f(v),f(w)) \in E_B$ , то есть существует соответствие между вершинами графа и вершинами графа , сохраняющее отношение смежности. Например, на рис. 12.3 показаны два изоморфных орграфа: вершины в орграфе соответствуют вершинам 2, 3, 6, 1, 4, 5 в указанном порядке в орграфе и может быть более чем одно соответствие, и на рис. 12.3 графы имеют на самом деле второй изоморфизм : соответствуют в указанном порядке вершинам 2, 3, 6, 1, 5, 4. Изоморфные графы отличаются только метками вершин, в связи с чем задача определения изоморфизма возникает в ряде практических ситуаций, таких, как информационный поиск и определение химических соединений.
  
  Заметим, что можно ограничится орграфами. Любой неориентированный граф превращается в орграф заменой каждого ребра двумя противоположно направленными ребрами. Два полученные таким образом орграфа, очевидно, изоморфны тогда и только тогда, если изоморфны исходные графы.
  
  Планарность
  
  Граф называют планарным, если существует такое изображение на плоскости его вершин и ребер, что:
  - каждая вершина изображается отдельной точкой на плоскости;
  - каждое ребро изображается простой кривой, имеющей концевые точки ;
  - эти кривые пересекаются только в общих концевых точках. Задача определения того, можно ли изобразить граф на плоскости без пересечения ребер, имеет большой практический интерес (например, при конструировании интегральных схем или печатных плат необходимо выяснить, можно ли окончательную схему вложить в плоскость).
  Определение планарности графа отличается от других рассмотренных нами задач, поскольку при изображении точек и линий на плоскости приходится больше иметь дело с непрерывными, а не с дискретными величинами. Взаимосвязь между дискретными и непрерывными аспектами планарности заинтересовала математиков и привела к различным характеристикам планарных графов. С точки зрения математики эти характеристики изящны, но эффективных алгоритмов определения планарности они не дают. Наиболее успешный подход к определению планарности состоит просто в том, что граф разбивается на подграфы и затем делается попытка разместить его на плоскости, добавляя подграфы один за другим и сохраняя при размещении планарность.
  
  Вначале сделаем несколько простых, но полезных наблюдений. Поскольку орграф планарен тогда и только тогда, если планарен соответствующий неориентированный граф , полученный игнорированием направления ребер, то достаточно рассматривать только неориентированные графы, поскольку неориентированный граф планарен тогда и только тогда, если все его двусвязные компоненты планарны. Поэтому если неориентированный граф является разделимым, мы можем разложить его на двусвязные компоненты и рассматривать их отдельно. Наконец, поскольку параллельные ребра и петли всегда можно добавить к графу или удалить из него без нарушения свойства планарности, нам достаточно рассматривать только простые графы. Поэтому при определении планарности будем предполагать, что граф неориентированный, простой и двусвязный .
  
  Наша основная стратегия состоит прежде всего в том, чтобы в графе найти цикл , разместить на плоскости в виде простой замкнутой кривой, разложить оставшуюся часть на непересекающиеся по ребрам пути и затем попытаться разместить каждый из этих путей либо целиком внутри , либо целиком вне . Если нам удалось разместить так весь граф , то он планарен, в противном случае он непланарен. Трудность этого способа заключается в том, что при размещении путей можно выбирать либо внутренность, либо внешность , и мы должны проконтролировать, чтобы неправильный выбор области размещения на ранней стадии не устранял возможности размещения последующих путей, — это могло бы привести нас к неверному заключению, что планарный граф непланарен.
  Похожие публикации: