Особые типы графов.

1. Нуль граф – это граф, который не содержит дуг.

2. Полный граф – это граф, который содержит все возможные дуги.

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

Отношения на графах.

1. Отношение эквивалентности. Графы являются эквивалентными, если эквивалентны их множества дуг и множества вершин.

2. Отношения подграфа. Граф является подграфом графа G, если множество вершин графа является подмножеством вершин графа G, и множество дуг графа являются подмножеством дуг графа G.

Рис 4.2. Примеры правильных и неправильных подграфов.

3. Отношения частичности. Граф является частичным графом графа G, если множество вершин графа эквивалентно множеству вершин графа G, а множество дуг графа является подмножеством дуг графа G.

Рис 4.3. Пример частичного графа.

Комплексные элементы графа.

1. Цепь – это непрерывная последовательность дуг соединяющих некоторые две вершины.

<b,c>,<c,d>

N1=b N2=d

2. Цепь называется простой, если в ней не повторяется ни одна вершина.

3. Цикл – это простая цепь, у которой начальные и конечные вершины совпадают.

Частные случаи графов.

1. Граф называется связным, если любые его две вершины можно соединить цепью.

Рис 4.4. Примеры связного и несвязного графов.

Для ориентированного графа существует понятие «сильносвязности».

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

2. «Лесом» называется граф не имеющий циклов.

3. «Деревом» называется связный «лес», т.е. связный граф не имеющий циклов.

Методы задания графов.

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

Рис 4.5. Графический способ задания графов.

2. Перечислением. При этом необходимо задать множество вершин и дуг.

3. С помощью матрицы смежности.

	a	b	c	d
a	0	0	0	0
b	1	0	1	0
c	0	0	0	1
d	1	1	0	0

Рис 4.6. Задание графа при помощи матрицы смежности.

Матрица смежности неориентированного графа симметрична относительно главной диагонали.

4. С помощью матрицы инцидентности. Строки матрицы соответствуют вершинам графа, а столбцы – дугам. Если вершина инцидентна дуге, то соответствующий элемент матрицы имеет значение единица. Матрица инцидентности обычно используется для задания графов с малым количеством дуг.

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

a
b	a,c
c	d
d	a,b

Рис 4.7. Задание графа с помощью списка смежности.