55.50. ГРАФЫ

 
  THIS SECTION IS UNDER CONSTRUCTION  
 

Графы
граф - это совокупность объектов со связями между ними. 
Объекты представляются как вершины или узлы графа, а связи - как дуги или рёбра. 
Для разных областей применения, виды графов могут различаться направленностью,
ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

		Графы
	      /      \
  ориентированные   неориентированные
	




  
  Ориентированный граф 
 

Def
===
Ориентированный граф (Directed Graph)
	пара (V,E), где
		V - конечное множество			(Vertex set)
		E - бинарное отношение на V (VxV)	(Edge set)

Элементы V - называются вершинами
Элементы E - называются дугами

Обозначения:
	Вершина (Vertex) - кружок
	Ребро (Edge)	 - стрелка

Возможны циклические ребра - ребра из вершины в нее же
Ребра вида (v,v) - называются петлями

x = (v,w)  Вершина v - начало дуги x
	   Вершина w - конец  дуги х
	   Дуга x выходит из v и заходит в w.


  





  
  Неориентированный граф 
 

  


Def
===
Неориенированный граф 
	G = (V,E), где
		V - конечное множество			(Vertex set)
		а E - состоит из пар {u,v}, таких что
			u принадлежит V
			v принадлежит V
			u != v	(т.е. не содержит ребер-циклов)

Элементы V - называются вершинами
Элементы E - называются ребрами


Каждое ребро из 2х разных вершин
ребро {u,v} - говорят u смежно с v

x = {u,v}  Вершины u и v - концы ребра х.






Вершины и ребра - элементы графа


Степень вершины - количество ребер для которых она является концевой
		  (при этом петли считаются дважды)

Вершина называется изолированной если она не является концом ни для какого ребра



  

  


  






  
  Пути и циклы 
 

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


Простой путь - все вершины различны

  



Цикл - путь в котором начальная вершина совпадает с конечной и содержит
       хотя бы одно ребро.  (Loop)

Циклом называют путь, в котором первая и последняя вершины совпадают. 
При этом длиной пути (или цикла) называют число составляющих его рёбер.


  


Простой цикл.

Граф без циклов - Ациклический

для ориенированного графа:
  


  





  
  Связанный граф 
 

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

Связанный граф (неориентированный)
  





  
  Полный граф 
 

Полный граф - неориенированный граф любая вершина которого смежна любой другой

  

  

  







  
  Лес и деревья 
 

Ациклический неориентированный граф - лес
	Лес в принципе несвязанный
	Его связанные части - деревья
Лес - граф компонентами которого являются деревья

  


  

  

  

  





  
  Свойства 
 

Граф называется:

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




  
  Иерархия графов 
 

  





  
  Мультиграф 
 

Мультиграф (multigraph) 
	одни и те же вершины могут соединять много ребер

Одинаковые пары в G - называют кратными или паралельными ребрами.

Количество одинаковых пар (v,w) в G называют кратностью ребра (v,w)


  


  


  






  
  Псевдограф 
 

Псевдограф - мультиграф у которого также возможны ребра-циклы

  






  
  Гиперграф 
 

Гиперграф (hypergraph)
	содержит гиперребра - соединяющие не две, а произвольное количество
	вершин

  




  
  Размеченный граф 
 

Размеченный граф G = G(V, L, E), где
		V - Vertex set
		L - Label set
		E - подмножество множества VxLxV

Ребро (a,l,b)

Граф с весовыми коэффициентами
  




  
  Представление графа 
 


Список смежных вершин		удобно для разряженных (sparse) графов

  


Матрица смежности		удобно для плотных (dence) графов