Теория графов и комбинаторика

p~i t т.к. это едй!1отв0ишй набор различных цэлкх но- отридатальных чисел, яв правооходящих *шола р-/ . Тагам 0 ( ^ разом, в rpa|i0 имеегоя одна изолированная ввршяна 2 r ( «Cf 7 - J Е одна верийна степени . Удалим изолированную верши- Получим граф о f " ! вершиной, в которой лшеетоя вершина Степана f " ' , что невозможно. Это прогиворечие доказывает •feopeiii}' Заметим, что эта теорема не справедлива для мульти- гю^юв и псевдографов. Это видно из диаграммы: Пусть Q =(\/, X) ~ х^раф о р вершинами; d\ , . . . . ,(if - <.*0п0па его вертн в порядкен е у б ы в а н и я ; ^ s/> . Тог­ да пооладовательность , df ) йазнваетоя вектором отепенай графа (г • и обозначается d g % a e = C''^ij(iAj"'jaf>). Еолп гмф - однородный отепенй , то вмьсу птт ~JC6-)-n^. Ко следует и& щкдада^еи теоремы, век­ тор отвяадей любото щаехого графа имеет, по крайней мере, два одинтеошк элемента. Кинимальная и максигтьная из «твпеией вершин графа обоа- дачаюгоя соответственно S '{6-} и Л (<--). Очевидно, для однород­ ных грш^ов внлоляяютоя условия S'C^ - А(б^)=ciC&) . S2.5. Отаен'гчтованнне гтехТн Ориентированным графом иг oprpf^OM называатоя пара (?-(\6Г), где V - конечное непустое миожеотзо вершин, а ' Г - конвчнс п шокестяо упорядоченных пар различных элементов из V . Иэ этого оараделения оледует, что f с- , Упорядоченг а пары йэГ называютоя дугами сда^зфа , а Г - множеотвом ? гра­ фа S . Е о л а € Г , 10 говорят, что дуга Y иоходит И.8 велшана V" и заходит в вершну . В этом случае веришна?^ наэырается началок. дуги у <или первой проекцией дуги ; ir="pi~S' ) , а МГ - концом дуги X (или второй проввдкей V : и г - Y ) . Дуги называют также ориентированными ped- рави. На диаграммах Дуги йзо<5раяаютоя в видеш т & оо отрелка- ми, похвэавающвми направление от начала к концу дуги, Ирииеденные в првдадущих параграфах определения глулътигра- фа, ооврдогра|а, no^rpaija, кратных pedep, петель я т . д . , отно- ояфеоя к графам, могут быть легко перефразированы применитель­ но к орграфам о учетом чряентации дуг. Пример диаграммы оргра­ фа с Кратными дугами н петлями изображен на Здеоь 14