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

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

  • автор:

4.5. Деревья

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

Ориентированным деревом называется бесконтурный орграф, у которого отрицательная полустепень ρ – любой вершины не более 1 и существует ровно одна вершина, называемая корнем ориентированного дерева, у которой отрицательная степень ρ – = 0.

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

1. В неориентированном дереве существуют по крайней мере две концевые вершины.

2. Между любыми двумя вершинами дерева имеется ровно один путь.

3. Число ребер в дереве всегда на единицу меньше числа вершин (m = n–1).

Поскольку в дереве все пути – простые, то в нем есть по крайней мере один максимальный путь, т. е. путь, который нельзя продолжить. Концы этого пути и являются концевыми вершинами.

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

Третий пункт теоремы проще всего доказать, используя понятие ориентированного дерева. Выберем в дереве произвольную вершину. Назовем ее корнем. Ребра, инцидентные корню, ориентируем в направлении от корня. Для каждой вершины vi, являющейся концом одного из этих ребер, ориентируем остальные инцидентные ей ребра в направлении от vi. Продолжаем эту процедуру до тех пор, пока не будут достигнуты концевые вершины. В силу единственности пути между вершинами ни одна вершина не будет достигнута дважды (т. е. не придется ориентировать уже ориентированные ребра), а в силу связности дерева все вершины будут достигнуты. Из этой процедуры видно, что корень не имеет входящих ребер, а все остальные вершины имеют по одному входящему ребру. Поскольку все ребра являются входящими для какой-то вершины и в процессе ориентации число вершин и ребер не изменилось, то отсюда и следует п. 3 теоремы.

Для ориентированных деревьев свойства 1 и 3 верны всегда, а свойство 2 – нет. Вот почему ориентированное дерево: 1) всегда слабо связно; 2) односторонне связно, только если оно является ориентированной цепью (т.е. когда все вершины лежат на единственном пути из корня); 3) никогда не бывает сильносвязным, поскольку сильно связный граф обязательно содержит цикл.

Для всех вершин ориентированного дерева, за исключением корня, отрицательная полустепень ρ – = 1, а положительная полустепень ρ + может принимать любое значение от нуля. При этом те вершины, у которых положительная полустепень ρ + = 0, называются листьями дерева. Ориентированное дерево, у которого каждая вершина, отличная от корня, есть лист, называется кустом.

Рассмотрим некоторые параметры, которые характеризуют ориентированное дерево.

v0 Уровень 3

v1 v2 v3 Уровень 2

v4 v5 v6 v7 v8 Уровень 1

v9 Уровень 0

Высота ориентированного дерева – это наибольшая длина пути из корня в лист; глубина вершины ориентированного дерева – это длина пути из корня в эту вершину; высота вершины – это наибольшая длина пути из данной вершины в лист и , наконец, уровень вершины ориентированного дерева – это разность между высотой ориентированного дерева и глубиной данной вершины. Из этих определений можно сделать вывод, что уровень корня равен высоте дерева, но уровни различных листьев так же, как и их глубины, могут быть различны, однако высота любого листа равна нулю (рис. 4.15).

При идентификации деревьев удобной является корневая форма представления дерева. При выборе корня из дерева последовательно удаляются все концевые вершины и ребра до тех пор, пока не останется одна вершина или две. В первом случае оставшаяся вершина выбирается в качестве корня и называется центром. Во втором случае вершины и связывающее их ребро образуют бицентр.

При другом способе выбора корня дерева используется понятие высоты вершины. С каждой вершиной связаны ответвления, представляющие собой части дерева. В качестве корня выбирается вершина с наименьшей высотой и называется центроидом. Если имеются две такие вершины, то они вместе с объединяющим их ребром образуют бицентроид. При этом за корень принимается та вершина, из которой вырастает дерево с меньшим числом вершин.

Любую булеву функцию можно наглядно изобразить в виде ориентированного дерева. При этом листья этого дерева помечаются переменными или константами логического уравнения, а каждый узел, не являющийся листом, – одной из операций булевой алгебры. Пример такого дерева для функции

показан на рис. 4.16

