Типы графов

1. Нуль-граф состоит только из изолированных вершин:

2. Однородный граф - это граф, в котором степени всех вершин одинаковы:

3. Симметрический граф - граф, в котором любые две смежные вершины соединены двумя противоположно ориентированными дугами:

4. Антисимметрический граф - граф без петель, в котором каждая пара смежных вершин соединена только в одном направление:

(x_i, x_j) Î U Þ (x_j,x_i) Ï U.

5. Полный граф - граф, в котором любая пара вершин соединена другой (ребром):

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

7. Изоморфные графы имеют одно и то же число вершин и, если две любые вершины одного графа соединены ребром, то и соответствующие им вершины другого графа тоже соединены (разные изображения одного и того же графа):

D

8. Плоский (планарный) граф - такой граф, который можно изобразить на плоскости так, чтобы никакие два ребра не пересекались в точках, отличных от вершин.

Матричные способы задания графов

Матрицей смежности вершин орграфа называется квадратная матрица п–го порядка (п – число вершин). Строки и столбцы соответствуют вершинам графа, элементы p_ij равны количеству дуг, идущих из i–й вершины в j–ую.

Если орграф состоит из однократных дуг, то матрица состоит из 1 и 0. В случае неориентированного графа ему вместе с ребром (x_i; x_j) принадлежит и ребро (x_j; x_i), поэтому матрица будет симметрической.

Матрица смежности дуг орграфа – это квадратная матрица m–го порядка (m – число дуг). Строки и столбцы соответствуют дугам графа. Элементы q_ij равны 1, если дуга u_i непосредственно предшествует дуге u_j и 0 – в остальных случаях.

Матрицей смежности ребер неориентированного графа является матрица m–го порядка, элементы которой q_ij равны 1, если ребро u_i и ребро u_j имеют общую вершину, и 0 – в остальных случаях.

Матрица инцидентности орграфа – прямоугольная матрица размера nxm, где n – число вершин, m – число дуг. Элементы матрицы

	1, если uj исходит из i-й вершины;
	–1, если uj заходит в i-ю вершину;
	0, если дуга uj не инцидентна вершине;
	2, если вершина является и началом и концом дуги.

Если граф неориентированный, то его элементы 1 и 0.

Пример 1. Для данного графа составить матрицу смежности вершин и определить полустепени захода и исхода.

Решение. Граф содержит 5 вершин, поэтому матрица смежности 5-го порядка. Из х1 исходят дуги к х3 и х4, 2 в х5 , => р13 = р14 = 1, р15 =2. Из х2 в х3 и х4, => р23 = р24 = 1 и т.д. Т.о. х1 х2 х3 х4 х5 Р –(xi) х1 х2 х3 х4 х5 Р+(xi) 4 2 2 2 2 Р+(xi)+ Р –(xi) = Р(xi).

Пример 2. По данной матрице построить наглядное изображение графа.

.

Решение. Это симметрическая матрица 4-го порядка с неотрицательными элементами. Следовательно, ее можно изобразить как граф с 4 вершинами.

Т.к. р₁₁=2 => х₁ инцидентна 2 ребрам с началом и концом в х₁ (т.е. петлям).

р₁₂ = 1 => х₁ и х₂ соединены 1 ребром.

р₁₃ = 0 => ребра (х₁, х₃) не существует.

р₁₄ = 3 => 3 ребра (х₁, х₄). И т.д.