Что такое висячие вершины графа

7

Теория графов. Термины и определения в картинках

В этой статье мы познакомимся с основными терминами и определениями Теории графов. Каждый термин схематично показан на картинках.

Самый объёмный модуль на курсе «Алгоритмы и структуры данных» посвящён теории графов.

Граф — это топологичекая модель, которая состоит из множества вершин и множества соединяющих их рёбер. При этом значение имеет только сам факт, какая вершина с какой соединена.

Например, граф на рисунке состоит из 8 вершин и 8 рёбер.

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

В этой статье мы познакомимся с основными терминами и определениями теории графов. На курсе “Алгоритмы и Структуры данных” в компании Отус “Теория графов” изучается в самом объёмном модуле из 6 вебинаров, где мы изучаем десяток самых популярных алгоритмов.

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

Ребро — неупорядоченная пара двух вершин, которые связаны друг с другом. Эти вершины называются концевыми точками или концами ребра. При этом важен сам факт наличия связи, каким именно образом осуществляется эта связь и по какой дороге — не имеет значения; однако рёбра может быть присвоен “вес”, что позволит говорить о “нагруженном графе” и решать задачи оптимизации.

Инцидентность — вершина и ребро называются инцидентными, если вершина является для этого ребра концевой. Обратите внимание, что термин “инцидентность” применим только к вершине и ребру.

Смежность вершин — две вершины называются смежными, если они инцидентны одному ребру.

Смежность рёбер — два ребра называются смежными, если они инцедентны одной вершине.

Говоря проще — две вершины смежные, если они соединены ребром, два ребра смежные — если они соединены вершиной.

Петля — ребро, инцидентное одной вершине. Ребро, которое замыкается на одной вершине.

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

Кратные рёбра — рёбра, имеющие одинаковые концевые вершины, по другому их называют ещё параллельными.

Мультиграф — граф с кратными рёбрами.

Псевдомультиграф — граф с петлями и кратными рёбрами.

Степень вершины — это количество рёбер, инцидентных указанной вершине. По-другому — количество рёбер, исходящих из вершины. Петля увеливает степень вершины на 2.

Изолированная вершина — вершина с нулевой степенью.

Висячая вершина — вершина со степенью 1.

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

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

Полный граф — это граф, в котором каждые две вершины соединены одним ребром.

Сколько рёбер в полном графе? Это известная задача о рукопожатиях: собралось N человек (вершин) и каждый с каждым обменялся рукопожатием (ребро), сколько всего было рукопожатий? Вычисляется как сумма чисел от 1 до N — каждый новый участник должен пожать руку всем присутствующим, вычисляется по формуле: N * (N — 1) / 2.

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

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

Планарный граф. Если граф можно разместить на плоскости таким образом, чтобы рёбра не пересекались, то он называется “планарным графом” или “плоским графом”.

Если это невозможно сделать, то граф называется “непланарным”.

Минимальные непланарные графы — это полный граф К5 из 5 вершин и полный двудольный граф К3,3 из 3+3 вершин (известная задача о 3 соседях и 3 колодцах). Если какой-либо граф в качестве подграфа содержит К5 или К3,3, то он является непланарным.

Путь или Маршрут — это последовательность смежных рёбер. Обычно путь задаётся перечислением вершин, по которым он пролегает.

Длина пути — количество рёбер в пути.

Цепь — маршрут без повторяющихся рёбер.

Простая цепь — цепь без повторяющихся вершин.

Цикл или Контур — цепь, в котором последняя вершина совпадает с первой.

Длина цикла — количество рёбер в цикле.

Самый короткий цикл — это петля.

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

Цикл Гамильтона — цикл, проходящий через все вершины графа по одному разу. Другими словами — это простой цикл, в который входят все вершины графа.

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

Пока ещё не придуман алгоритм, который за полиномиальное время нашёл бы кратчайший цикл Гамильтона в полном нагруженном графе, однако есть несколько приближённых алгоритмов, которые за приемлимое время находят если не кратчайший, то очень короткий цикл, эти алгоритмы мы также рассматриваем на курсе Отуса — “Алгоритмы и структуры данных”.

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

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

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

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

Лес — граф, в котором несколько деревьев.

Ориентированный граф или Орграф — граф, в котором рёбра имеют направления.

Дуга — направленные рёбра в ориентированном графе.

Полустепень захода вершины — количество дуг, заходящих в эту вершину.

Исток — вершина с нулевой полустепенью захода.

