Графы и их элементы

Теория графов берет начало с решения знаменитым математиком российской академии наук Леонардом Эйлером задачи о кенигсбергских мостах в 1736 году. Он показал, что нельзя обойти семь городских мостов города Кенигсберг (расположенного на двух островах и по берегам реки Прегал) и вернуться в исходную точку, пройдя по каждому из семи мостов ровно один раз. Следующий импульс теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.

Графы служат удобным средством описания связей между объектами. С графами мы сталкиваемся постоянно. Например, сеть автомобильных дорог, воздушных сообщений, нефтепроводов или газопроводов – все это примеры графов.

Для введения формального определения графа нам понадобятся следующие

Определение 1.1. Пусть нам задано некоторое непустое множество М элементов произвольной природы. Тогда n- местным набором (кортежем) над множеством М называется произвольная последовательность из n элементов этого множества (можно рассматривать и бесконечные наборы). В дальнейшем n- местные наборы над М мы будем задавать с использованием круглых или уголковых скобок перечислением элементов наборов, т.е. в виде (а₁,а₂,…, а_n) или 〈а₁,а₂,…, а_n〉, а их множество обозначать М ⁿ. Таким образом:

Mⁿ= {(а₁,а₂,…, а_n)| а₁,а₂,…, а_n∊M}.

Определение 1.2. С формальной точки зрения обыкновенным графом G называется кортеж (набор) двух объектов G=〈V,U〉, где V – произвольное непустое конечное множество, элементы которого называются вершинами графа, а U – произвольное подмножество множества двухэлементных подмножеств V ⁽²⁾ множества V, элементы которого называются ребрами (или дугами)графа.

Из определения графа сразу следует, что всякое ребро (дуга) графа u ={ v_i,v_j } ∊ U определяется некоторой парой вершин v_i,v_j ∊V. Ясно также, что обыкновенный граф не может иметь ребер вида { v_i,v_i } (петель) и что он не может иметь различных ребер, помеченных одной и той же парой вершин (кратных или параллельных ребер). Если допустить в графе существование кратных ребер, то такой граф называется мультиграфом. Если же допустить в графе существование как кратных ребер так и петель, то такой граф называется псевдографом.

Графы – это способ «визуализации» связей между определенными объектами. Эти связи могут быть как «ненаправленными» (например, сеть дорог с двусторонним движением), так и «направленными» (например, генеалогическое дерево). В соответствии с этим в теории графов выделяют два типа графов – неориентированные и ориентированные графы. В дальнейшем мы будем называть графами неориентированные графы, а ориентированные графы – орграфами. Поскольку для неориентированных графов направления ребер не установлены, то порядок перечисления вершин при описании конкретного ребра графа неважен и потому для обозначения ребер применяется теоретико-множественная символика – ребро обозначается как некоторое множество двух вершин, т.е. { v_i,v_j }. Для орграфов направления ребер существенны и потому ребра орграфа будем обозначать наборами (v_i, v_j) и называть дугами. Граф, содержащий как неориентированные так и ориентированные ребра называется смешанным графом.

Существуют различия в терминологии для графов и орграфов. Проведем (согласно [3]) «параллельное» введение основных понятий графов и орграфов, позволяющее наглядно их сопоставить.

