Элементы теории графов

Начало теории графов как математической дисциплине было положено Эйлером в его знаменитом рассуждении о Кёнигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной на эту тему в течение почти ста лет. Естественные науки оказали свое влияние на развитие теории графов благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок поддавалось формулировке непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая из этих задач - проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 г. Никакая другая проблема не вызывала столь многочисленных и остроумных работ в области теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до 1973 г. оставалась мощным стимулом исследований различных свойств графов (предложенное в 1973 году положительное решение этой проблемы до сих пор оспаривается некоторыми математиками).

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

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

Граф G = <V, Е> есть совокупность множества вершин V и множества ребер (дуг) Е , причем есть множество упорядоченных пар <x,y> для ориентированного графа и для неориентированного графа ( при этом для неориентированного графа считаем, что ребра {a, b} и {b, a} совпадают {a, b}={b, a}).

Граф неориентированный, если все его ребра не ориентированы, и граф ориентированный, если все его ребра ориентированы.

Ребро ориентированного графа мы обозначаем символом <x, y>; ребро неориентированного графа обозначается символом {x, y}. В случае, когда несущественно, о каком ребре идет речь, или когда это ясно из контекста, будем произвольное ребро графа обозначать символом (x, y).

В приложениях граф обычно интерпретируется как совокупность точек V, в которой точки x и y соединены дугой со стрелкой если <x, y>E и дугой без стрелки если . В случае ориентированного графа для ребра <x, y> вершина x - начальная вершина, y - конечная вершина ребра. Можно также говорить, что e = <x, y> есть ребро, выходящее из вершины x (исходящее из вершины x) и входящее в вершину y. Как в случае ориентированного, так и в случае неориентированного ребра говорят, что ребро e инцидентно вершинам x и y, а так же, что x и y инцидентны ребру e. Говорят, что две вершины x и y графа смежны, если (x, y) является ребром. Два ребра смежны, если они имеют общую вершину.

При фактическом изображении графа имеется большая свобода в размещении вершин и в выборе формы соединяющих их дуг. Поэтому может оказаться, что один и тот же граф представляется совершенно различными чертежами. Будем говорить, что два графа G = <V, E> и G^ = <V^, E^> изоморфны, если существует такое взаимно-однозначное соответствие между множествами их вершин V и V^, что вершины соединены ребрами в одном графе тогда и только тогда, когда соответствующие им вершины соединены в другом графе.

Таким образом, если VV^ и при этом соответствии x  x^, yy^{, то} (x, y) E тогда и только тогда, когда (x, y) E^ ((x, y) E  (x, y) E).

Задача.

Доказать, что графы, изображенные на следующем рисунке 3.1, изоморфны.

Рис. 3.1.

Вершина, не инцидентная никакому ребру, называется изолированной. При определении множества вершин V данного графа часто имеет смысл учитывать только неизолированные вершины.

Важным случаем является неориентированный полный граф U = U(V), ребрами которого являются всевозможные пары {x,y} для всех различных вершин x и y из V. В ориентированном полном графе имеются пары ребер <x,y> и <y,x> для всех различных вершин x, y  V.

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

1. Можно допускать рёбра, у которых обе вершины совпадают l =(x,x). Такое ребро называется петлей. U₀ - полный граф с петлями.

2. Пара вершин может соединяться несколькими ребрами e_i = (x,y)_i , в частности вершины x и y могут соединяться несколькими ребрами в каждом направлении.