Дискретная математика (стр. 4 )

Если в орграфе полустепень захода некоторой вершины равна нулю (т. е. d+(v) = 0), то такая вершина называется источником, если же нулю равна полустепень исхода (т. е. d–(v) = 0), то вершина называется стоком.

Графы G1 и G2 равны, то есть G1 = G2, если их множества вершин и ребер совпадают: V1 = V2 и E1 = E2. Графы, отличающиеся только нумерацией вершин и ребер, называются изоморфными.

Пример.

Три внешне различные диаграммы являются диаграммами одного и того же графа.

Дополнением графа G(V1, E1) называется граф `G(V2, E2), где V2 = V1 & E2 =  = {e Î V1 ´ V1 ½ e Ï E1}.

G `G

4.2. Связность

В связном графе любые две вершины соединены (простой) цепью.

Компоненты связности –

связные части графа.

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

Вершина графа называется точкой сочленения, если ее удаление делает граф несвязным.

Мостом называется ребро, удаление которого делает граф несвязным.

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

Пример.

Вершины u, v – точки сочленения, и других точек сочленения нет.

Ребро х – мост, и других мостов нет.

Подграфы {a, b, u, w}, {c, d, v}, {e, f, v} – блоки, и других блоков нет.

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

Пусть G(V, E) – орграф, v1 и v2 – его вершины. Говорят, что две вершины v1 и v2 связаны в орграфе G, если они связаны в графе G’, полученном из G отменой ориентации ребер. Если все вершины в орграфе связаны, то орграф называется связным. Орграф называется односторонне связным, если для любой пары вершин существует путь между ними хотя бы в одну сторону. Говорят, что две вершины v1 и v2 сильно связаны в орграфе G, если существует путь (ориентированная цепь) из v1 в v2 и из v2 в v1. Если все вершины в орграфе сильно связаны, то орграф называется сильно связным.

Пример.

Сильная (слева) связность и связность.

Компоненты сильной связности орграфа – его сильно связные подграфы.

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

 

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

 

Конденсация графа, изображенного выше.

4.3. Планарность

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

Граф планарен тогда и только тогда, когда он не содержит в качестве подграфов ни К5, ни К3, 3.

4.4. Деревья

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

Свойства деревьев:

1.  Дерево – связный граф без циклов.

2.  Дерево – связный граф, в котором q = p – 1.

3.  Любые две вершины соединены в дереве единственной простой цепью.

4.  Любое ребро дерева есть мост.

Пример. Все различные (свободные) деревья с 6 вершинами.

 

Корневым ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами:

·  существует единственный узел, полустепень захода которого равна 0; он называется корнем ордерева;

·  полустепень захода всех остальных узлов равна 1;

·  каждый узел достижим из корня.

Пример. Ориентированные деревья с 4 узлами.

Концевая вершина ордерева называется листом. Вершины, не являющиеся листьями, называются внутренними. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева – это расстояние от корня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева.

Если наибольшая из полустепеней исхода для вершин дерева равна m, тогда дерево называется m-арным деревом. В частном случае, когда m = 2, дерево называется бинарным деревом. В каждом бинарном дереве каждый сын родителя обозначается либо как левый сын, либо как правый сын (но не то и другое одновременно).

В m-арном ориентированном дереве d–(v) £ m для каждой его вершины v. Таким образом, родитель имеет не более m сыновей. Полным m-арным ориентированным деревом называется такое ориентированное дерево, в котором d–(v) = m для каждой его вершины v, не являющейся листом, и все листы находятся на одном уровне. Таким образом, каждый родитель имеет в точности m сыновей.

Контрольные вопросы

1. Нарисуйте следующие графы:

а) К5; б) К1,4.

2. Изоморфны ли следующие графы?

а)

б)

3. Найдите дополнения приведенных ниже графов.

а) б)

 

4. Найдите точки сочленения, мосты, блоки.

5. Которые из приведенных ниже графов являются деревьями?

а) б) в)

 

5. Способы задания графов

Представление проиллюстрируем на следующих примерах:

Граф G Граф D

5.1. Матрица смежности

Представление графа с помощью квадратной булевской матрицы M: array [1..p, 1..p] of 0..1, отражающей смежность вершин, называется матрицей смежности, где

Пример.

		1	2	3	4				1	2	3	4
	1	0	1	0	1			1	0	1	0	0
G:	2	1	0	1	1		D:	2	0	0	1	1
	3	0	1	0	1			3	0	0	0	0
	4	1	1	1	0			4	1	0	1	0