О />риентированное дерево называютбинарным, если положительная полустепень любой его вершины не больше 2; бинарное ориентированное дерево называют полным, если из любой его вершины, не являющейся листом, исходят ровно две дуги, а уровни листьев совпадают. Примеры различных бинарных ориентированных деревьев приведены на рис. 4.17. На рис. 4.17а, б показаны неполные ориентированные бинарные деревья, на рис. 4.17в – полное. Рис. 4.16

Теорема 4.4 (теорема о высоте бинарного ориентированного дерева с заданным числом листьев). Бинарное ориентированное дерево с n листьями имеет высоту, не меньшую log2 n.

Эта теорема имеет одно весьма интересное приложение. Предположим, что необходимо расположить строго по возрастанию элементы конечного линейно упорядоченного множества <a1, . an>. Эту задачу называют задачей сортировки, а любой алгоритм, ее решающий, – алгоритмом сортировки. С математической точки зрения алгоритм сортировки должен найти такую перестановку <аi1, . . . , аin> элементов множества, которая была бы согласована с заданным на нем отношением ≤ линейного порядка, т.е. для любых k, l из справедливости неравенства ik < il должно следовать аik ≤ аil

v0

v1 v0 v0

v2 v3 v1 v2 v1 v2

v4 v5 v3 v4 v3 v4 v5 v6

Первоначально сортируемые элементы могут быть расположены в произвольном порядке, т.е. исходной может быть любая перестановка элементов сортируемого множества, и мы не имеем никакой априорной информации об этой перестановке. Единственный способ получить такую информацию – проводить попарные сравнения элементов аi, (относительно рассматриваемого линейного порядка) в какой-либо последовательности. Заметим, что при этом совершенно не обязательно проводить все возможные сравнения, т.е. сравнивать аi с аj для всех i ≠ j. Например, можно использовать транзитивность отношения порядка.

Все сравнения, которые в принципе могут быть проведены в процессе работы некоторого алгоритма, изображаются наглядно в виде ориентированного дерева, называемого деревом решений. На рис. 4.18 приведено дерево решений для трехэлементного множества <а, b, с>. Вершины ориентированного дерева, не являющиеся листьями, помечены проверяемыми неравенствами, а множество листьев находится во взаимно однозначном соответствии с множеством всех перестановок исходного множества.

Поскольку в результате сортировки может получиться любая перестановка исходного множества и каждой такой перестановке соответствует лист дерева решений, в общем случае количество листьев будет равно n! – количеству перестановок n-элементного множества.

Следовательно, сортируя входную последовательность, алгоритм обязательно пройдет какой-то путь от корня дерева решений к одному из листьев и, таким образом, число операций сравнения (число шагов алгоритма сортировки) будет величиной, пропорциональной высоте дерева решений, не меньшей чем log2n!, в силу теоремы 4.4. Используя для оценки факториала при больших n формулу Стирлинга

,

получаем, что дерево решений имеет высоту порядка n log2n.

Таким образом, в общем случае задачу сортировки с помощью попарных сравнений нельзя решить быстрее, чем за указанное число шагов. Безусловно, конкретный путь в дереве решений из корня к одному из листьев зависит от исходной перестановки. Например, в дереве решений, приведенном на рис. 4.18, есть два «коротких» пути длины 2, однако остальные пути имеют длину 3.

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

В заключение этой главы следует еще раз отметить, что графы являются одним из наиболее распространенных языков для представления разнообразных математических объектов и формулировки различных теоретических и прикладных задач, выходящих за пределы собственно теории графов. Трудно назвать прикладную область, где не применяется теория графов. Графы используются в математической логике и теории формальных систем, в теории алгоритмов и теоретическом программировании (для представления и анализа алгоритмов и программ), в теории языков и грамматик (для синтаксического анализа текстов). Они используются для описания и анализа как статических структур (организационных структур, транспортных сетей), так и динамических систем, в которых вершинам соответствуют состояния системы, а ориентированным ребрам – переходы из одного состояния в другое. Именно графы являются наиболее удобным средством формализованного представления конечных автоматов.

Контрольные задания

1. Сколько существует неориентированных графов с n вершинами?

