2014-02-02
569
По аналогии с ранее рассмотренными (неориентированными) графами ориентированные графы имеют такие характеристики, как степень вершины, понятия пути и цикла. Перечислим их. Определение 3. Степенью выхода вершины ориентированного графа называется число ребер, для которых эта вершина является началом (число ребер, «выходящих» из вершины). Степенью входа вершины ориентированного графа называется число ребер, для которых эта вершина является концом (число ребер, «входящих» в вершину).
Дерево имеет одну грань — внешнюю (бесконечную грань). Рассмотрим произвольный граф «дерево», имеющее В, вершин и Р ребер. По теореме, из предыдущего пункта, дерево имеет число ребер на 1 меньше, чем число вершин, т. е.
Помимо вершин и ребер плоского графа часто пользуются еще одной его характеристикой — гранями. Определение 2. Гранью плоского графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри циклов.
| На рисунке изображен плоский граф с четырьмя гранями: АВЕА, ЕБВГДЕ, ЕДГЕ и внешняя по отношению к циклу АБВГЕА область, ее называют также «бесконечной» гранью (на рисунке она отмечена штриховкой). | 
|
В-Р=1
|
|
|
Если будем преобразовывать исходное дерево, добавляя к нему непересекающиеся ребра (чтобы получающиеся графы оставались плоскими) — образовывать новые грани (помимо одной бесконечной, имевшейся первоначально). И проследим, как ведут себя соотношения между числами вершин, ребер и граней вновь получаемых графов. То очевидно, что при добавлении одного ребра к графу число граней увеличивается на 1 (появляется простой цикл). При последующих добавлениях с каждым новым ребром либо появляется новый цикл, либо старый «распадается» на два, т. е. в любом случае — при добавлении одного ребра число граней также увеличивается на одно. Таким образом, при данном преобразовании величина Р — Г постоянна
(здесь Р — число ребер, а Г — число граней некоторого полученного в результате преобразований графа).
И, зная, что у дерева одна грань (Г=1):
Р-Г = Р-1
Очевидно, что рассматриваемое преобразование не изменяет исходного числа вершин B.
Пользуясь формулами и равенством: P = В— 1 получим:
Р-Г=В-2.
(доказательство предоставляем вам)
Последняя формула или такой ее вид:
В-Р+Г=2
называется формулой Эйлера.
Эту формулу называют также формулой Эйлера для многогранников, так как это соотношение справедливо для вершин, ребер и граней всех пространственных многогранников.
Существуют значительные классы практических задач, которые решить с помощью ранее рассмотренных типов графов невозможно.
Так, например, схема дорог и площадей города изображается с помощью плоского графа. Но если нужно этой схемой воспользоваться с целью проезда по городу на автомашине, а движение на отдельных (или на всех) улицах одностороннее?
Тогда могут помочь сориентироваться в этой ситуации стрелки, расположенные, например, прямо на ребрах-улицах рассматриваемой схемы (графа) города.
Определение 1.
Ребро графа называется ориентированным ребром, если одну из его вершин считать началом, а другую — концом этого ребра.
Определение 2.
Граф, у которого все ребра ориентированные, называется ориентированным графом.
На практике часто ориентированные графы используют для наглядного представления процесса и результата спортивных соревнований.
|
|
|
| Так, на рисунке изображена (с помощью графа) схема игр между командами А, Б, В, Г, Д, Е. Но эта схема не дает информации о результатах игры. Обычно используют ориентацию ребра от выигравшей команды к проигравшей, т. е. если А выиграла у Д, то граф ориентируют от А к Д. | 
|
| На этом рисунке (с помощью ориентированного графа) показаны результаты игр между командами, изображенными с помощью графа на предыдущем рисунке. Если игра может быть сыграна вничью, то обычно ребро графа оставляют неориентированным (ребро ВЕ) и такой граф называют смешанным. |
| Так, на рисунке изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие: Ст.вх.А=2, Ст.вых.А=1 Ст.вх.В=2, Ст.вых.В=0 Ст.вх.Д=1, Ст.вых.Д=3 |
A1A2, A2A3,..., Аn-1Аn
