Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/mmks/dec09/ruhovich.pdf Дата изменения: Mon Mar 29 18:18:19 2010 Дата индексирования: Tue Oct 2 09:32:19 2012 Кодировка: koi8-r

Степенные последовательности ориентированных графов А. Рухович
В данной работе иссдедуются критерии существования планарных орграфов с заданными степенными последовательностями. Четкие формулировки см.ниже. Аналогичные критерии без условия планарности справедливы и доказываются еще более просто. Для последовательностей a1 ; a2 ; a3 ; :::an и b1 ; b2 ; b3 ; :::bn степеней входа и степеней выхода произвольного орграфа выполняется условие (*) a1 + a2 + a3 + ::: + an = b1 + b2 + b3 + ::: + bn . Действительно, количество ре бер орграфа одновременно равно и числу `выходов ре бер из вершин', и числу `входов ре бер в вершины'. Теорема LM. Планарный ориентированный граф на n вершинах со степенями входа a1 ; a2 ; a3 ; :::an и степенями выхода b1 ; b2 ; b3 ; :::bn существует тогда и только тогда, когда выполнено условие (*). В графе без петель cтепень выхода ai вершины i меньше суммы степеней входа остальных вершин. Поэтому в любом графе без петель со степенями входа a1 ; a2 ; a3 ; :::an и степенями выхода b1 ; b2 ; b3 ; :::bn выполнено условие (**) ai + bi b1 + b2 + b3 + ::: + bn для любой вершины i. Теорема M. Планарный орграф без петель на n вершинах степеней входа a1 ; a2 ; a3 ; :::a и степеней выхода b1 ; b2 ; b3 ; :::bn существует тогда и только тогда, когда выполнены условия (*) и (**). Число ре бер в орграфе со степенями входа a1 ; a2 ; a3 ; :::an равно a1 + a2 + ::: + an . В связном графе не менее n - 1 ре бер. Значит, если наш орграф слабо связен, то (***) a1 + a2 + ::: + an n - 1. Теорема LMc. Слабо связный планарный ориентированный граф на n вершинах со степенями входа a1 ; a2 ; a3 ; :::an и степенями выхода b1 ; b2 ; b3 ; :::bn существует тогда и только тогда, когда выполнены условия (*) и (***). Теорема Mc. Слабо связный планарный орграф без петель на n вершинах степеней входа a1 ; a2 ; a3 ; :::an и степеней выхода b1 ; b2 ; b3 ; :::bn существует тогда и только тогда, выполнены условия (*), (**) и (***). Доказательство теоремы LM. Часть `тогда' доказана выше. Докажем часть `только тогда'. Возьмем n вершин 1; 2; : : : ; n. Построим в i-й вершине min{ai ; bi } петель. Назовем вершину i · источником, если ai > bi , · нейтралом, если ai = bi , · стоком, если ai < bi . Нарисуем на плоскости x точек, где x равно сумме ai := ai - bi по каждому источнику i. Назовем эти точки вершинками (не вершинами). Нарисуем на плоскости ai стрелок (не ре бер), выходящих из источника i в вершинки под номерами от a1 + : : : + ai-1 + 1 до a1 + : : : + ai . Аналогично, нарисуем на плоскости bi := bi - ai стрелок, выходящих из вершинок под номерами от b1 + : : : + bi-1 + 1 до b1 + : : : + bi . Все эти начала и концы рисуем попарно непересекающимися вне (уже нарисованных) петель. Так как a1 + a2 + a3 + ::: + an = b1 + b2 + b3 + ::: + bn , то о бщее количество стрелок, входящих в вершины равно количеству стрелок, входящих в вершины. Так же, в каждую вершинку входит одна стрелка и выходит одна стрелка. Теперь удалим каждую вершинку i и стрелки, входящую и выходящую из нее. Вместо них построим ре бро между вершиной, из которой выходила стрелка в i, и вершиной, в которую входила стрелка из i. Это можно сделать, что бы полученный граф не имел самопересечений (см. рис.1). Получится планарный орграф с заданными степенями вершин. QED

n


Доказательство теоремы M. Часть `только тогда' доказана выше. Докажем часть `тогда'. По теореме LM существует нарисованный на плоскости без самопересечений орграф G с тре буемыми степенями вершин. (Но он, возможно, имеет петли. Что бы получить граф без петель, будем удалять петли.) Пусть есть петля в вершине i. Докажем, что в некоторой грани графа G, содержащей i найдется ре бро j k такое, что вершины j и k отличны от i. Действительно, если такого ре бра нет, то и во всем графе нет ре бра, о бе вершины которого отличны от i. Но тогда все ре бра графа либо входят в i, либо выходят из i. Так как есть петля в вершине i, то ai + bi > b1 + b2 + b3 + ::: + bn . Полученное противоречие доказывает тре буемое утверждение. Удалим ре бро j k и петлю в i. Дополним граф ре брами j i и ik как на рисунке 2, т.е. что бы полученный граф был планарным. Нетрудно заметить, что степени вершин графа при этом не изменились. Поскольку вершины j и k отличны от i, то новых петель не появилось. Тогда количество петель сократилось на один. Такими операциями можно удалить все петли в графе, не меняя степеней вершин. Получится искомый орграф без петель. QED Доказательство теоремы LMc. Часть `только тогда' фактически доказана выше. Докажем часть `тогда'. По теореме LM существует планарный граф G с нужными степенями вершин. Пусть он содержит q компонент слабой связности, где q > 1. Из условия (***) вытекает, что в графе не менее n - 1 ре бер. Так как n - 1 > n - q, то хотя бы в одной компоненте слабой связности есть неориентированный цикл (т.е. цикл, в котором ре бра могут быть ориентированы в разные стороны). Возьмем ре бро ij этого цикла и произвольное ре бро kl компоненты слабой связности, не включающей этот цикл. Удалим эти ре бра и до бавим ре бра il и kj , как на рисунке 3. Степени вершин сохранились, число компонент слабой связности понизилось на одну. Планарность графа сохранилась. Такими операциями можно понизить число компонент слабо связности до одной. Получится слабо связный граф. QED Часть `тогда' в теореме Mc выводится из теоремы M аналогично, поскольку при применении описанной операции не могут появиться петли (из-за того, что ре бра ij и kl были в разных компонентах слабой связности).