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

 

В ориентированном графе множество состоит из упорядоченных пар , которые называются дугами или ориентированными ребрами, вершина – начало дуги, – ее конец (рис. 36).

Рис. 36 Полустепенью исхода вершины называется число дуг, исходящих из , она обозначается . Полустепенью захода вершины , , называется число дуг, входящих в .

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

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

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

Если – орграф, то обратным к нему ориентированным графом будет граф , где дуга тогда и только тогда, когда дуга .

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

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