Теория графов








Граф (от греческого gr a jw - пишу) - множество V вершин и набор E неупорядоченных и упорядоченных пар вершин; обычно граф обозначают как G(V, E).

Неупорядоченная пара вершин называется ребром, упорядоченная пара - дугой.

Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги - ориентированным (или орграфом).

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

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

Вершины, соединенные ребром или дугой, называются смежными.

Ребра, имеющие общую вершину, тоже называются смежными.

Ребро (или дуга) и любая из его вершин называются инцидентными.

Принято говорить, что ребро (u, v) соединяет вершины u и v, а дуга (u, v) начинается в вершине u и кончается в вершине v.
 
 

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

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

Существуют и другие способы задания графов. Пусть v1, v2, ... vn- вершины графа G(V, E), а e1, e2, ... em - его ребра (дуги).

Матрицей смежности графа G называется матрица A=||aij||, i=1,...,n; j = 1, ..., n, у которой элемент aij равен числу ребер (или дуг), соединяющих вершины vi и vj (соответственно, идущих из вершины vi в вершину vj).

Матрицей инцидентности графа G называется матрица B=||bij||, i=1, .., n; j = 1, ..., m, у которой элемент bij равен 1, если вершина vi инцидентна ребру (дуге) ej и равен 0, если не инцидентна.

Наконец, граф можно задать посредством списков. Например,

вариант 1: списком пар вершин, соединенных ребрами (или дугами);

вариант 2: списком списков для каждой вершины множества смежных с ней вершин.
 
 




0-граф

Графическое представление


 














1) A ° 2) A ° ° B 3) A ° ° B

° C

 4) A ° ° B 5) A ° ° B

C ° ° D C °° D

° E
 
 




Матрица смежности (квадратная!)


 



 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1)
A
2)
A
B
A
0
A
0
0
B
0
0

и так далее.
 
 




Матрица инцидентности (прямоугольная!)


 



 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1)
AA
2)
AA
AB
BA
BB
A
0
A
0
0
0
0
B
0
0
0
0

и так далее.
 
 




Список пар вершин (соответствие)


 


















1) Ж 2) Ж и так далее.
 
 






Список списков смежных вершин (простых поддеревьев)


 


















1) A ( ) 2) A ( ), B ( ) и так далее.
 
 




1-граф

Варианты (с петлями, без петель, дуги, ребра и т.п.)
 
 

Графическое представление


 














и так далее.
 
 




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


 



 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1)
A
2) а)
A
B
A
1
A
1
0
B
0
0

 
 
2) б) 
A
В
2) в)
A
B
A
0
1
A
0
0
В
0
0
B
0
1

 

и так далее.
 
 




Матрица инцидентности


 



 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1)
AA
2)
AA
AB
BA
BB
A
1
A
1
0
0
0
B
0
0
0
0

и так далее.
 
 




Список пар вершин


 


















1) (A, A) 2) a) (A, A) 2) б) (A, В) и так далее.
 
 




Список списков смежных вершин


 


















1) A (A) 2) а) A (A) 2) б) A (B) 2) в) B (B) и так далее.
 
 
 
 

Два графа G(V, E) и H(W, I) называются изоморфными, если существует взаимно-однозначное соответствие между множествами вершин V, W и множествами ребер E, I, сохраняющее отношение инцидентности.

Подграфом G╒(V╒, E╒) графа G(V, E) называется граф с множеством вершин V╒ НV и множеством ребер (дуг) E╒Н E, - такими, что каждое ребро (дуга) из E╒инцидентно (инцидентна) только вершинам из V╒ .

Последовательность ребер (v0, v1), (v1, v2), ..., (vi-1, vi), (vi, vi+1), ..., (vr-1, vr) называется маршрутом, соединяющим вершины v0 и vr. Маршрут замкнут, если v0 = vr.

Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины различны.

Замкнутая (простая) цепь называется (простым) циклом.

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

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

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

Граф называется k - связным (k - реберно - связным), если удаление не менее k вершин (ребер) приводит к потере свойства связности.

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

Длина маршрута (цепи, простой цепи) равна количеству ребер а порядке их прохождения. Длина кратчайшей простой цепи, соединяющей вершины vi и vj в графе G, называется расстоянием d (vi, vj) между viи vj. В связном неориентированном графе расстояние удовлетворяет аксиомам метрики.

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

Среди одноместных операций наиболее употребительны: удаление и добавление ребра или вершины, стягивание ребра (отождествление пары смежных вершин), подразбиение ребра (т.е. замена ребра (u, v) на пару (u, w), (w, v), где w - новая вершина) и др.

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


 
 



Предыдущий раздел Оглавление    Следующий раздел