Методичка_графы. Понятие графа и его элементов. Типы графов Из истории развития теории графов

• Название: Понятие графа и его элементов. Типы графов Из истории развития теории графов
• Дата: 06.03.2019
• Размер: 0.79 Mb.
• Имя файла: Методичка_графы.docx
• Тип: Решение; #69683
• страница: 3 из 4

Напр.: е₁ и е₂ – строго параллельные дуги

е₃ и е_4, е₅ и е₆ – пары нестрого параллельных дуг

(!!) Нестрого параллельные дуги, отображающие ориентацию связи в обоих направлениях, по существу, равноценны неориентированной связи и могут быть заменены ребром.

Опр. Граф, который содержит ребра и дуги, называется смешанным.

Так, изображенный выше ориентированный граф можно изобразить в виде смешанного:

v₁ v₂
v₃

v₅ v₄

(!!) Всякий неориентированный граф можно превратить в ориентированный, заменив в нем каждое ребро на пару нестрого параллельных дуг.

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

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

Напр.: = 3 = 0

v₁ v₂ = 1 = 2
v₅
v₄ v₃

(!!) Очевидно, суммы положительных и отрицательных степеней всех вершин орграфа равны между собой и равны числу всех дуг.

Опр. Вершина, степень которой равна нулю, называется .

Так, v₁ – исток, v₅–сток

(!!) Концевая вершина орграфа может быть либо стоком, либо истоком.

5.3. Ориентированные маршруты

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

Опр. Маршрут, не содержащий повторяющихся дуг, называется путем, а не содержащий повторяющихся вершин, - простым путем.

Опр. Замкнутый путь называется контуром, а простой замкнутый путь – простым контуром.

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

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

ПР. Дан орграф. Сколько в нем маршрутов длины 3? (8)

1 2 3

● ● ●

● ●

4 5

5.4. Связность орграфов

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

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

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

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



5.5. Матрица смежности орграфа

Каждую дугу орграфа е_к представляют как упорядоченную пару вершин (v_i; v_j), при этом (i; j) - элемент матрицы смежности равен числу дуг, направленных от вершины v_i к вершине v_j.

Напр.: v₁ е v₂

e₃ e₄

e₁ e₂ е₈ e₅ v₃

e₆

v₅ е₉ v₄

v1	v2	v3	v4	v5
	1		1		v1
		1	1		v2
	1		1		v3
		1		1	v4
2					v5

(!!)Матрица смежности орграфа, в общем случае, несимметрична. Петлям соответствуют единицы на главной диагонали. Нулевая строка и нулевой столбец с тем же номером соответствуют изолированной вершине.
5.6. Матрица инцидентности орграфа

В случае орграфа ненулевой элемент матрицы инцидентности равен +1, если v_i – начальная вершина дуги е_j, и равен -1, если v_i – конечная вершина дуги е_j. В клетке, соответствующей петле, ставится .

Напр.: Матрица смежности для приведенного выше орграфа имеет вид:

е1	е2	е3	е4	е5	е6	е7	е8	е9
-1	-1					1	1		v1
		1	-1			-1			v2
		-1	1	1	-1				v3
				-1	1		-1	1	v4
1	1							-1	v5

5.7. Графы и бинарные отношения

Пусть на множестве Х задано бинарное отношение R. Ему соответствует ориентированный граф, вершины которого изображают элементы из Х, а дуга (x_i; x_j) существует тогда и только тогда, когда x_i R x_j.

Если имеют место соотношения x_i R x_j и x_j R x_i, то вершины связываются 2-мя нестрого параллельными дугами, которые можно заменить ребром. Таким образом, симметричному отношению соответствует неориентированный граф.

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

Если R транзитивно, то в графе для каждой пары рёбер (x_i; x_j) и (x_j; x_k) имеется замыкающее ребро (x_i; x_k).

Если бинарное отношение х R у устанавливает связь между элементами х и элементами у, то граф такого отношения будет ориентированным биграфом.

Рассмотрим теперь соответствие между операциями над отношениями и операциями над графами. Для каждого отношения R существует обратное ему отношение R^-1, граф которого отличается от графа отношения R тем, что направления всех дуг заменены на противоположные.
6. Деревья

