На первом занятии, вводя понятие графа, мы рассма­тривали в качестве примера состязания спортивных команд. Мы. соединяли две команды, скажем А и С, ребром АС в том случае, когда эти команды уже играли друг с другом. Однако такой граф не дает ответа на один весьма существен­ный вопрос: кто именно выиграл игру?
Этот недостаток легко может быть устранен. Если команда А выиграла у С, условимся ставить на ребре АС стрелку, направленную от А к С. Предположим, что нам известны результаты всех уже сыгранных игр, и добавим к графу рис. 1 соответствующие стрелки; пусть при этом получится граф, изображенный на рис. 58.               

      
Рис 58.

На этом графе показано, что команда А выиграла у С, команда F проиграла А, а В вы­играла все игры — с С, Е, F  и т. д.

Ребро графа называется ориентированным, если одну вершину считают началом ребра, а другую — концом.
Граф, все ребра которого ориентированы, называется ориентированным графом.
Одна и та же вершина ориентированного графа может служить началом для одних ребер и концом для других. Соответственно различают две степени вершины: степень выхода и степень входа.
Степенью выхода вершины А ориентированного графа называется число выходящих из А ребер (обозначение: d+(A)).
Степенью входа вершины А ориентированного графа называ­ется число входящих в А ребер (обозначение: d-(A)).
А что, если какая-то игра окончилась вничью? Мы можем отразить ничейные результаты на графе, оставляя соответствующие ребра неориентирован­ными. При этом мы получим так называемый смешанный граф, на котором имеются как ориенти­рованные, так и неориентированные ребра.
Путем в ориентированном графе G от А1 до Аn называется по­следовательность ориентированных ребер <А1; А2>, <А2; А3>, ..., <Аn-1; Аn>, такая, что конец каждого предыдущего ребра совпадает с началом следующего и ни одно ребро не встречается более одного раза.

Рис. 59
Если в ориентированном графе G нашелся путь от А до В, то обратного пути от В к А может и не быть (рис. 59).
Если существует ориентированный путь от А до В, то говорят, что В достижи­ма из А,
В графе G на рисунке 38 В достижима
из А, А не достижима из В.
Простым путем в ориентированном гра­фе называется путь, в котором ни одна вершина не содержится более одного раза. Замкнутый путь в ориентированном графе называется ориентированным циклом.
Длиной пути называется число ребер в этом пути.
Расстоянием от А до В в ориентированном графе называется длина наикратчайшего пути от А до В. Если пути от А до В не существует, то расстояние от А до В называют бесконечным и обо­значают ?. Расстояние от А до В будем обозначать S (АВ). Для графа на рисунке 38
S (АВ) = 1,    S (СВ) - 2, S (ВС) = ?.
Задача 9.1.
В приморском курортном городе после установления одностороннего движения оказалось, что число улиц, по которым можно въехать на каждый перекресток, равно числу улиц, по которым можно из него выехать. Докажите, что можно предложить такой маршрут патрулирования, который начинается и оканчивается в одном месте и проходит через каждый участок улиц ровно один раз.
Решение.
Построим орграф G, задающий движение в городе.
Орграф называется связным, если от любой его вершины до любой другой можно перейти по дугам без учета их ориентации. Связный орг­раф называется эйлеровым, если в нем есть эйлеров цикл.
Теорема 12. Связный орграф является эйлеровым тогда и только тогда, когда для каждой его вершины v выполняется равенство d-(v) = d+(v).
Теорема доказывается точно так же, как и теорема в задаче 4.2.
Из условия задачи следует, что для вершин построенного графа G выполняется равенство d-(v) = d+(v). Следовательно, граф G эйлеров, и эйлеров цикл определит нужный маршрут патрулирования.
Задача 9.2.
На плоскости отмечено конечное число точек. Некоторые пары то­чек являются началами и концами векторов, причем число векторов, входящих в любую точку равно числу векторов, выходящих из нее. Найдите сумму векторов.
Решение.
Точки плоскости вместе с векторами образуют орграф G.Цикл орграфа, все вершины которого различные, называется контуром.
Теорема 13. Связный орграф G эйлеров тогда и только тогда, когда G является объединением контуров, попарно не имеющих общих ребер.
Доказательство. Необходимость. Пусть G — эйлеров орграф. Рассмотрим его любую вершину u1. Выйдем из вершины u1по некоторой дуге (u1, u2).Это возможно сделать, так как орграф Gсвязный. Поскольку d-(u2) = d+(u2), то из вершины u2можно выйти по дуге (u2, u3). Орграф Gимеет конечное число вершин, поэтому, в конце концов, мы попадем в не­которую вершину w, в которой были раньше. Часть цепи, которая начинается и оканчивается в вершине w, является контуром С1. Удалим дуги кон­тура С1 из орграфа G. В получившемся орграфе G1(возможно несвязном) степени входа и выхода вершин, принадлежавших С, уменьшились на единицу, степени входа и выхода остальных вершин не изменились. Следовательно, для любой вер­шины v орграфа С1 будет выполняться равенство d-(v) = d+(v). Поэтому в орграфе G1 можно выделить контур C2и т.д.
Достаточность доказывается путем объединения контуров в эй­леров цикл (см. доказательство теоремы в задаче 4.2).
Теорема доказана.

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