Полустепень исхода вершины — количество дуг, исходящих из этой вершины

Сток — вершина с нулевой полустепенью исхода.

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

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

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

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

Это только основные термины и определения теории графов, которые мы рассматриваем на первом вебинаре модуля “Теория графов”. Цель статьи — дать наглядное и понятное представление об этих терминах, для чего и были нарисованы эти картинки.

3. Элементы теории графов

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

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

В 1736 г. Эйлер показал, что сделать это невозможно.

С тех пор поток задач с применением графов нарастал. Однако теория графов как математическая дисциплина сформировалась только в середине 30-х гг. XX в. благодаря работам таких математиков, как Г. Кёниг, Л.С. Понтрягин, А.А. Зыков и др.

Впервые же понятие «граф» ввел венгерский математик Д. Кёниг в 1936 г.

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

Определение 1. Неориентированным графом (или графом) называется совокупность двух множеств – непустого множества (множества вершин) и множества неупорядоченных пар различных элементов множества(–множество ребер).

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

Например, изображение графа с множеством вершин и множеством реберможет иметь следующий вид (рис. 12).

Изображение графа с множеством вершин и множеством реберможет иметь вид, представленный на рис. 13.

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

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

Определение 4. Степенью вершины называется удвоенное количество петель, инцидентных этой вершине, плюс количество остальных инцидентных ей ребер. Обозначение:. Вершина степени 0 называетсяизолированной, а степени 1 – висячей (концевой). Ребро, инцидентное висячей вершине, называют концевым.

Например, в графе (рис. 14) вершины и– смежные,иинцидентны ребруи являются его концами;– смежные ребра; вершиныине являются смежными, поскольку между ними есть вершина,и– не являются смежными ребрами:

, .

В графе (рис. 15) вершина – изолированная, вершина– висячая; ребро, соединяющее вершинусаму с собой, образует петлю:

, ,.

Теорема 1. Сумма степеней вершин графа всегда четная.

Теорема 2. Сумма степеней всех вершин графа равна удвоенному числу ребер, т. е. , где– число ребер.

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

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

Например, изображение орграфа (рис. 16) с множеством вершини множеством дуг.

Дуга : 1 – начало дуги, 2 – конец дуги;– петля; ребра,– кратные: , ,, , .

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

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

Определение 8. Замкнутая цепь называется циклом, а замкнутая простая цепь – простым циклом.

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

Например, в графе (рис. 17):

–маршрут, но не цепь (длина – 3);

–цепь, но не простая цепь (длина – 5);

–простая цепь (длина – 4);

–цикл, но не простой цикл (длина – 6);

–простой цикл (длина – 3).

Определение 10. Для орграфов цепь называется путем, а цикл – контуром.

Например, в орграфе (рис. 18):

и – пути;

–контур.

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

мультиграф – граф, содержащий кратные ребра;

граф с петлями – граф, содержащий петли (рис. 15);

псевдограф – граф, содержащий как петли, так и кратные ребра (рис. 16);

простой граф – граф без петель и кратных ребер (рис. 14);

полный граф – простой граф, в котором каждая пара вершин соединена ребром (рис. 19);

дерево – простой граф, не содержащий циклов;

эйлеровый граф – граф, содержащий эйлеровый цикл;

гамильтоновый граф – граф, содержащий гамильтоновый цикл.

Вопросы и задачи для самостоятельного решения

1. Для следующего графа (рис. 20):

а) выпишите смежные вершины и смежные ребра;

б) выпишите вершины с инцидентными ребрами;

в) определите степени каждой вершины графа;

г) укажите, как называются вершины ; ребраV и VI;

д) укажите, как называется такой граф.

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

2.1. Для графа на рис. 21:

а) ; в);

б) ; г).

2.2. Для графа на рис. 22:

а) ; в);

б) ; г).

_{2.3. Для графа на рис. 23:} .

3. Для следующего графа (рис. 24):

а) выпишите степени всех вершин;

б) определите, чем являются последовательности ребер и вершин: 1, 2, 1, 3, 4 и 1, 2, 4.

Что такое висячие вершины графа

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

Теперь взглянем на участок Москвы с автомобильными дорогами (скриншот сделан с сайта Яндекс.Карты).

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

Наконец, посмотрим на пример цепи питания в биологии.