2. Доказать, что сумма степеней всех вершин неориентированного графа равна удвоенному числу ребер ( это утверждение известно под названием «леммы о рукопожатиях»).

3. Установить, какие из изображенных на рис. 4.19 графов изоморфны, а какие нет

4. Найти все попарно неизоморфные графы неориентированные графы с четырьмя вершинами и тремя ребрами.

5. Установить, является ли ориентированный граф, изображенный на рис. 4.20, связным. Постройте матрицу смежности для этого графа.

6. Доказать, что связный неориентированный граф имеет эйлеров цикл тогда и только тогда, когда степень каждой его вершины четная. Рис. 4. 20

7. Инцидентор графа Р определен значениями: P(a,1,b); P(b,2,b); P(b,3,с); P(е,4,b); P(c,5,d); P(d,6,с); P(f,7,c); P(d,8, d); P(е,9,d); P(a,10,е); P(а,11,d); P(a,12,f) – которые истинны, остальные ложны. Построить граф, составить таблицы смежности и инцидентности, определить центр графа.

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

0 7 8 9 10

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

10. Вычислите количество деревьев на множестве р вершин при р = 5;10;15;20. Сколько времени потребовалось бы для подсчета деревьев с производительностью 10 6 операций/с, считая одну операцию на дерево?

11. Покажите, что для деревьев на р вершинах при р < 5 центры и центроиды (или бицентры и бицентроиды) совпадают.

Дерево (граф)

В теории графов, дерево — связный (ориентированный или неориентированный) граф, не содержащий циклов (для любой вершины есть один и только один способ добраться до любой другой вершины). Древовидная структура — тип организации, в котором каждый объект связан с хотя бы одним другим.

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

m\geq 0

  1. существует один корень дерева T
  2. остальные узлы (за исключением корня) распределены среди непересекающихся множеств T1. Tm , и каждое из множеств является деревом; деревья T1. Tm называются поддеревьями данного корня T

