Сколько ребер в дереве в котором 7 вершин

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

Графом \(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 в с++.

// как сделать список по матрице vector > g(n); for (int i = 0; i < n; ++i)< for (int j = 0;j < n;++j)< cin >> a; if (a) g[i].push_back(j); > > // список по списку ребер cin >> n >> m; vector > g(n); for (int i = 0; i < m; ++i)< cin >> v1 >> v2; g[v1].push_back(v2); g[v2].push_back(v1); >

Здесь асимптотика по памяти и времени считывания — \(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

void dfs (int v) < used[v] = 1; for (auto to : g[v]) < if (!used[to]) < dfs(to); >> >

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

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

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

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

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

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

for (int i = 0; i < n; ++i)< if (!used[i]) < amount++; dfs(i); >>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

void dfs (int v) < used[v] = 1; for (size_t i=0; i < g[v].size(); ++i) < int to = g[v][i]; if (used[to] == 0)< p[to] = v; dfs (to); >else if (used[to] == 1 && to != p[v]) < cycle = true; >> used[v] = 2; >

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

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

9 задача в контесте на поиск цикла в графе.

Деревья — Теория графов

В этом уроке мы изучим еще один вид графов — древовидные. Именно этот вид графов активно используется в программировании — он связан с алгоритмами сортировки и поиска.

Деревья

Деревья — это связные графы без циклов. Их часто применяют в математике и информатике. Вот так они выглядят:

Как видно из примера, у деревьев определенная древовидная ветвистость, откуда они и получили свое название.

Благодаря связности и отсутствию циклов у деревьев есть ряд свойств:

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

Листья и индукция

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

вершинами можно перемещаться с шагом

Для этого нам понадобится лист в дереве — вершина, которая находится на концах каждого дерева.

Разберем следующую теорему: у каждого дерева с хотя бы двумя вершинами есть хотя бы два листа. Докажем это утверждение.

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

в дереве. Их единственные соседи — вершины, которые располагаются перед ними на пути.

Обсудим, почему это работает именно так:

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

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

Дерево, эквивалентные определения

Для графа [math]G[/math] эквивалентны следующие утверждения:

1. [math]G[/math] — дерево.
2. Любые две вершины графа [math]G[/math] соединены единственным простым путем.
3. [math]G[/math] — связен и [math] p = q + 1 [/math] , где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер.
4. [math]G[/math] — ацикличен и [math] p = q + 1 [/math] , где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер.
5. [math]G[/math] — ацикличен и при добавлении любого ребра для несмежных вершин появляется один простой цикл.
6. [math]G[/math] — связный граф, отличный от [math] K_p [/math] для [math] p \gt 3 [/math] , а также при добавлении любого ребра для несмежных вершин появляется один простой цикл.
7. [math]G[/math] — граф, отличный от [math] K_3 \cup K_1 [/math] и [math] K_3 \cup K_2 [/math] , а также [math] p = q + 1 [/math] , где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер, и при добавлении любого ребра для несмежных вершин появляется один простой цикл.

Доказательство эквивалентности

[math] 1 \Rightarrow 2 [/math]

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

[math] 2 \Rightarrow 3 [/math]

Очевидно, что граф связен. Докажем по индукции, соотношение [math]p = q + 1[/math] . Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше [math]p[/math] вершин. Если же граф [math]G[/math] имеет [math]p[/math] вершин, то удаление из него любого ребра делает граф [math] G [/math] несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, [math] p = q + 1 [/math] .

[math] 3 \Rightarrow 4 [/math]

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

[math] 4 \Rightarrow 5 [/math]

[math]G[/math] — ациклический граф, значит каждая компонента связности графа является деревом. Так как в каждой из них вершин на единицу больше чем ребер, то [math] p = q + k [/math] , где [math]k[/math] — число компонент связности. Поскольку [math] p = q + k [/math] , то [math] k = 1 [/math] , а значит [math]G[/math] — связен. Таким образом наш граф — дерево, у которого между любой парой вершин есть единственный простой путь. Очевидно, при добавлении ребра появится второй путь между парой вершин, то есть мы получим цикл.

[math] 5 \Rightarrow 6 [/math]

Поскольку [math] K_p [/math] для [math] p \gt 3 [/math] содержит простой цикл, то [math]G[/math] не может им являться. [math]G[/math] связен, так как в ином случае можно было бы добавить ребро так, что граф остался бы ациклическим.

[math] 6 \Rightarrow 7 [/math]

Докажем, что любые две вершины графа соединены единственной простой цепью, а тогда поскольку [math] 2 \Rightarrow 3 [/math] , получим [math] p = q + 1 [/math] . Любые две вершины соединены простой цепью, так как [math]G[/math] — связен. Если две вершины соединены более чем одной простой цепью, то мы получим цикл. Причем он должен являться [math] K_3 [/math] , так как иначе добавив ребро, соединяющее две вершины цикла, мы получим более одного простого цикла, что противоречит условию. [math] K_3 [/math] является собственным подграфом [math]G[/math] , поскольку [math]G[/math] не является [math] K_p [/math] для [math] p \gt 3 [/math] . [math]G[/math] — связен, а значит есть вершина смежная с [math] K_3 [/math] . Очевидно, можно добавить ребро так, что образуется более одного простого цикла. Если нельзя добавить ребра так, чтобы не нарушалось исходное условие, то граф [math]G[/math] является [math]K_p[/math] для [math] p \gt 3 [/math] , и мы получаем противоречие с исходным условием. Значит, любые две вершины графа соединены единственной простой цепью, что и требовалось.

[math] 7 \Rightarrow 1 [/math]

Если [math]G[/math] имеет простой цикл, то он является отдельной компонентой [math]K_3[/math] по ранее доказанному. Все остальные компоненты должны быть деревьями, но для выполнения соотношения [math] p = q + 1 [/math] должно быть не более одной компоненты отличной от [math]K_3[/math] , так как в [math]K_3[/math] [math] p = q = 3 [/math] . Если это дерево содержит простой путь длины 2, то в [math]G[/math] можно добавить ребро так, что образуются два простых цикла. Следовательно, этим деревом является [math]K_1[/math] или [math]K_2[/math] . Значит [math]G[/math] является [math]K_3 \cup K_1[/math] или [math]K_3 \cup K_2[/math] , которые мы исключили из рассмотрения. Значит наш граф ацикличен. Если [math]G[/math] ациклический и [math] p = q + 1 [/math] , то из [math] 4 \Rightarrow 5 [/math] и [math] 5 \Rightarrow 6 [/math] верно, что [math]G[/math] — связен. В итоге получаем, что [math]G[/math] является деревом по определению.

См. также

• Алгоритмы на деревьях
• Двоичное дерево поиска

Источники информации

• Харари Ф. Теория графов. /пер. с англ. — изд. 2-е — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
• Википедия — дерево(теория графов)

• Алгоритмы и структуры данных
• Основные определения теории графов

Сколько ребер в дереве в котором 7 вершин

Задача 6:

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

Решение:

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

Задача 7:

Докажите, что в дереве любые две вершины соединены ровно одним простым путем.

Решение:

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

1) выбрать первую точку, в которой пути расходятся

2) за выбранной точкой на пути 1 найти первую точку, принадлежащую также и пути 2

Теперь участки первого и второго пути между точками A и B образуют простой цикл.

Задача 8:

Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется висячей).

Решение:

Рассмотрим произвольную вершину дерева и пойдем по любому выходящему из нее ребру в другую вершину. Если из новой вершины больше ребер не выходит, то мы остаемся в ней, а в противном случае идем по любому другому ребру дальше. Понятно, что в этом путешествии мы никогда не сможем попасть в вершину, в которой уже побывали: это означало бы наличие цикла. Так как у графа конечное число вершин, то наше путешествие обязательно должно закончиться. Но закончиться оно может только в висячей вершине!

Задача 9:

В графе все вершины имеют степень 3. Докажите, что в нем есть цикл.

Решение:

Рассмотрим произвольную компоненту связности этого графа. Она не является деревом, так как в ней нет висячей вершины. Значит, в ней есть цикл.

Задача 10:

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

Решение:

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

Задача 11:

В стране Древляндия 101 город, и некоторые из них соединены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог?

Решение:

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

Задача 12:

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

Решение:

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

Задача 13:

Волейбольная сетка имеет вид прямоугольника размером 50 × 600 клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски?

Решение:

Будем рассматривать волейбольную сетку как граф, вершинами которого являются узлы сетки, а ребрами – веревочки. В этом графе нужно удалить как можно больше ребер так, чтобы он остался связным. Будем убирать ребра по очереди до тех пор, пока это возможно. Заметим, что если в графе есть цикл, то возможно удаление любого ребра этого цикла. Связный граф, не имеющий циклов, является деревом. Поэтому, только получив дерево, мы не сможем убрать ни одного ребра. Подсчитаем число ребер в нашем графе в этот момент. Количество вершин осталось тем же – 51 • 601 = 30651. Число ребер в дереве на 1 меньше числа вершин и, следовательно, в нашем дереве будет 30650 ребер. Сначала же их было 601 • 50 + 600 • 51 = 60650. Таким образом, можно удалить 30000 ребер, то есть у волейбольной сетки можно перерезать 30000 веревочек (но не более!).

Задача 14:

В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый?

Решение:

Ответ: 30 • 29/2 – 29 = 406.

Задача 15:

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

Решение:

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

Задача 16:

В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от любого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать в каждом городе, совершив не более а) 198 перелетов; б) 196 перелетов.

Решение:

а), б) Рассмотрите «максимальное» дерево и выберите путь, соединяющий две висячие вершины.