В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 39
Текст из файла (страница 39)
46.1 полагаем д(1) =й,. Из леммы 45.2 и критерия 46.( вытекает, что возмонгпо одно из двух; либо мы приходим к пулевой последоватольности меток и одновременно получаем реализацию последовательности д, либо очередной шаг проваливается, т, е. последовательность д пе является графическои. На рис. 46.$ 1-процедура демонстрируется на примере последовательности (Зг, 2г). Кагкдый столбец на атом рисунке соответствует одному шагу 1-процедуры.
Отметим еще один критерий графичности последовательности. Т о о р е и а 46.2 (П. Эрдгш, Т. Галлаи, $960 г.). 11рввнльная и-последовательность д является графической тогда и только тогда, когда для каждого й = 4, п — $ верно неравенство ь п ~', И;( И(1с — 4) + ~ пп'п(1с, ЫД.
г=з ~=4+1 213 Д, 1чьт,п, 4 — 1, 1=1,п, с = (сы сз~..., Сп)у и докажем, что последовательность с также удовлетворнет условинм теоремы. Пусть а ь Ь'х — — ~2' А за=~с;, 1=1 ь-х 214 > Необходимость неравенства (1) проверяется легко. Пусть С вЂ” реализация последовательности д, $'С = (1, 2,..., и), дел 1 = Ып 1 = 1, и, Яь = ~з 4. к=х Разобьем сумму Я, на две части: Я, = А + В, где А— сумма степеней вершин порожденного подграфа 6(1, 2, ..., й), а  — вклад, вносимый в сумму Я, реорами вида ((, где 1~ й, 1> й.
Очевидно, что п А(й(й — 1), В< .У,' ш(п(й,сУ,), а=а+ г откуда и вытекает неравенство (1). Приведем доказательство достаточности условий тео- ремы, принадленсащее С. Л. Чоудахгу (1986 г.). Пусть д — правильная п-последовательность, причем неравен- ство (1) верно для каждого й = 1, и — 1. Если д; = г (1= 1, и), то хотя бы одно из чисел г и п четное, по- скольку сумма членов последовательности И вЂ” четное число. Кроме того, г < и — 1. Прк этих условиях суще- ствует п-вершинный регулярный граф степени г (ут- верждение 7.1). Стало быть, д — графическая последова- тельность.
Пусть теперь среди членов 4 последовательности И есть различные, Не ограничивая общности, рассмотрим случай, когда д ть О. Воспользуемся индукцней по сумме 2=1 членов последовательности Ы. При Х = 2 условиям тео- ремы удовлетворяет только одна п-последовательность (1, 1, О, ..., О); зта последовательность, очевидно, гра- фическая.
Возьмем теперь Х) 2 и предположим, что ус- ловия теоремы достаточны для графичности пробой пра- вильной и-последовательности с меньшей чем Х суммой членов. Пусть ~=пил П: г7;) 4 ~). Тогда 1 ~ г< п — 1. Положим Заметим, что Я» = Я» (Й = 1, ( — 1). Нужно доказать перавенства 5» ( й (Й вЂ” 1) + ~.", ппп(й, с1), 1 = 1, и — 1. (2) 1=»ж1 Это совсем просто при й ~ ~. Имеем Я„=- Я» — 1 'й(й — 1) + ~ ппп(Й,111) — 1 1=-»+1 ( Й (1с — 1) + ~л„п11п (й, с1), 1=»+1 и неравенство (2) верно. Пусть теперь й ~ 1 — 1.
В этой ситуации е» = е» = Й1(». (3) Если, к тому же, 11» ( Й вЂ” 1, то из равенств (3) непосред- ственно вытекает Я»( Й(й — 1)( Й(й — 1) + ~~'~~ ппп(й, с1), т. е. неравенство (2) верно. Далее отдельно рассмотрим две возможности: 1) 111 = = й, 2) И» ) й + 1. 1) Заметим, что в рассматриваемом случае о11 — 2) О.
1=И-1 (4) поэтому из (5) следует, что Я»( й(й — 1) + ~~Л~ ппп(й, с1), 1=-»+1 т. е. неравенство (2) верно. 215 Это очевидно при й + 2 ~ п — 1. Если же й+ 2 = и, то 1 = п — 1 и, следовательно, д = ((и — 2) " ', д ) . Далее, имеем Х =(п — 2) (и — 1) + д,. Так как Х вЂ” четное число и 11„ ) О, то 11„ ~ 2, откуда и следует неравенство (4). Согласно (3) и (4) Я„= — й' ( Йа — й + о1»„.1( ( Йа — й + д»+1 + (»т, + ... + д„ вЂ” 2. (5) Для 1) Й имеем д, = пт1п (Й, 11,), д, — 1 = пт!п (й, И, ~), 2) Гели 0„» 72+ 1, то ш1п (/', д,) =- 1пш (72, А 1) = Ус.
Поэтому и Яа = Яа "12(Й вЂ” 1) + ~2 ш1п(А.,4) = 1=-2~-1 = Й(72 — 1) + ~"„ш1п(1с, с1), 1 — 1+1 и неравенство (2) верно. Пусть теперь И ~ а + 1. В этом случае ворпо неравепство и Яд ~ (72 (72 — 1) + ~~',~ тп1п (72, 4) — 1. (6) 12 а+1 Действительпо, если, напротив, (6) певерпо, то и Я„= 12(й — 1) + ~ шип(72, о21). 1=й+1 Положив с=ш1п 0: А+ц.~ ~ Й и учитывая (3), получим и Л11 =я =й(й — 1)+(К+ с — 72)72+ Х А= 1 = 1 -~- 2+ 1 и = й(1+ с — 1) + ~', 111 1=1+г+1 и, далее, 52+1 — (12 + 1) 4, = 72 (~ + в — 1) + и И + )' 4)12(1+ à — 1)+ ~' 4 = 1=-1+ г Ь1 1=1+ -Н а =(Ус+ 1)Л +(У."+ 1)(е+ г — й — 1) + Х А= 1=-1+г-~-1 = (12+ 1)12+ ~ ш1п(71+ 1,01).
1=1-~-2 Последпее противоречпт тому, что последовательпость д удовлетворяет перавепствам (1). Неравепство (6) доказало. С учетом (6) и (3) получаем и Я„( й (72 — 1) + ~.'", пип (!2, п1) — 1. (7) 1=2+1 2Ы В рассматриваемои случае 1~)с+ 1, |(, =с(,~1+1, шш()с, Н,) =ппп ()с, с,) =!с, пйп (к, с„) = с„= |(„— 1, ппп((с, Ы„) = д„, поэтоиу нз (7) вытекает ь Бь( )с(Й вЂ” 1) + ~; ппп (й, с|).
|=аз-1 Тем самым доказано, что в любой ситуации последовательность с удовлетворяет условиям теоремы. Так как суима членов этой последовательности равна Х вЂ” 2, то она графическая по индуктивному предположению. Возьмем произвольную реализацию С последовательности с. Пусть а, Ь ~ (тС, |(е(( а = со с(ед Ь = с . Кслн вершины а и Ь не смежны, то граф С+аЬ является реализацией последовательности д п, следовательно, |( — графическая последовательность.
Пусть аЬ |и ВС. Так как с(сна= А — 1 < и — 2, то существует вершина е |и ('С, пе смежная с а. Но |(еде ) :- с(ед Ь, поэтому существует верни|на ) |и ('С, смежная с е и не снежная с Ь. Итак, граф С допускает переключение в=-(аЬ, е)). Граф вС = С вЂ” аЬ вЂ” е)+ ае+ Ь) также служит реализацией последовательности с, причем в нем вершины а н Ь не смежны. Но тогда, как доказано выше, последовательносты( является графической. < Прн тестировании последовательности с помощью критерия Эрдеша — Галлаи нет необходимости проверять все и — 1 неравенств (1). Пусть Н вЂ” правильная п-последовательност|ь )с (с() =- и|ах П: д| ~ О.
Тогда верно следующее У т в ер ж де н не 4йз.З, Ясла последовательность с( удовлетворяет каждому из неравенств (1) при Й = =1, й(д), то она удовлетворяет и каждому из оставшихся неравенств (1). Доказательство опускается. 5 47. Реализация графической последовательности с максимальной связностью В зависимости от выбора ведущих вершин (-процедура может строить различные роализацнн графической последовательности. Ее можно оргаш|зовать так, чтобы она строила реализации с некоторымн предписанными свойствами, если, конечно, такие реализации существуют. Ниже показано, как с помощью (-процедуры построить такую реализацию С графической последовательно- сти, число Л(6) реберкой связпости которой максимальяо среди всех реализаций.
Пустс, д — правильпая графическая п-последовательность. Поскольку Л(6) - б(6) для любого графа 6 (б(6) — минимальная степень вершил), то мы стремимся построить реализацисо 6 последовательности д с Л(6)= сУ„. Вначале построим просто связную реализацисо. Теорема 47.1. Правилысая графическая п-последовательность д лсожет быть реализована связнылс графом тогда и только тогда, когда д„) О и верно неравенство ~чл~ 4) 2(п — 1).
с=с г,'слсс уссагассссьсе условия выполняются, то 1-процедура, на колкдом сиаге которой ведущей является вершина с минимальной положительной лсетной, приводит к связному графу. 3 а ьс е ч а и и е. Прп д„) 1 перавепство (1) выполняется автоматически. > Необходимость условий теоремы очевидна. В самом деле, связпьш граф порядка п яе имеет изолировассных вершин и число ребер в пем пе менее п — 1.
Из леммы о рукопожатиях вытекает неравенство (1). Достаточпость докажем пядукцией по длине последовательности д. При п = 2 условиям теоромы удовлетворяет только одна последовательность д =(1з). Реализацией этой последовательности служит связный граф Кг, стало быть, для и = 2 теорема верна. Пусть теперь п ) 2 и доказываемое утверясденпе верно для графических последовательностей, длины которых мепьше п. Отдельно рассмотрим два случая: 1) д. = 1, 2) д ) 1.
1) д. = 1. Так как п) 2, то пз яеравепства (1) вытекает, что дс) 1. Рассмотрим производпую последовательность ""=(1ь Ь, 1.-с) Л =А — 1, (с=де с=2, п — 1. Поскольку ь — с ь ~ ус = ',~~ с1; — 2) 2(п — 2), /с) О, то послодоватояьпость д" удовлетворяет условиям теоремы. 218 2) д" ) 1. Сссова будем различать две ситуации: а) дв„— — 2 и б) д„„) 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