Содержание

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

  • Степень узла — количество поддеревьев узла
  • Концевой узел (лист) — узел со степенью нуль.
  • Узел ветвления — неконцевой узел.
  • Уровень узла определяется рекурсивным образом:
  1. Уровень корня дерева T равен нулю
  2. Уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева дерева T , содержащего данный узел.
  • Дерево с отмеченной вершиной назывется корневым деревом.
    • m -й ярус узла T — множество узлов дерева, на уровне m от корня дерева. на вершинах: u \prec v, если вершины u и v различны и вершина u лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной v .
    • корневое поддерево с корнем v — подграф \<v\>\cup\<w\mid v&amp;lt;w\>» width=»» height=»» />.</li> </ul> <h3>Двоичное дерево</h3> <p>Термин <i>двоичное дерево</i> имеет несколько значений:</p> <ul> <li><b>Двоичное (бинарное) дерево</b> (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят 3.</li> <li><b>Двоичное (бинарное) дерево</b> (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят 2. — это специальная абстрактная Структура данных используемая в программировании. На двоичном дереве основаны такие структуры данных, как Двоичное дерево поиска, Двоичная куча, Красно-чёрное дерево, АВЛ-дерево, Фибоначчиева куча и др.</li> </ul> <h3>N-арные деревья</h3> <p>N-арные деревья определяются по аналогии с двоичным деревом. Для них также есть ориентированные и неориентированные случаи, а также соответствующие абстрактные структуры данных.</p> <ul> <li><b>N-арное дерево</b> (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят N+1.</li> <li><b>N-арное дерево</b> (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят N.</li> </ul> <h3>Свойства</h3> <ul> <li>Дерево не имеет кратных ребер и петель.</li> <li>Любое дерево с <i>n</i> вершинами содержит <i>n</i> − 1 ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда <i>B</i> − <i>P</i> = 1 , здесь <i>B</i> — число вершин, <i>P</i> — число рёбер графа.</li> <li>Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственным <i>элементарным</i> путём.</li> <li>Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.</li> <li>Любое дерево является двудольным графом. Любое дерево, содержащее счётное количество вершин, является планарным графом.</li> </ul> <h3>Подсчёт деревьев</h3> <p><img decoding=

      • Число различных деревьев которые можно построить на n нумерованных вершинах, равно nn − 2 (Теорема Кэли).
      • Производящая функция
      • Производящая функция
      • При верна следующая ассимптотика

      Кодирование деревьев

      Дерево можно кодировать наборами из нулей и единиц. Рассмотрим, например, укладку дерева на плоскости. Начиная с какой либо вершины, будем двигаться по ребрам дерева, сворачивая в каждой вершине на ближайшее справа ребро и поворачивая назад в концевых вершинах дерева. Проходя по некоторому ребру, записываем 0 при движении по ребру в первый раз и 1 при движении по ребру второй раз (в обратном направлении). Если m — число ребер дерева, то через 2m шагов мы вернемся в исходную вершину, пройдя по каждому ребру дважды. Полученная при этом последовательность из 0 и 1 (код дерева) длины 2m позволяет однозначно восстанавливать не только само дерево D , но и его укладку на плоскости. Произвольному дереву соответствуют несколько таких кодов. В частности, из этого способа кодирования вытекает следующая грубая оценка на число деревьев с n вершинами:

      t_n\le T_n&amp;lt; 2^<2n>» width=»» height=»» /></p> <h3>См. также</h3> <h3>Книги</h3> <ul> <li><i>Дональд Кнут</i> Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4</li> <li><i>Оре О.</i> Теория графов. — 2-е изд.. — М.: Наука, 1980. — С. 336.</li> </ul> <p> <em>Wikimedia Foundation . 2010 .</em> </p> <h4>Полезное</h4> <h4>Смотреть что такое «Дерево (граф)» в других словарях:</h4> <p><strong>граф</strong> — Графическое изображение электрической цепи, в котором ветви электрической цепи представлены отрезками, называемыми ветвями графа, а узлы электрической цепи — точками, называемыми узлами графа. [ГОСТ Р 52002 2003] граф Основное понятие и… … Справочник технического переводчика</p><div class='code-block code-block-9' style='margin: 8px 0; clear: both;'> <!-- 9paljutemu --> <script src=

Граф — [graph] основное понятие и объект изучения теории графов, математически определяется двояко. С одной стороны как совокупность двух множеств: множества элементов x Î X и множества соответствий, отношений между этими элементами t Î T. С другой… … Экономико-математический словарь

Дерево — [tree] в теории графов, связный граф без циклов, обладающий следующими основными свойствами (которые математически эквивалентны): если за n принять число вершин (элементов графа), то он содержит ровно n 1 ребро, не имеет циклов; если добавить… … Экономико-математический словарь

дерево (в теории графов) — В теории графов ? связный граф без циклов, обладающий следующими основными свойствами (которые математически эквивалентны): если за n принять число вершин (элементов графа), то он содержит ровно n 1 ребро, не имеет циклов; если добавить ребро,… … Справочник технического переводчика

дерево решений — Граф схема, отражающая структуру задачи оптимизации многошагового процесса принятия решений. Ветви дерева отображают различные события, которые могут иметь место, а узлы (вершины) состояния, в которых возникает необходимость выбора. [ОАО РАО… … Справочник технического переводчика

дерево целей — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] дерево целей В программно целевых методах планирования и управления — граф, схема, показывающая членение общих (генеральных) целей плана или… … Справочник технического переводчика

Дерево целей — [relevance tree] в программно целевых методах планирования и управления граф, схема, показывающая членение общих (генеральных) целей плана или программы на подцели, последних на подцели следующего уровня и т.д. (дерево это связный граф,… … Экономико-математический словарь

Граф Кэли (теория групп) — Граф Кэли граф, который строится по группе с выделенной системой образующих. Назван в честь Кэли. Определение Пусть дана дискретная группа G и система образующих S. Предположим S = S − 1, то есть, для каждого . Графом Кэли группы G по системе… … Википедия

Граф Кэли — граф, который строится по группе с выделенной системой образующих. Назван в честь Кэли. Определение Пусть дана дискретная группа и система образующих . Предположим , то есть, для каждого . Графом Кэли группы … Википедия

Дерево решений — [decision tree] граф, схема, отражающая структуру задачи оптимизации многошагового процесса принятия решений. Применяется в динамическом программировании и в других областях для анализа решений, структуризации проблем. Ветви дерева отображают… … Экономико-математический словарь

Определение, формы представления графов. Матрица смежности для орграфа. Цикл Эйлера и цикл Гамильтона , страница 6

Неориентированое дерево есть связный граф без циклов, или связный граф, содержащий n вершин и n-1 ребер. Несвязный граф без циклов, отдельными компонентами связности которого являются деревья, называется лесом.

Ориентированное дерево представляет собой ориентированный граф без циклов, в котором полустепень захода каждой вершины, за исключением одной, назы2Ҁаемой корнем дерева, равна единице, а полустепень захода корня дерева равна нулю. Пример ориентированного дерева с корнем – вершиной х1 приведен на рис. 6.1.

Граф – дерево часто называют минимальным графом, имея в виду, что он содержит минимальное число ребер, оставаясь связным. Граф – дерево можно рассматривать не только как минимальный граф, но и какчасть некоторого исходного графа.

Остовным деревом графа называют дерево, содержащее все вершины графа.

Рис. 6.1. Рис.6.2. Рис. 6.3.

Ориентированное Ориентированный Остовное дерево дерево граф

Отметим, что в связном неориентированном графе всегда может быть построено остовное дерево, в то время как не всякий орграф содержит его. Например, орграф, изображенный на рис. 6.2., не содержащий остовного дерева, т.т. нулевую полустепень захода имеют не одна, а две вершины: х1 и х3. Если же убрать ориентацию дуг, то можно построить в полученном неориентированном графе, например, остовное дерево, представленное на рис. 6.3.

Очевидно, что остовных деревьев в графе может быть некоторое множество. Полный связный неориентированный граф с n вершинами содержит n n-2 остовных деревьев; другими словами, на n вершинах можно построить n n-2 деревьев

Если ребрам графа приписаны числа (веса), которые могут иметь различный физический смысл, то суммарный вес ребер, вошедших в дерево, называют “длиной” дерева.

Сколько ребер содержит лес с n вершинами и р компонентами связности?

Построить все возможные деревья для графа с четырьмя вершинами и выделить среди них не изолированные (существенные).

Доказать, что все оставшиеся деревья будут изоморфны одному из полученных в п.6.2.

Характеристические числа графов.

К характеристическим числам графа относятся:

цикломатическое число n(G), хроматическое число k (G), число внутренней устойчивости (число независимости) a(G), число внешней устойчивости (число доминирования) b(G), кликовое число.

Заметим, что характеристические ч8Ѐсла не зависят от изоморфных преобразований графа.

При рассмотрении связного неориентированого графа G(Х, А) без петель с n вершинами и m ребрами . Величину n((G)=m-n+1

называют цикломатическим числом графа[(1,2,](. Принимая во внимание, что дерево с n вершинами имеет n-1 ребро, можно сказать, что цикломатическое число равно числу ребер, которые необходимо удалить из данного графа, чтобы получить дерево.

Основное свойство цикоматического числа состоит в том, что оно равно максимальному числу независимых циклов. Циклы считаются независимыми, если в каждом из них содержится по крайней мере одно ребро, не входящее в другие циклы графа. Если граф несвязный и содержит р компонент связности, то циклическое число определяется так:

7.1. Граф G(Х, А) задан матрицей смежности А2 из упражнения 5.1.

А) Построить его геометрическое изображение.

Б) Определить цикломатическое число.

В) Указать независимые циклы.

6.1. Хроматическое число.

Неориентированный граф G(Х, А) без петель называется r – хроматическим, если его вершины могу быть раскрашены в r цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, в которое таким образом могут быть раскрашены вершины графа называется хроматическим числом графа G [1,2,4]. Обозначим его К(G).

Графы — определения, деревья, хранение и поиск в глубину

Графом \(G\) называется пара множеств \(G = (V, E\) , где \(V(G)\) — непустое конечное множество элементов, называемых вершинами графа, а \(E\) — множество пар элементов из \(V\) (необязательно различных), называемых ребрами графа. \(E = \<(u , v)\ | u, v \in V\>\) — множество ребер графа \(G\) , состоящее из пар вершин \((u, v)\) . Ребро \((u, v)\) соединяет вершины \(u\) и \(v\) .

Граф — это набор вершин (точек) и соединяющих их отрезков (рёбер).

Примеры графаПримеры графа

Две вершины, соединенные ребром, называют смежными вершинами. Обычно в задачах \(N\) — количество вершин, а \(M\) — ребер. Количество ребер, исходящее из вершины называют степенью вершины \(d(v)\) . Для вершины \(a\) ребро \((a, b)\) называется инцидентным ей. На рисунке ниже вершине 8 инцидентно только ребро (4, 8), а вершине 10 ребра (2, 10) и (5, 10).

Теоретическое задание

Назовите степень 1-ой и 6-ой вершины и какие ребра инциденты им.

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

Простой граф не содержит петель и кратных ребер. Если не сказано ничего про наличие петель и кратных ребер, мы будем всегда считать, что граф простой.

Теоретическое задание

Сколько может быть рёбер в простом графе в \(N\) вершинами?

Теоретическое задание

Найдите цикл размера 4 и петлю в этом непростом графе.

Также часто рассматривают ориентированные графы — это графы, у которых ребра имеют направление, а иначе граф – неориентированный.

Хранение графа в программе

Чаще всего в задачах по программмированию вершины графа — это числа от \(0\) до \(N-1\) , чтобы удобно было обращаться к ним как к индексам в разных массивах.

Также чаще всего вам дают считать граф как просто список всех рёбер в нем (но не всегда, конечно). Как оптимально считать и сохранить граф? Есть 3 способа.

Для графа существуют несколько основных способов хранения:

  1. Матрица смежности. Давайте хранить двумерную матрицу \(A_\) , где для данного графа G верно, что если \(A_\) = 1, то две вершины \(i\) и \(j\) являются смежными, иначе вершины \(i\) и \(j\) смежными не являются.

Мы храним для каждой из \(N\) вершин информацию, есть ли ребро в другие вершины, то есть суммарно мы храним \(N^2\) ячеек, а следовательно асимптотика по памяти — \(O(N^2)\) .

  1. Список смежности. Давайте для каждой из \(N\) вершин хранить все смежные с ней, для этого нам потребуется любая динамическая структура, например vector в с++.

Здесь асимптотика по памяти и времени считывания — \(O(N + M)\) , так как мы храним для каждой вершины, куда есть ребра, то есть \(2 M\) ребер, а также суммарно \(N\) векторов.

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

  1. Список рёбер. Иногда граф явно вообще не требуется, а хватает хранить просто список ребер, который нам дают на вход.

Заметьте, что все эти способы обощаются на случай ориентированных графов — при этом матрица смежности становится неориетированной: если есть ребро из вершины \(i\) в вершину \(j\) , то сделаем \(A_ = 1\) , а \(A_ = 0\) , если только нет обратного ребра тоже. А в списке смежности в ориентированном случае при считывании ребра \((u, v)\) будем добавлять только \(v\) в список соседей \(u\) , но не наоборот.

Практическое задание

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

Деревья

Дерево — это связный неориентированный граф без циклов.

Пример дерева

  1. У дерева с хотя бы 2 вершинами всегда есть висячая вершина — вершина степени 1.

Действительно, если начать из любой вершины идти по непосещенным ранее вершинам, то в какой-то момент мы прекратим это делать, ведь граф конечный. При этом если из этой вершины не может быть ребер в непосещенные вершины — ведь тогда прекращать рано, и не может быть ребер в посещенные ребра (помимо предыдущей) — ведь тогда есть цикл. А значит, есть ребро только в предыдущую вершину, значит степень равна 1.

  1. У дерева с хотя бы 2 вершинами всегда есть две висячие вершины.

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

  1. У дерева с \(N\) вершинами всегда ровно \(N-1\) ребро.

Давайте отрезать от дерева его висячие вершины — при этом число вершин уменьшится на один, число ребер тоже уменьшится на один, а граф останется деревом. Раз граф остается деревом, у него все время будет висячая вершина, пока \(N > 1\) . В какой-то момент останется только одна вершина и ноль ребер. Раз мы отрезали столько же вершин, сколько ребер, и получили 1 вершину и 0 ребер, значит изначально вершин было ровно на одну больше.

  1. Между любыми двумя вершинами в дереве есть ровно один простой путь.

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

  1. Дерево — это минимальный по числу рёбер связный граф на \(N\) вершинах.

Действительно, если есть связный граф, в котором меньше, чем \(N-1\) ребро, то давайте уберем из его цикла ребро. Граф при этом остается связным, а число ребер уменьшается. Давайте повторять это, пока в какой-то момент циклов в графе не будет, а значит осталось дерево. Но мы уже доказали, что в дереве \(N-1\) ребро, это противоречие, ведь у нас сначала было меньше ребер, а мы еще и удалили сколько-то.

DFS (Алгоритм обхода графа в глубину)

Обход в глубину — простой, но многофункциональный алгоритм обхода графа по ребрам. Самое главное, что он может — это проверить, какие вершины достижимы из данной.

При обходе графа мы используем вспомогательный массив used, в котором храним 1, если вершина была посещена или 0 иначе. В начале мы считаем, что все вершины не использовались, затем мы выбираем одну вершину, помечаем ее посещенной и запускаемся рекурсивно из всех ее соседей, тогда мы посетим все вершины, которые достижимы из данной, если же остались вершины с used = 0 значит они недостижимы.

Красивая визуализация: https://visualgo.net/en/dfsbfs

Давайте оценим сложность алгоритма. Так как мы проверяем, что вершина еще не использовалась, то всего мы пройдет каждую вершину 1 раз, но при этом и ребро между двумя вершинами, мы рассматриваем только когда рассматривается один конец, то есть мы просмотрим каждое ребро не более одного раза, суммарно получаем оценку \(O(N + M)\) .

Практическое задание

Задачи 3-5 в контесте.

Поиск компонент связности графа

Путем в графе называется последовательность вершин \(v_i \in ��\) , \(i = 1. k\) таких, что две последовательные вершины в пути соединены ребром, \(k\) — длина пути. Граф называется связным, если для любых двух его вершин существует путь между ними. Граф всегда можно разбить на непересекающиеся связные подмножества (возможно одно), между которыми рёбер нет, они называются компонентами связности.

Поиск в глубину dfs будет обходить ту компоненту связности, из вершины которой, он был вызван. Поэтому для поиска компонент связности можно каждый раз вызываться из любой непосещенной вершины и тогда в результате мы посетим все вершины, а следовательно и найдем все компоненты связности.

Практическое задание

На данную тему задачи 6 и 10 в контесте.

Остовное дерево

Остованым деревом в связном графе называется любое подмножество ребер, которое является деревом на всех вершинах. То есть любой способ выкинуть несколько ребер так, чтобы осталось дерево на N вершинах и N-1 ребро выделяет в графе остовное дерево.

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

Практическое задание

7 задача в контесте на выделение остовного дерева в графе.

Раскраска графа в два цвета

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

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

Практическое задание

8 задача в контесте на раскраску графа в два цвета

Поиск циклов в графе

Циклом в графе \(G\) называется ненулевой путь, ведущий из вершины \(v\) в саму себя. Граф называют ацикличным, если в нем нет циклов.

В обычном dfs мы используем два цвета (1 — вершина посещена, 0 — не посещена), если же нам надо найти цикл, то давайте хранить 3 цвета:

  • 0 — вершина не просмотрена
  • 1 — мы входили DFS-ом в эту вершину, но еще не вышли (а значит из нее есть путь до текущей),
  • 2 — мы входили DFS-ом в эту вершину

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

В неориентированном графе также надо дополнительно рассмотреть случай, когда мы идем в предка — это циклом все-таки не считается, для этого нужно отдельно добавить второй аргумент prev, где хранить предыдущую вершину в dfs, и никогда не идти в неё.

Похожие публикации:
  1. Как изменить ключ в словаре питон
  2. Как поставить камеру заднего вида на хендай солярис
  3. Как установить озон на телефон
  4. Какой из названных здесь двигателей обладает наибольшим кпд

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *