Сколько ребер и вершин в данном графе

Графы. Основные определения. Соотношения между количеством ребер и количеством вершин.

Простой граф – не имеет петель, а также если он не имеет рёбер с одинаковой упорядоченной парой вершин.

простой граф

Смежность вершин для неориентированного – вершина Y смежна с вершиной X, если в графе существует ребро соединяющее вершину Y с вершиной X.

Смежность вершин для ориентированного – вершина Y смежна с вершиной X, если в ориентированном графе существует ребро исходящее из вершины Х и входящее в вершину Y.

вершина Y смежная, Х несменная

матрица смежности

Ориентирований граф матрица смежности, из 1 в 2

список смежности

турнир

Ответ:

Полный граф – каждая вершина соеденена с каждой вершиной

Однородный граф – это граф, степени всех вершин которого

Изоморфизм графов. Примеры.

кол-во неориентированных простых графов

кол-во ориентированных простых графов

Изоморфизм простых графов – графы G1 и G2 изоморфны если существует отображение ФИ из множества вершин V1 в V2 которые являются взаимно однозначными и сохраняют отношение смежности (в графе G1 имеется ребро х y = Е(число рёбер) принадлежащие множеству рёбер графа G1 тогда в графе G2 обязано быть ребро фи от х и фи от у, они должны принадлежать множеству рёбер графа G2 и наоборот)

графы G1 и G2 изоморфны

Пути, цепи, циклы.

маршрут

путь (цепь) – рёбра не могут повторяться

простой путь – рёбра и вершины не могут повторяться

Элементарная дуга – это цепь, в которой каждая вершина встречается только один раз

В простом графе можно описывать путь только вершинами

Замкнутый маршрут – в котором начальные и конечные вершины совпадают

Замкнутый путь – ребра не повторяются

Цикл – маршрут у которого начальные и конечные вершины совпадают и рёбра, и вершины не повторяются.

Обхват – длина минимального цикла, если в графе циклов нет – обхват = бесконечности

Обхват графа больше 3 – граф свободный от треугольников

Изолированная вершина циклом не является

Связность графов.

Связные вершины – если вершины соединены хотя бы одним путём

2 и 4 связаны, 1 и 7 не связаны

Если вершина 1 связана с вершиной 2, вершина 2 связана с 3, то 1 связан с 3

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

Пусть G есть граф, построенный на вершинах 1,2…,15, в котором вершины ii и jj смежны тогда и только тогда, когда их наибольший общий делитель больше единицы. Сколько компонент связности имеет такой граф?

Компонента связности –

Связанный ориентированный граф – если существует путь из вершины Х в Y, так из Y в Х.

1 и 4 сазаны между собой путь из 1 в 4 =124 путь из 4 в 1 = 41, вершины 1 и 3 не связаны

компоненты сильной связности

Сильно связанный граф – Если граф состоит из единственной такой компоненты

Какое максимальное количество ребер может быть в простом слабо связном ориентированном графе на 10 вершинах, не являющимся сильно связным? Ответ: Каждая вершина из десяти должна соединяться с 9 другими. Но она не может соединяться сама с собой, поэтому мы умножаем 9 не на 10 (по количеству вершин), а так как она соединяется со всеми, кроме себя (простой граф), на девять. 9*9 = 81

Вершинное разделяющие множество (вершинный разрез) – множество вершин после удаление которых граф разваливается на несвязные компоненты.

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

связность графов

Вершино k связный граф – если граф построен на вершине и при удалении любых вершин в количестве меньше k, граф остаётся связным

Вершинная связность – граф G имеет вершинную связность = k если этот граф является ещё вершино k связным, однако вершино k+1 уже не является

Реберная связность – размер минимального рёберно разделяющего множества для этого графа, тоесть какое минимальное число ребер нужно удалить чтобы граф распался на 2 компоненты связности

реберная связность

Мост – ребро удаление которого приводит к разделению на 2 компоненты связности

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

Реберно k связный граф – если удаление любых ребер такого графа в количестве меньше чем k не приведёт к потере связности этого графа

Реберная связность графа – максимально возможное значение k, что граф ещё является реберно k связным, но реберно k+1 связным уже не является.

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

Разрез графа – это минимальное количество ребер, которые необходимо удалить, чтобы граф перестал быть связным.

Знакомство с ГРАФАМИ

Информация для учителей, работающих в матемаческих кружках.

Просмотр содержимого документа
«Знакомство с ГРАФАМИ»

Знакомьтесь: граф

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

Пример 1. В деревне 9 домов. Известно, что у Петра соседи Иван и Антон, Максим сосед Ивану и Сергею, Виктор – Диме и Никите, Евгений – сосед Никиты, а больше соседей в этой деревне нет (соседними считаются дворы, у которых есть общий участок забора). Может ли Пётр огородами пробраться к Никите за яблоками?

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

Пример 2. В трёх вершинах пятиугольника расположили по фишке (см. рис. 2а). Разрешается двигать их по диагонали в свободную вершину. Можно ли такими действиями добиться того, чтобы одна из фишек вернулась на первоначальное место, а две другие поменялись местами (см. 2б)?

Решение. Заметим, что диагонали пятиугольника образуют один замкнутый цикл. Представим себе, что фишки – это пуговицы, нанизанные на нитку (см. рис. 2в). Ясно, что если двигать пуговицы по нитке, то поменять местами две пуговицы нельзя. Поэтому переставить фишки требуемым образом невозможно.

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

Определение 1. Графом называется конечное множество точек, некоторые из которых соединены линями. Точки называются вершинами графа, а соединяющие линии – рёбрами.

Примерами графов могут служить: любая карта дорог, схема метро, электросхема, чертёж прямоугольника и т.д.

Кстати, с дворянским титулом «граф» их связывает общее происхождение от латинского слова «графио» — пишу.

Замечания:

1. Каждое ребро соединяет ровно две вершины.

2. Вершины, из которых не исходит ни одного ребра, называются изолированными.

3. Графы, у которых вершина соединена сама с собой, и графы, в которых пара вершин соединена несколькими рёбрами, мы пока не рассматриваем, хотя иногда такие графы также бывают нужны.

4. Полезно представить граф как набор пуговиц, некоторые из которых соединены нитями. При этом, где именно расположены пуговицы, и как проходят нити – не важно: граф от этого не меняется, важно лишь то, какие пары пуговиц (вершины) соединены нитями.

Такие одинаковые, но, быть может, по-разному нарисованные графы принято называть изоморфными. На рисунках 3а и 3б изображены изоморфные графы.

Определение 2. Степенью (или порядком) вершины называется количество рёбер, исходящих из этой вершины. Вершина называется чётной, если из неё выходит чётное число рёбер, и нечётной, если из неё выходит нечётное число рёбер.

Так, например, в графе, изображенном на рисунке 3, первая и пятая вершины имеют степень 1, вторая вершина – степень 4, третья и четвертая вершины – степень 2.

Пример 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединён с пятью другими?

Решение. Предположим, что это возможно. Рассмотрим граф, вершины которого соответствуют телефонам, а рёбра – соединяющим их проводам. В этом графе 15 вершин, степень каждой из которых равна пяти. Подсчитаем количество рёбер в этом графе. Для этого сначала просуммируем степени всех его вершин. Ясно, что при таком подсчете каждое ребро учтено дважды (см. замечание 1). Поэтому число рёбер графа равно . Но это число нецелое, а значит такого графа не существует, следовательно соединить телефоны требуемым образом невозможно.

Пример 4. На концерте каждую песню исполняли двое артистов, и никакая пара не выступала вместе более одного раза. Всего было 12 артистов, каждый выступил по 5 раз. Сколько было песен?

Решение. Рассмотрим граф, вершинами которого являются выступавшие артисты. Соединим пару артистов ребром, если они вместе пели. Получим граф с 12 вершинами степени 5, каждой песне соответствует ребро. Аналогично предыдущему примеру, в графе рёбер, то есть было 30 песен.

Обратите внимание на то, что рёбра считать легче, чем песни или провода. Рёбра легко изображать, именно это свойство (наглядность) обусловило столь широкое распространение графов.

Замечания:

5. Чтобы подсчитать число рёбер графа нужно просуммировать степени вершин и полученный результат разделить на два.

6. Сумма степеней всех вершин графа должна быть чётной (иначе её нельзя было бы разделить на два нацело).

Пример 5. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 – по 4 друга, а 10 – по 5 друзей?

Решение. Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 – степень 4, 10 – степень 5. Однако сумма степеней вершин такого графа нечётна (проверьте), что противоречит замечанию 6. Не может.

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

Определение 4. Циклом называется путь, у которого начало и конец совпадают.

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

Пример 6. Сколько рёбер в полном графе с пятью вершинами?

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

Определение 7. Граф называется связным, если для любой его вершины найдется путь, связывающий её с любой другой вершиной этого графа.

На рис. 1 мы видим, что граф несвязен, на рис. 2, 3, 4 изображены связные графы, кроме того они имеют циклы.

Замечания:

7. Несвязный граф состоит из нескольких «кусков». Эти «куски» называются компонентами связности графа. (Например, на рис. 1 две компоненты связанности, то есть изображён один граф соседства, состоящий из двух «кусков»).

8. Связный граф имеет одну компоненту связности.

9. В каждой компоненте сумма степеней вершин чётна (для связного графа очевидно, а для несвязного подумайте почему).

Пример 7. В тридевятом царстве лишь один вид транспорта – ковёр-самолёт. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных – по 20. Докажите, что из столицы можно долететь в город Дальний (возможно с пересадками).

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

Докажем методом «от противного». Пусть в компоненте связности города Дальнего нет. Тогда в ней из одной вершины выходит 21 ребро, а из всех остальных – по 20. То есть сумма степеней вершин нечётна, что противоречит замечанию 9. Получили противоречие, значит наше предположение неверно, то есть город Дальний входит в эту же компоненту связности.

Пример 8. Можно ли нарисовать графы, изображенные на рис. 5а и на рис. 5б, не отрывая карандаш от бумаги и проводя каждое ребро один раз?

Решение. а) Можно. Например, последовательность вершин может быть такой: 1-2-3-1-4-2-5-3-4.

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

Возможно, вам знакома аналогичная задача про открытый конверт (или домик).

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

Замечание:

10. Эйлеров граф должен иметь не более двух нечётных вершин.

Впервые такие графы были исследованы великим математиком Леонардом Эйлером в 1736 году в связи со знаменитой задачей о Кёнигсбергских мостах.

Пример 9. Схема мостов Кёнигсберга изображена на рис. 6. Можно ли совершить прогулку, пройдя по каждому мосту ровно один раз?

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

Пример 10. В углах шахматной доски 3 3 стоят 4 коня: 2 белых (в соседних углах) и два чёрных (см. рис. 7а). Можно ли за несколько ходов (по шахматным правилам) поставить коней так, чтобы во всех соседних углах стояли кони разного цвета?

Решение. Отметим центры клеток доски и соединим отрезками пары отмеченных точек, если из одной в другую можно перейти шагом коня (конь ходит буквой Г). Мы получили граф (см. рис. 7б). В нём есть изолированная вершина (см. замечание 2), это вершина 5. Попробуйте обойти все остальные вершины графа и вернуться в исходную вершину. У вас должно получиться, ведь рёбра и все вершины, кроме вершины 5, образуют эйлеров граф, содержащий цикл. Перемещение коней по доске соответствует движению по рёбрам этого цикла. Для графа на рис. 7б изображен изоморфный граф (см. рис. 7в и замечание 4). Ясно, что при движении по циклу нельзя изменить порядок следования коней.

Список литературы (советуем почитать):

1. Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки: пособие для внеклассной работы. Глава 6. Графы–1. Киров: АСА, 1994 г.

2. Гуровиц В.М., Ховрина В.В. Графы. Москва: МЦНМО, 2012 г.

3. Каннель-Белов А.Я., Ковальджи А.К. Как решают нестандартные задачи. Часть I. Идеи и методы решения задач: Графы. Москва: МЦНМО, 2008 г.

4. Савин А. Графы. Журнал «Квант» № 6, 1994 г.

5. Фосс В. Элементы теории графов. Журнал «Квант» № 8, 1973 г.

8.1. В стране Цифра есть девять городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Два города соединены авиалинией только в том случае, если двузначное число, составленное из цифр-названий этих городов, делиться на 3. Можно ли добраться из города 1 в город 9?

8.2. В фирме 50 компьютеров, некоторые пары компьютеров должны быть соединены кабелями. От каждого компьютера должно отходить по 8 кабелей. Сколько понадобиться кабелей?

8.3. Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?

8.4. В графе с восьмью вершинами степень каждой вершины равна двум. Нарисуйте все такие графы (не забывайте, что графы могут быть несвязными).

8.5. Нарисуйте одним росчерком, не проведя ни одной линии дважды, фигуры, изображённые на рис. 8, (пронумеруйте последовательность проводимых рёбер).

8.6. Доска имеет форму креста, который получится, если из квадратной доски 4 4 выкинуть угловые клетки. Можно ли обойти её ходом шахматного коня и вернуться на исходное поле, побывав на всех полях ровно по разу?

Решение простых комбинаторных задач с помощью графов

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

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

Граф из 6 вершин и 7 ребёр.

Сколько различных трёхзначных чисел можно написать с помощью цифр 0 и 1?

Получаем 4 числа: 100,101,110 и 111

Полный граф в комбинаторике

Полный граф – это граф со всеми возможными ребрами.

С помощью полного графа удобно решать задачи полного перебора про «всех со всеми».

5 школьных команд по волейболу сыграли серию игр. Каждая команда провела с другими командами по одному матчу. Сколько всего матчей было сыграно?

Изобразим полный граф с 5-ю вершинами и посчитаем количество ребёр.

N = 10. Значит, было сыграно 10 матчей.

Граф-дерево

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

Граф-дерево с 9 узлами и 8 ребрами.

Из каждого узла выходит не более 2 ребер.

Такое дерево называют бинарным.

С помощью дерева удобно составлять упорядоченные комбинации элементов.

На столе стоит три стакана сока – апельсиновый, виноградный и яблочный. Можно взять только два стакана. Сколько есть возможных вариантов и каких?

По правилу произведения число возможных вариантов: $3 \cdot 2 = 6$. Поскольку, порядок выбора неважен, остаётся $\frac<6> <2>= 3$ варианта. Построим граф:

3 варианта: 1) апельсиновый + яблочный, 2)апельсиновый + виноградный, 3) виноградный + яблочный.

Примеры

Пример 1. Вася, Петя, Коля и Толя хотят быть дежурными в столовой. Но можно выбрать только троих. Сколько вариантов выбора есть?

Построим полный граф.

Каждая тройка ребят соответствует треугольнику в этом графе.

Например, Вася образует три треугольника с оставшимися тремя ребятами:

$ \frac<3\cdot 2> <2>= 3$ — ВПК, ВТК и ВТП

Без Васи есть только один треугольник – ПКТ

Общее количество треугольников 3+1=4

Ответ: 4 варианта

Пример 2. Под рукой есть 6 видов овощей (капуста, морковь, лук, помидоры, огурцы и перец). Для салата нужно 3 вида овощей. Сколько всего различных салатов можно приготовить?

Построим полный граф.

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

Например, капуста образует треугольники с оставшимися 5 овощами. Таких треугольников $ \frac<5\cdot 4> <2>= 10$, где деление на 2 учитывает повторение ребра в каждой паре («лук-огурец» = «огурец-лук» и т.д.).

Количество треугольников, в которые не входит капуста: $ \frac<4\cdot 3> <2>= 6$

Количество треугольников, в которые не входят капуста и морковь: $ \frac<3\cdot 2> <2>= 3$

Количество треугольников, в которые не входят капуста, морковь и перец: $ \frac<2\cdot 1> <2>= 1$

Итого 10+6+3+1 = 20 различных треугольников.

Ответ: 20 салатов

Примечание: по расчетной формуле $C_6^3 = \frac<6\cdot 5 \cdot 4> <1\cdot 2 \cdot 3>= 20$ — ответ правильный.

Пример 3*. Сколько существует способов занять 1,2 и 3 места на чемпионате, в котором участвуют 11 команд? Решите задачу с помощью полного графа.

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

По аналогии с примерами 1 и 2, общее количество треугольников:

Так, как порядок мест важен, в каждом треугольнике $– 3\cdot2 = 6$ вариантов распределения медалей.

По правилу произведения: $6\cdot165 = 990$ — общее количество способов.

Ответ: 990 вариантов

Примечание: по расчетной формуле $A_3^ <11>= 11\cdot10\cdot9 = 990 $ — ответ правильный.

Пример 4. В столовой есть на выбор

• два первых блюда: щи (Щ) и борщ (Б)
• три вторых блюда: мясо (М), рыба (Р), блинчики с творогом (Т)
• два напитка: компот (К) и сок (С)

Сколько вариантов обедов можно составить из этих блюд и каких?

По правилу произведения общее количество вариантов обедов: $2\cdot3\cdot2 = 12$

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

Графом \(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, и никогда не идти в неё.