1. Основные понятия теории графов
Граф - система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий (рис. 1).
Кружки называются вершинами графа, линии со стрелками - дугами, без стрелок - ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным (рис. 1, А); граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным (рис. 1, Б).
Опр. 1. Задано конечное множество X, состоящее из n элементов (X = {1, 2,…, n}), называемых вершинами графа, и подмножество V декартова произведения X ?X, то есть , называемое множеством дуг, тогда ориентированным графом G называется совокупность (X, V).
Опр. 2. Неориентированным графом называется совокупность множества X и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству X.
Дугу между вершинами i и j, , будем обозначать (i, j). Число дуг графа будем обозначать m (V = ()).
Опр. 3. Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми ребрами (дугами), соединяющими вершины из этого множества. Если из графа удалить часть ребер (дуг), то получим частичный граф.
Опр. 4. Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) - инцидентным соответствующим вершинам.
Опр.5. Путем называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги.
Опр. 5.1. Простой путь - путь, в котором ни одна дуга не встречается дважды.
Опр. 5.2. Элементарный путь - путь, в котором ни одна вершина не встречается дважды.
Опр. 5.3. Контур - путь, у которого конечная вершина совпадает с начальной вершиной.
Опр. 5.4 Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).
Опр.6. Граф, для которого из (i, j) V следует (j, i) V называется симметрическим.
Опр. 7. Если из (i, j) V следует, что (j, i) V, то соответствующий граф называется антисимметрическим.
Опр. 8.1. Цепью называется множество ребер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого.
Опр. 8.2. Цепь - последовательность смежных вершин.
Опр. 9. Замкнутая цепь называется циклом.
Опр. 10.1. Элементарная цепь (цикл, путь, контур), проходящая через все вершины графа называется гамильтоновой цепью (соответственно - циклом, путем, контуром).
Опр. 10.2. Простая цепь (цикл, путь, контур), содержащая все ребра (дуги) графа называется эйлеровой цепью (соответственно - циклом, путем, контуром).
Опр. 11. Если любые две вершины графа можно соединить цепью, то граф называется связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами.
Опр. 12. Связностью графа называется минимальное число ребер, после удаления которых граф становится несвязным. Для ориентированных графов, если любые две вершины графа можно соединить путем, то граф называется сильно связным. Связный граф, в котором существует эйлеров цикл, называется эйлеровым графом.
Опр. 13. В неориентированном графе степенью вершины i называется число инцидентных ей ребер. Очевидно,. Граф, степени всех вершин которого равны n - 1, называется полным. Граф, все степени вершин которого равны, называется однородным.
Опр. 14. Вершина, для которой не существует инцидентных ей ребер (= 0) называется изолированной. Вершина, для которой существует только одно инцидентное ей ребро ( = 1) называется висячей.
Опр. 15. Определим матрицу смежности графа как квадратную матрицу n ?n, элемент которой равен единице, если (i, j) V, и нулю, если (i, j) V, i, jX. Для неориентированного графа матрица смежности всегда симметрическая.
Опр. 16. Определим матрицу инциденций для ребер графа как прямоугольную матрицу n?m, элемент которой равен единице, если вершина i инцидентна ребру j, и нулю в противном случае, i = 1, n, j = 1, m.
Опр. 17. Матрица инциденций для дуг графа - прямоугольная матрицу m xn, элемент rij которой равен плюс единице, если дуга исходит из вершины i, минус единице, если дуга заходит в вершину i, и нулю в остальных случаях, i = 1, n, j = 1, m
Опр. 18. Деревом называется связный граф без простых циклов, имеющий не менее двух вершин. Для дерева m = n - 1, а число висячих вершин равно Легко показать, что в дереве любые две вершины связаны единственной цепью.
Опр. 19. Прадеревом называется ориентированное дерево, у которого одна из вершин, называемая корнем, не имеет заходящих дуг, а степени захода остальных вершин равны единице.
Опр. 20. Плоским (планарным) называется граф, который можно изобразить на плоскости так, что различным вершинам соответствуют различные кружки и никакие два ребра не имеют общих точек, отличных от их границ (не пересекаются). Для плоского графа существует понятие грани - части плоскости, ограниченной ребрами и не содержащей внутри себя ни вершин, ни ребер.
Опр. 21. Степенью грани называется число ее граничных ребер (висячие ребра считаются дважды).
Любому связному плоскому графу G можно поставить в соответствие двойственный ему связный плоский граф G*, определяемый следующим образом: каждой грани графа G соответствует вершина графа G*, каждому ребру V графа G, являющемуся граничным для граней z1 и z2, соответствует ребро V* графа G*, соединяющее соответствующие граням z1 и z2 вершины.