С данной статьи начнем разбирать тему графов и связанных с ними алгоритмов.
Итак, Граф – это пара множеств V (англ. vertex) и E (англ. edge)
где V – множество вершин
E – множество неупорядоченных пар вершин из множества V (множество ребер)
Граф может быть ориентированным (часто используют название «орграф»), неориентированным или смешанным. В ориентированном графе, ребра являются направленными (то есть пары в E являются упорядоченными, например, пары (a, b) и (b, a) это два разных ребра). В свою очередь в неориентированном графе, ребра ненаправленные, и поэтому если существует ребро (a, b) то значит, что существует и ребро (b, a). Смешанный граф содержит в себе как направленные, так и не направленные ребра.
Кроме того, графы делятся на взвешенные и невзвешенные. Граф, в котором каждому ребру в соответствие поставлено некоторое числовое значение – вес, называется взвешенным графом. Если никакого числового значения рёбрам не поставлено, то граф называется невзвешенным.
Обозначения, часто используемые в теории графов:
· G = (V, E), здесь G – граф, V – его вершины, а E – ребра;
· |V| - порядок графа (количество вершин).
· |E| - размер графа (количество ребер).
Подграф – это граф в котором множества вершин являются подмножеством вершин оригинального графа, а множество ребер является подмножеством ребер оригинального графа.
Изоморфизм графа – это отношение между графами. Графы А и Б изоморфны если, отобразив наименование вершин графа А в вершины графа Б мы получим граф А с теми же ребрами. Определение очень вольное, зато простое. По рисунку понять намного легче, потому что именно изоморфизм позволяет нарисовать граф как нам удобно.
Планарный граф(плоский) – граф который можно нарисовать без пересечения ребер.
Тут с определением графа закончим и поговорим о ребрах и вершинах.
Кратные ребра – выходящие из общей и входящие в общую вершину.
Петля – ребро начало и конец которой приходится на одну и туже вершину (которая выходит и входит в одну и туже вершину)
Граф без петель и кратных ребер считается простым.
Две вершины v1, v2 называются смежными, если существует соединяющее их ребро.
Два различных ребра смежны, если они имеют общую вершину.
Инцидентные ребра – ребра, исходящие из вершины (один вид инцидентности) или входящие в нее (другой вид инцидентности)
Степень вершины – количество инцидентных ей ребер, а проще - количество ребер, соединяющих ее с другими вершинами (не забываем, что есть две инцидентности, а значит и две степени вершин – входящая степень и исходящая)
Маленькая теорема:
Сумма всех степеней вершин – ЧЁТНА и равна удвоенному количеству всех его ребер.
Висячая вершина (Лист)– вершина, имеющая степень равной 1.
Изолированная вершина – вершина со степенью равной 0.
Дальше просто набор коротких определений о путях и циклах:
Маршрут – это последовательность вершин и ребер вида В0(В0 В1)В1(В1 В2)….Вn
Длина маршрута – количество ребер.
Цепь – маршрут без повторяющихся ребер.
Простая цепь- без повторяющихся вершин.
Путь – это ориентированный маршрут.
Простой путь – если ребра в нем не повторяются
Элементарный путь – это простой путь, в котором и вершины не повторяются
Цикл – это цепь в которой первая и последняя вершина совпадают.
Простой цикл – нет повторяющихся ребер.
Связность: Две вершины называют связными если есть цепь из соединяющая.
Компонента связности – это подграф исходного графа, содержащий все вершины одного из классов эквивалентности по связности и все инцидентные им ребра.
Связный граф – содержащий одну компоненту связности.
Расстояние между вершинами – минимальное количество ребер между ними.
Мост – ребро при удалении которого увеличивается количество компонент связности.
Точка сочленения – вершина при удалении которой увеличивается количество компонент связности.
Не статья, а сплошной глоссарий. И тем не менее существует еще множество других определений, но они скорее всего нам и не понадобятся.
Не менее важный вопрос – как же представлять графы? – разберем в следующей статье.