Что общего у всех этих картинок? Главное, что на них изображено — это объекты и связи между ними. В теории графов все такие картинки называются графами. Графы состоят из вершин и рёбер. Так, в графе киевского метрополитена станции считаются вершинами, а перегоны между ними — рёбрами. В графе цепи питания биологические виды являются вершинами, и направленное ребро проведено от одного вида к другому тогда, когда первый вид является пищей для второго.

Итак, графом называется набор вершин и набор рёбер. Каждое ребро соединяет две вершины.

Степенью вершины называется количество рёбер, концом которых она является. Например, в графе метрополитенов большинство станций имеют степень 2, а конечные станции имеют степень 1. В графе славянской языковой группы вершина «западнославянский язык» имеет степень 4.

2. Виды графов и пути в графах

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

Путём в графе называется любая последовательность вершин, в которой каждые две соседние вершины соединены ребром. На рисунке выше A → C → B → G — это путь из вершины A в вершину G. Есть и более короткий путь из A в G: путь A → B → G. Длиной путиназывается количество рёбер в нём. Таким образом, кратчайший путь из A в G имеет длину 2.

Циклом в графе называют путь, у которого начальная и конечная вершина совпадают. На рисунке выше путь A → C → B → D → A является циклом.

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

1. между любыми двумя вершинами набора существует путь;
2. набор нельзя расширить, добавив в него ещё хотя бы одну вершину, чтобы при этом осталось верным свойство 1.

В ориентированном графе путём называется любая последовательность вершин, в которой соседние вершины соединены ребром, и это ребро идёт «слева направо» (в нужную сторону). Например, на рисунке ниже A → B → C → D является путём, а A → D → C → B — не является (потому что в графе нет рёбер A → D и C → B).

В ориентированном графе некоторые понятия, которые мы ввели для неориентированных графов, имеют свои аналоги. Например, наряду с понятием «степень вершины», в ориентированных графах используются понятия полустепень захода (количество рёбер, входящих в вершину) и полустепень исхода (количество рёбер, исходящих из вершины). На рисунке выше вершина D имеет полустепень захода 1 и полустепень исхода 3.

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

3. Деревья

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

Ещё одно удивительное свойство деревьев — это связь между количеством вершин и количеством рёбер. Договоримся обозначать буквой V количество вершин (от англ. vertex «вершина»), а буквой E — количество рёбер (от англ. edge «ребро»). Например, у дерева на рисунке выше V = 11, E = 10. Мы видим, что для графа на рисунке E = V − 1.

Чтобы понять, всегда ли это будет верно, рассмотрим висячие вершины. Висячей вершинойназывается вершина степени 1. На рисунке выше висячими являются вершины A, C, F, G, H, J и K. Заметим, что в дереве, в котором есть хотя бы две вершины, всегда есть хотя бы одна висячая вершина. Действительно, выберем произвольную вершину дерева и пойдём из неё гулять по рёбрам дерева в произвольном направлении, не возвращаясь назад. Поскольку циклов в дереве нет, то с каждым шагом мы будем посещать всё новые и новые вершины и в какой-то момент придём в вершину, из которой никуда пойти нельзя. Эта вершина и будет висячей.

Теорема. В любом дереве E = V − 1.

Доказательство. Как мы выяснили, если в дереве хотя бы две вершины, то в нём есть хотя бы одна висячая вершина. Выберем её и удалим из графа её и ребро, за которое она присоединена к графу. При этом количество вершин и рёбер уменьшится на единицу. С новым графом проделаем ту же операцию. В конце концов, когда мы удалим всё, что можно, мы получим граф из одной вершины. Для него V = 1, E = 0, т.е. E = V − 1. Значит, и в исходном дереве выполнялось E = V − 1. ▮

4. Как хранить граф в программах

Второй способ, которым можно хранить этот граф, — это структура данных «матрица смежности». Матрица смежности — это квадратная таблица, в которой на пересечении строки i и столбца j стоит 1, если в графе есть ребро из вершины i в вершину j, и стоит 0, если такого ребра нет.

Заметим, что матрица смежности неориентированного графа всегда симметрична относительно главной диагонали. Главная диагональ в матрице идёт из левого верхнего угла в правый нижний.

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

Семинар ДООМ Задачи, решаемые с помощью деревьев

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

Напомним некоторые свойства дерева.

1. В дереве нельзя вернуться в исходную вершину, двигаясь по ребрам и проходя по одному ребру не более одного раза.

Предположим, что мы смогли это сделать. Выделим этот путь(см. рис. 3). Так как ребра не повторяются, то это цикл. Но в дереве не может быть циклов. Значит, сделать этого нельзя.

2. В дереве любые две вершины соединены ровно одним путем.

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

3. В дереве с n вершинами n-1 ребер.

4. В дереве есть вершина, из которой выходит только одно ребро. Такая вершина называется висячей (см. рис. 5 — кругами выделены висячие вершины).

5. При удалении любого ребра из дерева он становится несвязным.

Пусть мы удалили ребро между вершинами А и В, и граф остался связным. Значит, в получившемся графе есть путь из А в В. Но в первоначальном графе был еще путь АВ по удаленному ребру, а в дереве любые две вершины соединены ровно одним путем.

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

1. Если граф связный и в нем нет циклов, то граф — дерево.

2. Если у связного графа число ребер на один меньше числа вершин, то граф — дерево.

3. Если в графе любые две вершины соединены ровно одним простым путем (таким, в котором ребра не повторяются), то граф — дерево.

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

1. В государстве Океания 17 островов, между ними проложены маршруты так, что с каждого острова выходит ровно четыре маршрута. Докажите, что в Океании есть такие два острова, что с одного до другого можно добраться двумя разными путями (но может быть с пересадками на других островах).

Решение задачи 1.

Представим себе острова вершинами графа, а маршруты — ребрами этого графа. В этом графе сумма степеней вершин равна 17*4 и значит в нем 17*4:2= 34 ребра. Если в этом графе есть цикл, то между любыми вершинами цикла есть два пути — с противоположным направлением обхода. Если же циклов в этом графе нет, то граф является деревом или состоит из нескольких деревьев, а в любом дереве число ребер на 1 меньше числа вершин. Но у нас в графе ребер больше чем вершин, значит в графе есть цикл.

2. На острове — столице Океании 53 дома, некоторые из которых соединены дорогами, и любые два города соединяет ровно один путь. Сколько дорог в столице Океании?

Решение задачи 2.

Пусть дома будут вершинами графа, а маршруты — ребрами этого графа. В этом графе любые два города соединяет ровно один путь, значит граф является деревом. В дереве вершин на 1 больше, чем ребер, значит дорог на 1 меньше, чем домов, значит их 52.

3. В 2007 году водное сообщение между 17 островами Океании стало невозможным из-за нашествия акул. Правительство организовало воздушное сообщение так, чтобы с любого острова можно было попасть на любой другой (но, может быть, с пересадками). Было проложено 16 маршрутов. Докажите, что если один маршрут закрыть, то найдется остров, с которого нельзя будет добраться до столицы (столица расположена на одном острове).

Решение задачи 3.

Пусть острова — вершины графа, а ребра — маршруты. Так как с любого острова можно попасть на любой другой, то граф связный, в нем 17 вершин и 16 ребер, ребер на 1 меньше, значит это дерево. Если один маршрут закрыть (удалить одно ребро из дерева), то граф станет несвязным. Тогда рассмотрим вершину (остров) из той компоненты связности, в которую не входит столица. С этого острова нельзя будет добраться до столицы.

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

Решение задачи 4.

Представим узлы сетки вершинами, а веревочки — ребрами графа. В начале игры было 5*6 вершин и 5*5+4*6=49 ребер (см. рис. 6).

Можно удалять ребра до тех пор, пока в графе остались циклы. Как только граф станет деревом, при удалении любого ребра он перестанет быть связным, и игрок не сможет сделать ход. Вершин при этом осталось 30, значит ребер стало 30-1=29. За игру будет удалено 49-29=20 ребер, значит последний ход сделает второй игрок и выиграет.

5. В Океании объявили конкурс: в куске сетки размером 5×20 ячеек нужно перерезать как можно больше веревочек так, чтобы сетка не распалась на куски. Победитель получит приз. Какое наибольшее число веревочек можно перерезать?

Решение задачи 5.

Если представить узлы сетки вершинами, а веревочки — ребрами графа, то в этом графе нужно удалить как можно больше ребер так, чтобы он остался связным. До разрезания было 6*20+21*5=205 ребер- веревочек. Можно удалять ребра до тех пор, пока не останется граф без цикла. При этом из цикла любое ребро можно удалить, и граф при этом останется связным. Связный граф, в котором нет циклов, дерево, в нем 6*21 вершина и соответственно 6*21 — 1= 125 ребер. Больше ребер удалять нельзя, тогда из дерева получится несвязный граф. Значит, можно удалить 205- 125=180 ребер.