Основные определения теории графов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Граф== {{Определение |definition = Графом <math> G </math> называется пара <math> G = (V, E); </math> где V - конечно…»)
 
(Граф)
Строка 4: Строка 4:
 
Графом <math> G </math> называется пара <math> G = (V, E); </math> где V - конечное множество вершин, а <math> E \subset V \times V </math> - множество рёбер.
 
Графом <math> G </math> называется пара <math> G = (V, E); </math> где V - конечное множество вершин, а <math> E \subset V \times V </math> - множество рёбер.
 
}}
 
}}
В ориентированном графе (v, u) = (u, v).
+
В [[Ориентированный граф|ориентированном графе]] (v, u) = (u, v).
  
 
==Ребро==
 
==Ребро==

Версия 08:40, 10 октября 2010

Граф

Определение:
Графом [math] G [/math] называется пара [math] G = (V, E); [/math] где V - конечное множество вершин, а [math] E \subset V \times V [/math] - множество рёбер.

В ориентированном графе (v, u) = (u, v).

Ребро

Для неориентированного графа

Определение:
Ребром называют неупорядоченную пару вершин [math] (v, u) \in E [/math].

Для ориентированного графа

Определение:
Ребром называют упорядоченную пару вершин [math] (v, u) \in E [/math].


Степень вершины

Для неориентированного графа

Определение:
Степенью вершины vi называется число рёбер инцидентных vi, и обозначается deg vi

Для ориентированного графа

Определение:
Полустепенью входа вершины vi называется число рёбер, входящих в эту вершину, и обозначается deg+ vi.


Определение:
Полустепенью выхода вершины vi называется число рёбер, выходящих из этой вершину, и обозначается deg- vi.


Петля

Определение:
Петлёй в ориентированном графе называется ребро, концы которого совпадают, то есть [math]e=\{v,v\}[/math].

В неориентированном графе петли запрещены.

Путь

Определение:
Путём в графе называется последовательность вида v0 e1 v1 ... ek vk; где ei = (vi-1; vi).


Цикл

Для ориентированного графа

Определение:
Циклом называется путь, начало и конец которого совпадают, тоесть v0 = vk

Для неориентированного графа

Определение:
Циклом называется путь в котором нет двух одинаковых рёбер подряд, а также начало и конец которого совпадают, то есть v0 = vk