6.1. Понятие дерева. Свойства свободных деревьев

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

(!!) Очевидно, что деревья не имеют петель и кратных ребер, т.е. являются простыми графами.

Среди различных деревьев выделяют 2 важных частных случая:

1. 
   Последовательное дерево, представляющее собой простую цепь.
   
2. 
   Звездное дерево, в котором одна из вершин смежна со всеми остальными вершинами.
   

ПР. а) Различные свободные деревья с 4-мя вершинами:

б) Различные свободные деревья с 5-ю вершинами:





в) Различные свободные деревья с 6-ю вершинами:

Очевидно:

1. 
   Для каждой пары вершин дерева существует единственная соединяющая их простая цепь.
   
2. 
   Дерево на множестве р вершин всегда содержит q = p – 1 ребер.
   
3. 
   Любое ребро дерева является мостом.
   
4. 
   В любом дереве имеются, по крайней мере, 2 концевые вершины.
   
5. 
   При добавлении в дерево ребра образуется цикл, а при удалении хотя бы одного ребра дерево распадается на компоненты, каждая из которых представляет собой также дерево или изолированную вершину.
   

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

(!!) Лес из к деревьев, содержащий р вершин, имеет в точности р – к ребер.

Опр. Остовным деревом (остовом, каркасом или скелетом) неориентированного графа G называется его подграф, содержащий все вершины графа и являющийся деревом.

Ребра графа, не входящие в остов, называются хордами графа относительно остова.
6.2. Дерево с корнем, ветви дерева

Если в дереве отметить некоторую вершину , то ее называют корнем дерева, а само дерево – деревом с корнем.

Обозначая вершины, смежные с вершиной v₀ соответственноv₁, v₂,…, с v₁ – v₁₁, v₁₂,…,а с v₂ – v₂₁, v₂₂,…и т.д., можно построить дерево с корнем.

(!!) Очевидно, что каждая вершина дерева может служить его корнем.

Если v – вершина дерева с корнем v₀, тогда множество всех вершин, связанных с корнем цепями, проходящими через вершину v, порождает подграф, который называется ветвью вершины v в дереве с корнем v₀. Очевидно, что эта ветвь связна и сама является деревом с корнем в этой вершине v.
6.3. Типы вершин и центры деревьев

Пусть дано конечное дерево G. Все его концевые вершины называются вершинами типа 1.Если удалить из графа все такие вершины вместе с инцидентными им ребрами, то получится подграф G, который будет деревом. Концевые вершины дерева G называются вершинами типа 2 в дереве G. Аналогично определяются вершины типов 3, 4, и т.д.

Ясно, что в конечном дереве G имеются вершины лишь конечного числа типов.

Опр. Вершины максимального типа называются центрами дерева.

(!!)Дерево имеет либо 1, либо 2 центра.

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

(!!) Если в дереве , то длина диаметральной цепи равна , где к – максимальный тип вершин дерева.
6.4. Ориентированное дерево

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

(!!) Прадерево имеет единственный корень, и все ребра в нем имеют направление от корня. При этом в каждую вершину ордерева входит только одно ребро.
Опр. Концевая вершина ордерева называется листом.

Опр. Путь из корня в лист называется ветвью.

Опр. Длина наибольшей ветви ордерева называется его высотой.

Опр. Уровнем вершины ордерева называется расстояние от корня до этой вершины. Вершины одного уровня образуют ярус дерева.

(!!) Корень имеет уровень равный 0.

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

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

Бинарное дерево имеет корень и два непересекающихся подмножества, каждое из которых само является бинарным деревом. Эти подмножества называются правым и левым поддеревьями исходного дерева.

Напр.:

Для практических целей, обычно, используют два подвида бинарных деревьев: двоичное дерево поиска и двоичная куча.

Опр. Двоичное дерево называется двоичным деревом поиска, если его элементы расположены так, что для каждого элемента n все элементы в левом поддереве n будут меньше, чем n, а все элементы в правом поддереве - больше, чем n.

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

Напр.: Три двоичных дерева поиска с одним и тем же набором элементов (2, 3, 5, 7, 8)