![](https://habrastorage.org/getpro/habr/upload_files/89b/bcc/e31/89bbcce313182b866733eec1a5f96656.jpeg)
В этой статье мы познакомимся с основными терминами и определениями Теории графов. Каждый термин схематично показан на картинках.
Самый объёмный модуль на курсе «Алгоритмы и структуры данных» посвящён теории графов.
Граф - это топологичекая модель, которая состоит из множества вершин и множества соединяющих их рёбер. При этом значение имеет только сам факт, какая вершина с какой соединена.
Например, граф на рисунке состоит из 8 вершин и 8 рёбер.
![](https://habrastorage.org/getpro/habr/upload_files/ffb/024/567/ffb024567fd7f560044a3927f8a7aab0.jpg)
Очень многие задачи могут быть решены используя богатую библиотеку алгоритмов теории графов. Для этого достаточно лишь принять объекты за вершины, а связь между ними - за рёбра, после чего весь арсенал алгоритмов теории графов к вашим услугам: нахождение маршрута от одного объекта к другому, поиск связанных компонент, вычисление кратчайших путей, поиск сети максимального потока и многое другое.
В этой статье мы познакомимся с основными терминами и определениями теории графов. На курсе “Алгоритмы и Структуры данных” в компании Отус “Теория графов” изучается в самом объёмном модуле из 6 вебинаров, где мы изучаем десяток самых популярных алгоритмов.
Вершина - точка в графе, отдельный объект, для топологической модели графа не имеет значения координата вершины, её расположение, цвет, вкус, размер; однако при решении некоторых задачах вершины могут раскрашиваться в разные цвета или сохранять числовые значения.
Ребро - неупорядоченная пара двух вершин, которые связаны друг с другом. Эти вершины называются концевыми точками или концами ребра. При этом важен сам факт наличия связи, каким именно образом осуществляется эта связь и по какой дороге - не имеет значения; однако рёбра может быть присвоен “вес”, что позволит говорить о “нагруженном графе” и решать задачи оптимизации.
Инцидентность - вершина и ребро называются инцидентными, если вершина является для этого ребра концевой. Обратите внимание, что термин “инцидентность” применим только к вершине и ребру.
Смежность вершин - две вершины называются смежными, если они инцидентны одному ребру.
Смежность рёбер - два ребра называются смежными, если они инцедентны одной вершине.
Говоря проще - две вершины смежные, если они соединены ребром, два ребра смежные - если они соединены вершиной.
![](https://habrastorage.org/getpro/habr/upload_files/196/e98/9ff/196e989ffc3dad638f48799367d8a38e.jpg)
Петля - ребро, инцидентное одной вершине. Ребро, которое замыкается на одной вершине.
Псевдограф - граф с петлями. С такими графами не очень удобно работать, потому что переходя по петле мы остаёмся в той же самой вершине, поэтому у него есть своё название.
![](https://habrastorage.org/getpro/habr/upload_files/b6c/d37/476/b6cd3747619e537188ab6e7399e45328.png)
Кратные рёбра - рёбра, имеющие одинаковые концевые вершины, по другому их называют ещё параллельными.
Мультиграф - граф с кратными рёбрами.
Псевдомультиграф - граф с петлями и кратными рёбрами.
![](https://habrastorage.org/getpro/habr/upload_files/b8f/dd3/cf1/b8fdd3cf189bc899b66d6096c9cb10ee.jpg)
Степень вершины - это количество рёбер, инцидентных указанной вершине. По-другому - количество рёбер, исходящих из вершины. Петля увеливает степень вершины на 2.
Изолированная вершина - вершина с нулевой степенью.
Висячая вершина - вершина со степенью 1.
![](https://habrastorage.org/getpro/habr/upload_files/d7e/e08/a28/d7ee08a28563fe6710a2c414926c2f28.jpg)
Подграф. Если в исходном графе выделить несколько вершин и несколько рёбер (между выбранными вершинами), то мы получим подграф исходного графа.
![](https://habrastorage.org/getpro/habr/upload_files/468/2ae/118/4682ae118793c500ee384f37d644aec5.png)
Идея подграфов используется во многих алгоритмах, например, сначала создаётся подграф их всех вершин без рёбер, а потом дополняется выбранными рёбрами.
Полный граф - это граф, в котором каждые две вершины соединены одним ребром.
![](https://habrastorage.org/getpro/habr/upload_files/9ab/c15/721/9abc15721c29dbc8a9dc61eaae355be3.png)
Сколько рёбер в полном графе? Это известная задача о рукопожатиях: собралось N человек (вершин) и каждый с каждым обменялся рукопожатием (ребро), сколько всего было рукопожатий? Вычисляется как сумма чисел от 1 до N - каждый новый участник должен пожать руку всем присутствующим, вычисляется по формуле: N * (N - 1) / 2.
Регулярный граф - граф, в котором степени всех вершин одинаковые.
![](https://habrastorage.org/getpro/habr/upload_files/594/284/c2e/594284c2e545f1f07807b85810842480.png)
Двудольный граф - если все вершины графа можно разделить на два множества таким образом, что каждое ребро соединяет вершины из разных множеств, то такой граф называется двудольным. Например, клиент-серверное приложение содержит множество запросов (рёбер) между клиентом и сервером, но нет запросов внутри клиента или внутри сервера.
![](https://habrastorage.org/getpro/habr/upload_files/7e2/517/bdc/7e2517bdc2b557d514a5618661f708f5.png)
Планарный граф. Если граф можно разместить на плоскости таким образом, чтобы рёбра не пересекались, то он называется “планарным графом” или “плоским графом”.
![](https://habrastorage.org/getpro/habr/upload_files/2e2/70e/ad9/2e270ead9df3601b882cb088638bc2f5.png)
Если это невозможно сделать, то граф называется “непланарным”.
Минимальные непланарные графы - это полный граф К5 из 5 вершин и полный двудольный граф К3,3 из 3+3 вершин (известная задача о 3 соседях и 3 колодцах). Если какой-либо граф в качестве подграфа содержит К5 или К3,3, то он является непланарным.
![](https://habrastorage.org/getpro/habr/upload_files/e0d/116/57b/e0d11657b5f28a024156557644e6fbe8.png)
Путь или Маршрут - это последовательность смежных рёбер. Обычно путь задаётся перечислением вершин, по которым он пролегает.
Длина пути - количество рёбер в пути.
Цепь - маршрут без повторяющихся рёбер.
Простая цепь - цепь без повторяющихся вершин.
![](https://habrastorage.org/getpro/habr/upload_files/6f6/ed7/afe/6f6ed7afe8bee69813675589384164e4.jpg)
Цикл или Контур - цепь, в котором последняя вершина совпадает с первой.
Длина цикла - количество рёбер в цикле.
Самый короткий цикл - это петля.
![](https://habrastorage.org/getpro/habr/upload_files/081/47a/9b1/08147a9b12c69345e0dab83efdc21c9c.png)
Цикл Эйлера - цикл, проходящий по каждому ребру ровно один раз. Эйлер доказал, что такой цикл существует тогда, и только тогда, когда все вершины в связанном графе имеют чётную степень.
![](https://habrastorage.org/getpro/habr/upload_files/8a5/306/ecc/8a5306eccdde68a02a324c894a1281c7.jpg)
Цикл Гамильтона - цикл, проходящий через все вершины графа по одному разу. Другими словами - это простой цикл, в который входят все вершины графа.
![](https://habrastorage.org/getpro/habr/upload_files/97e/f41/7f3/97ef417f30dce2a799e8bc3105a41270.jpg)
Взвешенный граф - граф, в котором у каждого ребра и/или каждой вершины есть “вес” - некоторое число, которое может обозначать длину пути, его стоимость и т. п. Для взвешенного графа составляются различные алгоритмы оптимизации, например поиск кратчайшего пути.
![](https://habrastorage.org/getpro/habr/upload_files/eed/345/683/eed345683a3e8b814ac6415230cbc9e7.jpg)
Пока ещё не придуман алгоритм, который за полиномиальное время нашёл бы кратчайший цикл Гамильтона в полном нагруженном графе, однако есть несколько приближённых алгоритмов, которые за приемлимое время находят если не кратчайший, то очень короткий цикл, эти алгоритмы мы также рассматриваем на курсе Отуса - “Алгоритмы и структуры данных”.
Связный граф - граф, в котором существует путь между любыми двумия вершинами.
Дерево - связный граф без циклов.
Между любыми двумя вершинами дерева существует единственный путь.
Деревья часто используются для организации иерархической структуры данных, например, при создании двоичных деревьев поиска или кучи, в этом случае одну вершину дерева называют корнем.
![](https://habrastorage.org/getpro/habr/upload_files/2b9/1a6/8bb/2b91a68bb72d006b9cd9ae9fbe902f62.jpg)
Лес - граф, в котором несколько деревьев.
![](https://habrastorage.org/getpro/habr/upload_files/501/32d/3ba/50132d3ba8ae6672f00b96d2b797eac7.jpg)
Ориентированный граф или Орграф - граф, в котором рёбра имеют направления.
Дуга - направленные рёбра в ориентированном графе.
![](https://habrastorage.org/getpro/habr/upload_files/127/77d/85b/12777d85bf1d6e441663e9f380ee0607.jpg)
Полустепень захода вершины - количество дуг, заходящих в эту вершину.
Исток - вершина с нулевой полустепенью захода.
Полустепень исхода вершины - количество дуг, исходящих из этой вершины
Сток - вершина с нулевой полустепенью исхода.
![](https://habrastorage.org/getpro/habr/upload_files/d25/560/cad/d25560cadcdd2aa19c01f7665b0c2647.png)
Компонента связности - множество таких вершин графа, что между любыми двумя вершинами существует маршрут.
![](https://habrastorage.org/getpro/habr/upload_files/801/d7e/0a0/801d7e0a056fd759f7d097775d936029.jpg)
Компонента сильной связности - максимальное множество вершин орграфа, между любыми двумя вершинами которого существует путь по дугам.
Компонента слабой связности - максимальное множество вершин орграфа, между любыми двумя вершинами которого существует путь по дугам без учёта направления (по дугам можно двигаться в любом направлении).
![](https://habrastorage.org/getpro/habr/upload_files/672/25f/d17/67225fd178e6a80be1320eea86471061.jpg)
Мост - ребро, при удалении которого, количество связанных компонент графа увеличивается.
![](https://habrastorage.org/getpro/habr/upload_files/21a/edb/8f6/21aedb8f6c9e0b8d7d4d36ff4a25d309.jpg)
Это только основные термины и определения теории графов, которые мы рассматриваем на первом вебинаре модуля “Теория графов”. Цель статьи - дать наглядное и понятное представление об этих терминах, для чего и были нарисованы эти картинки.