Неориентированные графы	Ориентированные графы
Если ребро u ={ vi,vj }, то говорят, что ребро u соединяет вершины vi и vj. При этом вершины vi и vj называются смежными, а также концами ребра u.	Если дуга u =(vi, vj), то говорят, что дуга u ведет из вершины vi в вершину vj. При этом вершины vi и vj называются смежными, причем vi называют началом, а vj концом дуги u.
Ребро u называют инцидентным вершине v, если она является одним из его концов. Концевые вершины ребра инцидентны ребру, образованному этими вершинами.	Дугу u называют инцидентной вершине v, если она является началом или концом дуги. Начало и конец дуги инцидентны дуге, образованной этими вершинами. Дугу u =(vi, vj) называют заходящей в вершину vj и исходящей из вершины vi.
Степенью вершиныv называют количество deg (v) всех инцидентных ей ребер.	Полустепенью захода вершиныv называют число deg ^–(v) всех заходящих в нее дуг, а полустепенью исхода вершиныv - число deg ^+(v) исходящих из нее дуг. Степенью вершины v называют число deg (v) равное сумме полустепеней захода и исхода этой вершины.
Вершина, степень которой deg (v) равна нулю, называется изолированной.	Вершина, полустепень захода которой deg ^-(v) равна нулю, называется источником, а вершина, полустепень исхода которой deg ^+(v) равна нулю, называется стоком. Вершина, степень которой deg (v) равна нулю, называется изолированной.
Множество вершин графа O(v), смежных с заданной вершиной v составляет окружение вершины v. Справедливо равенство | O(v) | = deg (v).	Для вершины v множество O^+(v) = {x | (v,x)∊U} называют множеством преемников вершины v, а множество O^-1(v) = {x | (х,v)∊U} - множеством предшественников вершины v. Справедливы равенства | O^+(v) | = deg ^+(v), | O^-1(v) | = deg ^-(v)
Цепь (путь) в графе G - это последовательность вершин (конечная или бесконечная) v0,v1,…,vn,…, такая, что любая пара соседних вершин этой последовательности образует ребро графа.	Путь (маршрут) в орграфе G - это последовательность вершин (конечная или бесконечная) v0,v1,…,vn,…, такая, что любая пара соседних вершин этой последовательности образует дугу орграфа, причем левая вершина образует начало, а правая – конец этой дуги.
Для конечной цепи v0,v1,…,vn число n (n⩾0) называют длиной цепи. Таким образом, длина цепи – это количество ее составляющих ребер. Цепь длины 0 – это отдельно взятая вершина графа.	Для конечного пути (маршрута) v0,v1,…,vn число n (n⩾0) называют длиной пути. Таким образом, длина пути – это количество ее составляющих ребер. Путь длины 0 – это отдельно взятая вершина орграфа.
Говорят, что вершина vi графа Gдостижима из вершины vj этого графа, если существует цепь v0,v1,…,vn, такая, что vj = v0 и vi= vn (при этом говорят, что данная цепь соединяет вершины vi и vj, которые называются концами цепи).	Говорят, что вершина vi орграфа Gдостижима из вершины vj этого графа, если существует путь v0,v1,…,vn, такой, что vj = v0 и vi= vn (при этом говорят, что данный путь ведет из вершины vi в вершину vj, называя первую вершину началом пути, а вторую его концом).
Простая цепь - это цепь, все вершины которой, кроме, быть может, первой и последней, попарно различны и все ребра которой попарно различны.	Простой путь - это путь, все вершины которого, кроме, быть может, первой и последней, попарно различны и все ребра которой попарно различны.
Простая цепь ненулевой длины с совпадающими концами называется циклом.	Простой путь ненулевой длины начало и конец которого совпадают называется контуром.
Произвольную цепь ненулевой длины с совпадающими концами, все ребра которой попарно различны, называется замкнутой цепью.	Произвольный путь ненулевой длины, начало и конец которого совпадают, все ребра которого попарно различны, называется замкнутым путем.
Неориентированный граф, не содержащий циклов, называется ациклическим.	Ориентированный граф, не содержащий контуров, называется бесконтурным.

Определим еще несколько понятий общих для неориентированных и ориентированных графов. Вершина графа, инцидентная ровно одному ребру (дуге), называется висячей. Ребро, инцидентное висячей вершине, называется висячим. Граф, множество ребер которого пусто, называется пустым. Граф, в котором любые две вершины соединены ребром, называется полным. Полный граф с n вершинами обозначается K_n. В дальнейшем, если не будет оговорено противное, нас будут интересовать в большинстве случаев обыкновенные неориентированные графы.

Теорема 1.1. Для любой цепи, соединяющей две вершины графа, существует простая цепь, соединяющая те же вершины. Для любого пути, ведущего из вершины v_i в вершину v_j орграфа, существует простой путь, ведущий из v_i в v_j.

Доказательство. Проведем доказательство для неориентированного графа (для орграфа доказательство аналогичное). Пусть вершины v_i и v_j соединены некоторой цепью С. Если эта цепь нулевой длины или является простой, то доказывать нечего (утверждение теоремы выполняется). Если же цепь С простой не является, то в ней существует повторяющаяся вершина w. Подцепь C’ исходной цепи С между двумя повторяющимися вхождениями вершины w - цепь с совпадающими концами.

Дата добавления: 2014-12-16