В этом уроке мы обсудим ориентированный граф. Мы с вами обсуждали графы, но не все задачи можно естественным образом описать теми графами, которые мы обсуждали. Например, в социальной сети есть отношение "быть другом", и если оно взаимно, то это описывается теми графами, которые мы обсуждали. Но бывает так, что это отношение не симметрично, например, "быть подписанным": один человек может быть подписан на другого, но обратное может быть неверно, и тогда это уже не очень описывается теми графами, которые мы обсуждали. Или другой пример: у нас есть транспортная сеть, и в ней есть односторонние дороги. И есть много других случаев, в которых отношения между объектами не симметричны. И для этого мы рассматриваем ориентированные графы. Объекты мы изображаем точками, и мы все еще называем их вершинами. Связанные отношением объекты мы соединяем стрелками и называем их ребрами. И здесь уже важно, что у нас не просто линии, а стрелки, и у стрелки есть начало и конец. При изображении стрелки могут пересекаться — это не запрещается; и возможны ребра сразу в обе стороны, то есть у нас, например, вершины A и B могут быть соединены и туда, и обратно — это тоже допустимо. Итак, ориентированными графами мы называем множество вершин, соединенных ориентированными ребрами, то есть стрелками. Множество вершин, как и для неориентированного случая, обозначают буквой V. Отдельные вершины часто обозначают буквами v и u. Множество ребер, как и раньше, обозначается буквой E. Отдельные ребра обозначаются маленькой буквой e. Давайте обсудим, что разрешается, а что нет, аналогично неориентированному случаю. Допускаем ли мы петли, то есть ребра, ведущие из вершины в саму себя? И допускаем ли мы кратные ребра, то есть ребра, ведущие из одной вершины в другую так, чтобы их было несколько (и при этом здесь важно, что они ведут в одну сторону)? Тут, как и с неориентированным случаем, можно допускать такие конструкции, можно не допускать. Мы по умолчанию не будем этого делать, но, опять же, большинство результатов переносится и на эти случаи. Итак, давайте продолжим с параметрами ориентированных графов. Для неориентированного случая мы заводили степени вершин, и здесь мы можем дать аналогичное определение, они будут немного отличаться. Пусть у нас есть вершина графа, тогда входящей степенью вершины называется число ребер, входящих в вершину v, то есть тех стрелок, которые входят в вершину v, и обозначается это через d плюс от вершины v. Исходящей степенью мы будем называть число ребер, исходящих из вершины v, то есть те, которые покидают вершину v. Обозначаем это d минус от v — количество таких ребер. И, например, для вершины D у нас есть одно входящее ребро из вершины C, и входящая степень здесь один, и два исходящих ребра — в вершину A и в вершину Е, исходящая степень здесь два. У нас было для неориентированного случая соотношение между степенями вершин и числом ребер, здесь есть похожее соотношение, оно немножко отличается, оказывается, что сумма всех исходящих степеней вершин в графе равна сумме всех входящих степеней вершин и равна числу ребер, или в виде формулы можно написать таким образом. Давайте обсудим, как это делается. И доказательство здесь почти такое же, как и для неориентированного случая. Давайте посчитаем двумя способами число концов ребер. И здесь важно: в отличие от неориентированного случая, мы различаем у ребер конец и начало, и мы считаем именно концы ребер. И тогда, при таком подходе, у нас концов ребер будет столько же, сколько самих ребер — у каждого ребра есть ровно один конец. Но с другой стороны, каждый конец ребра входит в какую-то вершину, и количество концов ребер, которые входят в данную вершину, мы обозначали через d плюс от v, так что если мы просуммируем это по всем вершинам, то получится, что количество концов ребер равняется сумме по всем v d плюс от v. Хорошо. Мы получили такое равенство, мы посчитали количество концов ребер двумя способами, оказалось, что это с одной стороны — количество ребер, с другой стороны — сумма входящих степеней вершин. Аналогично можно посчитать двумя способами число начал ребер, и тогда мы получим равенство такое, что количество ребер совпадает с суммой исходящих степеней вершин.
