Теория Графов. Часть 1 Введение и классификация графов
«Графы являются одним из объединяющих понятий информатики – абстрактное представление, которое описывает организацию транспортных систем, взаимодействие между людьми и телекоммуникационные сети. То, что с помощью одного формального представления можно смоделировать так много различных структур, является источником огромной силы для образованного программиста». Стивен С. Скиена
Введение
Сначала под землей города Москвы ничего не было. Потом была построена первая станция метро, а затем и вторая и третья. Образовалось множество станций метро. На карту было занесено множество точек. Позже между станциями стали прокладывать пути линии. И соединилась станция метро А со станцией метро Б. Все остальные станции также стали соединятся друг с другом и на карте появилось множество линий. В итоге мы имеем Московский метрополитен очень красивый, я там был проверял.
Схема Московского метро
Посмотрите какая красота. У нас имеется множество точек (которые называются вершинами или узлами), а также множество линий (называемые рёбрами или дугами). Обозначим множество вершин буквой V от английского vertex−вершина и множество рёбер обозначим E от английского edge−ребро. Граф в формулах именуют буквой G. Все вершины обязательно должны быть идентифицированы.
Отмечу, что число вершин обозначается буквой n:
Число рёбер обозначается буквой m:
Таким образом граф задается и обозначается парой V,E:
Граф — это совокупность пары множеств. Конечного есть и бесконечные, однако мы их пока не рассматриваем непустого множества V и множества E заданного неупорядоченными парами множества V.
Также определение графа рассказывается в этой статье на Хабре (https://habr.com/ru/post/65367/)
Неформально граф является совокупностью точек и линий. Линии в котором задаются парой вершин, расположенных не важно в каком порядке.
Разберем определение графа подробней. Может ли в G быть пустым множество E? Да без проблем! Такой граф будет называться нулевым, а вершины в нем будут называться изолированными.
Нулевой граф
Только вот множество V вершины пустым быть не может. Ведь множество E рёбра задается парой неупорядоченных вершин множества V. Две вершины образующие ребро, называются концами этого ребра.
Множество E задается парой неупорядоченных вершин множества V.
Пример: Пусть множество V = <1,2,3,4,5>. Тогда множество E =
Граф будет выглядеть следующим образом:
Висячей вершиной называется вершина которая соединена только с одной соседней вершиной. В нашем случаи висячей вершиной будет вершина 5, так как она соединена только с вершиной 1.
Степенью вершины — является количество рёбер исходящих выходящих из вершины и входящих в нее. Данное определение верно для ориентированных графов см. классификацию графов. Для неориентированных графов исходящая степень равна входящей. Степенью вершины 1 будет является число 4. Так как вершина 1 соединена с вершиной 2, 3, 4, 5.
Степень записывают, как:
Максимальная степень, то есть какое количество степеней вообще присутствуют в графе обозначаются, как:
Формула суммы степеней для G = V,E выглядит так:
То есть сумма степеней всех вершин v графа равна удвоенному количеству его рёбер E. Считаем количество степеней в нашем примере. От этого никуда не денешься. Я насчитал 12. А теперь считаем, сколько у нас рёбер. Их 6! Умножаем на 2 и получаем 12. Совпадение? Не думаю!
А давайте представим наш граф в другом виде, но с сохранением данных пар. G теперь имеет следующий вид:
Заметьте я не изменил пары между собой. Вершина 4 также соединяется с вершиной 3, а у вершины 1 степень также осталась 4. Так почему граф имеет совершенно другой вид и законно ли это?
Самое главное в графе это вершины и проведенные между ними рёбра. В связи с этим граф является топологическим объектом, а не геометрическим . То есть объектом который не меняется при любых растяжениях и сжатиях. Нам все равно какой мы сделали отрезок. Кривой, прямой, самое главное это наличие связи между вершинами. По этой причине графы являются очень универсальными в плане практического применения. Мы можем обозначать ими дороги, компьютерную сеть, людей которые дружат друг с другом или даже влюблены друг в друга.
Классификации графов
Первым признаком классификации является отсутствие или наличие ориентации у ребер.
Ребро является неориентированным если у него нет понятия начала или конца. То есть оба его конца равноправны. Такой граф называется неориентированным, обыкновенным или неографом.
Ориентированное ребро обозначается стрелкой. И указывает ориентацию от вершины к вершине. То есть данный граф имеет начало и конец. И называется он ориентированным или орграфом.
Ориентированный граф
Также существует граф со смешанными ребрами. Это когда в графе присутствуют, как ориентированные рёбра, так и неориентированные.
Вторым признаком является отсутствие или наличие кратных ребер.
Кратные ребра — это ребра которые встречаются между двумя вершинами сразу несколько раз. В примере ниже мы видим, что вершина a соединена с вершиной c несколько раз. То же самое происходит и a c b. Такой граф называется мультиграфом.
Граф в котором кратных ребер нет, является простым графом. В простом графе мы просто называем пару вершин для идентификации ребра, но в мультиграфе такое уже не сработает, так как одна и та же пара вершин будет указывать на два ребра и не понятно что к чему будет относится. Поэтому если вы повстречаете мультиграф, то вы должны обозначить каждое ребро отдельно.
Заключение
В данной стать я не рассмотрел, понятия смежности и инцидентности, однако я решил их рассмотреть в следующий раз. Также хочу отметить, что более подробно виды графов, я буду рассматривать в следующих статьях. Если у вас есть вопросы, предложения или я где-то допустил ошибки, то прошу написать их в комментариях.
Основные понятия теории графов. Изолированная и висячая вершина. Основные задачи теории графов. Проблемы надежности
Если связь имеет направление, то она называется дугой , иначе ребром .
Если все связи графа дуги, то такой граф называется ориентированным – орграфом, если ребра неографом.
Если в графе присутствуют и ребра и дуги – граф называют смешанным.
Две вершины называются смежными если они соединены ребром или дугой.
Две связи называются смежными если они имеют общую вершину.
Вершина xi инцидентна uij если она является началом или концом uij.
Ребро / дуга uij инцидентна xi если она входит или выходит из этой вершины.
Число дуг/ребер, инцидентных вершине xi называется степенью этой вершины ρ(xi).
Для неографа ∑(i=1 до |x|)ρ(xi)=2|V|.
Геометрически граф представляет собой множество точек и множество кривых, соединяющих эти точки.
ρ(х1)=3 ρ(х2)=ρ(х3)=2 ρ(х4)=1 ρ(х5)=0
Вершина, не имеющая инцидентных ребер (дуг) называется изолированной ρ(хi)=0.
Вершина, инцидентная только одному ребру/дуге называется висячей.
Граф, в котором перемещаясь от вершины к вершине можно попасть в любую вершину называется связным, иначе – несвязным.
Граф в котором все вершины попарно смежны – полный Kn.
n – количество вершин. Для полного графа |V|=(n(n-1))/2
Граф, имеющий кратные ребра называется мультиграфом.
Граф, в котором опущены некоторые ребра, а число вершин осталось прежним, называется частичным или суграфом.
Граф в котором опущены некоторые вершины и инцидентные им ребра, называется подграфом.
Граф имеющий кратные ребра и петли, называется псевдографом.
Если вершины графа можно разбить на два непересекающихся подмножества x1∩x2=0 так, что не существует ребер, соединяющих вершину из х1 с вершиной х2, то такой граф называется двудольным, бихроматическим, Кёнига.
Полный двудольный граф: все вершины из х1 связаны со всеми вершинами из х2: К3,3,
Графы называются изоморфными если у них одинаковое количество вершин и каждой паре вершин, соединенных в одном графе, соответствует пара вершин, соединенных в другом.
Последовательность ребер графа, в котором любая пара соседних ребер имеет одну и ту же инцидентную вершину – маршрут.
Маршрут, в котором все ребра различны – цепь.
Маршрут, для которого различны все вершины – простая цепь.
Замкнутая цепь – цикл, замкнутая простая цепь – простой цикл.
Цикл, в котором содержатся все ребра – Эйлеров цикл. Необходимое и достаточное условие его существования – четкость степеней всех вершин.
Простой цикл, который проходит через все вершины, называют гамильтоновым циклом..
Достаточное условие существования:
1. если в графе с n вершинами для любой пары вершин xi, xj выполняется условие: ρ(xi)≥n, то в таком графе существует Гамильтонов цикл.
2.В графе существует гамильтонов цикл, если для любой вершины xi выполняется условие ρ(xi)≥n/2
Несвязный граф без циклов, отдельные компоненты которого являются деревом – лес.
Связный граф без циклов — дерево
Любое дерево, построенное на n вершинах содержит (n-1) ребер; а лес, состоящий из n вершин, р деревьев, содержит (n-p) ребер.
Число различных деревьев связанного помеченного графа равно n n -2 /
Для n=4: n n -2 =16
Различают два крайних дерева: последовательное и звездное.
Дерево может быть выделено из любого графа, если оно содержит все вершины графа (это остов или покрывающее дерево)
Каждый граф обладает свойствами, которые оцениваются хар-ческими числами:
1. Цикломатическое число υ(G) – число ребер, которые необходимо удалить из графа, чтобы он стал деревом (или лесом, если граф был несвязным)
K=|U| — число ребер графа
|T|=n-1 – чмсло ребер дерева
υ(G)=k-n+p (если дерево)
2. Хроматическое число K(G) – наименьшее число непересекающихся подмножеств вершин, на которые можно разбить вершины графа так, чтобы ребра графа соединяли вершины только разных подмножеств. (только разноокрашенные вершины)
Граф называется плоским, ели он расположен на плоскости так, что ребра имеют общие точки лишь в вершинах.
Граф, изоморфный плоскому, но имеющий пересечения ребер, называется планарным.
Непланарный граф нельня нарисовать на плоскости без пересечений.
Планарность – свойство, плоскость – его реализация.
Операция расширения графа – замена одного ребра uij на 2: uip и upj с введением вершины р. Операция сжатия – обратная.
Исходный, расширенный и сжатый графы изоморфны с точностью до вершины i-ой степени.
Что такое висячие вершины графа
Начнём с выяснения, зачем же нам нужны графы, какие вещи в реальном мире они позволяют изучать. Посмотрим на карту метрополитена города Киева:
Теперь взглянем на участок Москвы с автомобильными дорогами (скриншот сделан с сайта Яндекс.Карты).
Далее, обратим внимание на генеалогическое древо славянской языковой группы.
Наконец, посмотрим на пример цепи питания в биологии.
Что общего у всех этих картинок? Главное, что на них изображено — это объекты и связи между ними. В теории графов все такие картинки называются графами. Графы состоят из вершин и рёбер. Так, в графе киевского метрополитена станции считаются вершинами, а перегоны между ними — рёбрами. В графе цепи питания биологические виды являются вершинами, и направленное ребро проведено от одного вида к другому тогда, когда первый вид является пищей для второго.
Итак, графом называется набор вершин и набор рёбер. Каждое ребро соединяет две вершины.
Степенью вершины называется количество рёбер, концом которых она является. Например, в графе метрополитенов большинство станций имеют степень 2, а конечные станции имеют степень 1. В графе славянской языковой группы вершина «западнославянский язык» имеет степень 4.
2. Виды графов и пути в графах
Подумаем, нужно ли считать граф дорог ориентированным. Пусть мы пишем программу, которая по графу дорог находит автомобильный маршрут между двумя точками в городе. Поскольку в городе бывают улицы с односторонним движением, то наша программа должна это учитывать. Значит, на каждом ребре нужно хранить направление — возможное направление проезда по ребру. Если по дороге можно проехать в обе стороны, то рисуют два ребра со стрелками в разные стороны.
Путём в графе называется любая последовательность вершин, в которой каждые две соседние вершины соединены ребром. На рисунке выше A → C → B → G — это путь из вершины A в вершину G. Есть и более короткий путь из A в G: путь A → B → G. Длиной путиназывается количество рёбер в нём. Таким образом, кратчайший путь из A в G имеет длину 2.
Циклом в графе называют путь, у которого начальная и конечная вершина совпадают. На рисунке выше путь A → C → B → D → A является циклом.
(Осторожно, сейчас мы введём очень сложное понятие.) Компонентой связностинеориентированного графа называется любой набор его вершин, который удовлетворяет следующим двум свойствам:
- между любыми двумя вершинами набора существует путь;
- набор нельзя расширить, добавив в него ещё хотя бы одну вершину, чтобы при этом осталось верным свойство 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, если такого ребра нет.
Заметим, что матрица смежности неориентированного графа всегда симметрична относительно главной диагонали. Главная диагональ в матрице идёт из левого верхнего угла в правый нижний.
Наконец, третий способ, который часто используют для представления графов, — это структура данных «списки смежности». В списках смежности для каждой вершины хранится список всех её соседей.