Часть 2. Теория графов

Исторически сложилось так, что теория графов зародилась в ходе решения головоломок около трехсот лет назад.

Толчок к развитию теория графов получила на рубеже 19 и 20 столетий, когда резко возросло количество работ в области топологии и комбинаторики. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы 20 столетия.

Графы используются в теории планирования и управления, в теории расписаний, в социологии, биологии, химии, медицине, в электронике, теории конечных автоматов и других областях знаний.

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

Во многих прикладных задачах изучаются системы связей между различными объектами. Объекты отмечаются точками, а связи между вершинами отмечаются отрезками (стрелками) между соответствующими точками.

Такие системы и образуют графы. Точки – вершины графа. Отрезки – ребра графа.

Граф может изображать сеть улиц в городе: вершины графа – перекрестки, а дуги – улицы с разрешенным направлением движения (улицы могут быть с односторонним и двусторонним движением).

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

Определение: Введем в рассмотрение два конечных множества.

V – непустое множество объектов V={v₁, …, v _n}

X – некоторый набор пар элементов из V вида x=(v, w) (которые связаны между собой)

Графом – называется алгебраическая система G= (V, X), где V – множество вершин графа, а X – множество ребер графа.

Пример:

G= (V, X)

V={v₁, v₂, v₃, v₄, v₅}

X={( v₁, v₂), (v₁, v₂), (v₂, v₃), (v₂, v₅), (v₅, v₅)}

или

X={x₁, x₂, x₃, x₄, x₅}

Определение: Ребра вида (v, v) называются петлями.

Определение: Одинаковые ребра, т.е. соединяющие одни и те же вершины, называются кратными (или параллельными) ребрами.

Определение: Количество кратных ребер (u, v) называется кратностью ребра (u, v).

Определение: Псевдограф – граф с кратными ребрами и петлями.

Определение: Мультиграф – псевдограф без петель.

Определение: Вершины, не принадлежащие ни одному ребру, называются изолированными.

Определение: Если в графе G указано направление ребер, то граф называется ориентированным.

Для ориентированных графов будем использовать букву Д.

Ребра ориентированного графа называются дугами.

Определение: Если направление ребер не указано, то граф называется неориентированным (н-графом) или просто графом.

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

Определение: Если x= (u, v) – ребро графа, то вершины u и v называются концами ребра x.

Определение: Если x= (u, v) – дуга орграфа, то u называется началом, а v концом дуги x.

В этом случае говорят: что дуга x исходит из вершины u и заходит в вершину v.

Определение: Вершины u, v графа G=(V, X) (орграфа Д=(V, X)) называются смежными, если (u, v)Х, т. е. вершины u, v называются смежными, если существует ребро (дуга), соединяющая их.

Определение: Два ребра называются смежными, если они имеют общую вершину.

Определение: Если вершина v является концом (началом или концом) ребра (дуги) x, то говорят, что вершина v и ребро (дуга) x инциденты.

Определение: Вершина, инцидентная ровно одному ребру, и само ребро называются концевыми (или висячими).

Определение: Степенью вершины v графа G называется число v), равное числу ребер, инцидентных вершине v.

У изолированной вершины v) = 0.

У висячей вершины v) = 1.

Определение: Полустепенью исхода вершины v в орграфе Д называется число v), равное количеству дуг, исходящих из вершины v.

Определение: Полустепенью захода вершины v в орграфе Д называется число v), равное количеству дуг, заходящих в вершину v.

Кол-во вершин и ребер в графе G будем обозначать соответственно n(G) и m(G). Кол-во вершин и дуг в орграфе Д будем обозначать соответственно n(Д) и m(Д).

Утверждение 1. Для любого псевдографа G выполняется равенство:

.

Утверждение 2. Для любого ориентированного псевдографа Д выполняется равенство:

.

Определение: Подграфом графа G называется граф, все вершины и рёбра которого содержатся среди вершин и ребер графа G.

Определение: Подграф называется собственным, если он отличен от самого графа.

Определение: Объединением графов G₁=(V₁, X₁) и G₂=(V₂, X₂) называется граф G=G₁+G₂=(V₁V₂, X₁X₂).

Определение: Пересечением графов G₁=(V₁, X₁) и G₂=(V₂, X₂), где V₁V₂ 0, называется граф G=G₁G₂=(V₁V₂, X₁ X₂).

Определение: Произведением графов G₁=(V₁, X₁) и G₂=(V₂, X₂) называется граф G=G₁×G₂=(V, X), для которого V=V₁×V₂ – декартово произведение множеств вершин исходных графов, а множество ребер X определяется следующим образом: вершины (u₁, u ₂) и (v₁, v₂) смежны в графе G тогда и только тогда, когда или u₁=v₁, а u₂ и v₂ смежны в графе G₂, или u₂=v₂, а u₁ и v₁ смежны в графе G₁.

Часто бывает важно определить, какие графы считаются различными, а какие не различаются. Обычно это связывают с понятием изоморфизма графов.

Определение: Два графа G₁=(V₁, X₁) и G₂=(V₂, X₂) называются изоморфными, если существуют взаимно однозначные отображения f и g, такие, что f: V₁  V₂ и g: X₁  X₂, сохраняющие инцидентность.

Обозначаются: G₁ ~ G₂.

Во многих случаях можно рассматривать графы с точностью до изоморфизма, т.е. не различать изоморфные графы. Однако, если какие-то вершины или рёбра графа обладают различной индивидуальностью, например, они занумерованы или им сопоставлены какие-либо численные характеристики (вес ребра, длина ребра и др.), то естественно при сравнении двух графов эту индивидуальность учитывать.

G₁~G₂~G₃

Определение: Последовательность вершин и ребер (дуг) графа G (орграфа Д) v₁x₁v₂x₂v₃…x_kv_k+1(k1) называется маршрутом (путём) из вершины v₁ в вершину v_k+1.

Определение: Длина пути (маршрута) равна количеству дуг (ребер) в последовательности (=k).

Определение: Вершина v₁ называется началом маршрута (пути), а v_{k+1 –} концом. Остальные вершины называются внутренними.

Маршрут (путь) рассматривается как непрерывная траектория движения по вершинам и рёбрам графа.

Пример: v₁x₁v₂x₃v₃x₆v₄ – маршрут из v₁ в v₄ длиной 3.

Определение: Незамкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны, называется цепью.

Определение: Цепь, в которой все вершины попарно различны, называется простой цепью.

Определение: Замкнутый маршрут (путь), в котором все ребра (дуги) попарно различны, называется циклом (контуром).

Определение: Цикл (контур), в котором все вершины попарно различны, называется простым циклом (простым контуром).

Определение: Неориентированный граф без циклов называется ациклическим.

Определение: Орграф, не имеющий контуров, называется бесконтурным.

Определение: Вершина v называется достижимой из вершины u, если существует маршрут, связывающий вершины u и v.