71. Теория графов. Основные понятия. Решаемые задачи.

Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств. G = (V, E), где V есть подмножество любого счётного множества, а E — подмножество V \times V.

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

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

Основные понятия теории графов

• Граф - система, которая интуитивно может быть рассмотрена как множество точек и множество соединяющих их линий (рис. 1).

• Точки называются вершинами графа, линии со стрелками - дугами, без стрелок - ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным, граф, со стрелками (линии являются дугами) называется ориентированным.

• Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми ребрами (дугами), соединяющими вершины из этого множества. Если из графа удалить часть ребер (дуг), то получим частичный граф.

• Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) - инцидентным соответствующим вершинам.

• Путем называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги.

  • Простой путь - путь, в котором ни одна дуга не встречается дважды.

  • Элементарный путь - путь, в котором ни одна вершина не встречается дважды.

  • Контур - путь, у которого конечная вершина совпадает с начальной вершиной.

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

• Граф, для которого из (i, j) V следует (j, i) V называется симметричным.

• Если из (i, j) V следует, что (j, i) V, то соответствующий граф называется антисимметричным.

• Цепью называется множество ребер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого. Цепь – последовательность смежных вершин.

  • Замкнутая цепь называется циклом.

  • Элементарная цепь (цикл, путь, контур), проходящая через все вершины графа называется гамильтоновой цепью (соответственно – циклом, путем, контуром).

  • Простая цепь (цикл, путь, контур), содержащая все ребра (дуги) графа называется эйлеровой цепью (соответственно – циклом, путем, контуром).

• Если любые две вершины графа можно соединить цепью, то граф называется связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами.

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

• В неориентированном графе степенью вершины i называется число инцидентных ей ребер. Очевидно, . Граф, степени всех вершин которого равны n – 1, называется полным. Граф, все степени вершин которого равны, называется однородным.

• Вершина, для которой не существует инцидентных ей ребер ( = 0) называется изолированной. Вершина, для которой существует только одно инцидентное ей ребро ( = 1) называется висячей.

• Определим матрицу смежности графа как квадратную матрицу n ×n, элемент которой равен единице, если (i, j) V, и нулю, если (i, j) V, i, j X. Для неориентированного графа матрица смежности всегда симметрическая.

• Деревом называется связный граф без простых циклов, имеющий не менее двух вершин. Для дерева m = n – 1, а число висячих вершин равно Легко показать, что в дереве любые две вершины связаны единственной цепью.

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

• Степенью грани называется число ее граничных ребер (висячие ребра считаются дважды).

• Любому связному плоскому графу G можно поставить в соответствие двойственный ему связный плоский граф G*, определяемый следующим образом: каждой грани графа G соответствует вершина графа G*, каждому ребру V графа G, являющемуся граничным для граней z1 и z2, соответствует ребро V* графа G*, соединяющее соответствующие граням z1 и z2 вершины.

Некоторые задачи теории графов

• Задача коммивояжёра — одна из наиболее известных NP-полных задач.

• Изоморфизм графов — можно ли путем перенумерации вершин одного графа получить другой.

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

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

Применение теории графов

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

• В информатике и программировании (граф-схема алгоритма)

• В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.

• В экономике

• В логистике

• В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф).