В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 40
Текст из файла (страница 40)
В ситуации а) из условий теоремы следует, что д =2, де=2, д=(т, 2" '), т>2. Для производной последовательности д" имеем д" =()ь сг, ..., )„-,)=(т — 1, 1 2"-г) г — 1 ~ 1с = т + 2 (и — 3) ) 2 ( и — 2), ~с ) О. б) для производной последовательности В ситуации д" получаем д"=(1 7'„...,7'„г), 7';) 1, с — 1,п — 1, и — 1 ~~",. ~с) 2(п — 2). с=9 Итак, в любой ситуации производная последовательность д" удовлетворяет условиям теоремы и по индуктивному предположению имеет связную реализацию р, получаемую в результате описанной в формулировке теоремы (-процедурьь Добавив к графу Н новую вершину, сгхехсную с вершинами степеней 7д, 7„..., )з„, получим связную реализацшо последовательности д.
з Аналогично доказывается Т е о р е м а 47.2, и-последовательность д может быть реализована деревом тогда и только тогда, яогда она не содсржит нулей и верно равенство в ~ дг = 2(п — 1). Се т При выполнении указанных условий 1-процедура построит реализацию последовательности д деревом, если па каждом шаге выбирать в качестве ведущей вершину с минимальной положительной меткой, На рис. 47.1 показана (-процедура, строящая дерево, которое является реализацией последовательности д = =(3г 2, 14) Перейдем к графам с более высоким числом реберной связности. Приведем без доказательства следующую теорему.
Теорема 47.3 (Д. Узнг, 1976 г.). Каждая правильная графическая и-последовательность д с д„) 1 имеет реализацию, тело реберной связности которой ровно д„, Такая реализация строится 1-процедурой, на каждол( шаге которой ведущей является вершина с минимальной положитслы(ой меткой. С числом вершинной связности дело обстоит слояспее.
Известно, что правильная графическая и-последовательность й может быть реализовала графом с числом вершинкой связности й„или а'„— "(, причем соответствующую реализацию также можно получить посредством Н/ ° (1/ бя (7/ (1) (1! (7! ° (7) (1) (и я! ° (в! ° (Я 5 1 ° (5! РЯ ° (Л 7 ° (5/ (5) Я/ 5 ° (Л (7/ (7! г ° (1! (1/ (1! ° (в/ 5 ° Я! ° (и (Н (З! ° (П) ° бп ° (Я б ° я/ ° (и (в! ° (я ° (я ° (я! ° (я ° Я/ 7 ° (1/ (Я ° аю ° (Я ° (Я ° (В) Рис. 47Л 1-процедуры. Однако доказательство этого факта и опи- сание выбора ведущих веря(ип достаточно громоздки и потому здесь ке приводятся. й 48. Гамильтоиова реализация графической последовательности В этом параграфе будет показано, как с помощью 1-процедуры построить реализацию графической последователькости, обладающую гамильтоповой цепью илп гамильтоковым циклом, если такие реализации существуют, В формулировке следующего утверждения используется обозкачекие Ь'(о), введенное в 4 46.
Теорема 48.х (В. Чакгфейзеп, 4978 г.). Если существует реализация правильной и-последовательности д, име!ощая гвмнльтонову цепь с началом в вершине степени дь то к такой реализации приведет 1-процедура, на первом шаге которой ведущей является вершина степени дь а на каждом из последу!ощих — вершина с минимальной полозкительной л(еткой из множества 8(о), где и — вершина, ведущая на предыдущем шаге.
220 О О1 ° Уд е(О) е10) ° (0) 1 ° (л) (0) о, ° (0) д) з ° (7) (1) О, В ° (2) (1) 1П -1 ° )01) ° (О) ° И) ° (о) 1 (1) (О) (о) (0) е (1) ° (1) е(2) 1'7) ° (1) ° (О) ~)) ( () 4(1) (0) ; ° )'7) ° (2) О е(2) ° 12) о ° (2) е 12) О ~-1 1 1 Рнс. 48.2 Рвс. 483 ~ г?еа иь то существует такая вершина и„, что )г ть 2, и1ие1иЕ6, и,и,ФЕ6. Но тогда граф 6 допускает переключение з=(и1и„, и,е1и,).
Граф в6 имеет гамильтонов цикл (и1, иг, ° ° ., щ, и, и — 1, ° ° ° и 1.1, 1'1) (рис. 48.1). '~ На рис. 48.2 показана процедура построения гамильтгновой реализации последовательности (32, 24). Получен граф 6 с гамильтоновой цепью (1, 3, 2, 5, б, 4); (1, 3, 2, 5, 6, 4, 1) — гамильтонов цикл. Докааательство етой теоремы требует перебора возможных вариантов и потому громоадко; здесь оно опускается. ??ерейдем к построению гамильтоновой реализации. Оно основано на следующей теореме.
Теорема 48.2 (В. Чапгфейзен, 1978 г.). Для того чтобы правальная и-последовательность 1? имела реализаци>о в виде гамнльтонова графа, необходнмо и достаточно выполнение следующих двух условий: 1) 1?1)1, 1=1, и; 2) существует реализацая последовательностн 1?, име- юЩаЯ гамильтоновУ Цепь с началом в веР2аине степени е?ь Необходимость условия теоремы тривиальна, докажем достаточность. Пусть 6 — реализация последовательности 1?, имеющая гамильтонову цепь (и„иг, ..., и„) с началом в вершине и1 степени 1?1. Коли и1и, 1нЕ6, то (01, иь ..., и„, и1) — гамильтонов цикл. ??усть и1и„ФЕ6. Тогда вершина и„смежна с какой- либо вершиной ие где 1 < 1< и — 1.
Рассмотрим вершину и1е1. Если и101+1 ж Е6, то (ип и21 ° ° . 01, и, и — ь °, ин и 01) — гамильтонов цикл. Пусть теперь и1и,ч1 Ф Е6. Поскольку вершина щ смежна как с и1 1, так и с и., а верШнна и1 ПЕ Сисяпа ПИ С и,Е1, НИ С ие, ХОтя доди1~ 5 49. Расщепляемые графы Некоторые свойства графов полностью определяются степенными последовательностями, т. е.
либо присущи всем реализациям степенной последовательности, либо пи одной пз ппх. Одно из таких свойств — расщепляемость. Граф С называется раси(епляелиям, если существует разбиение множества его вершин па клику п независимое множество, т. е. такое разбиение А 9 В= РС, что порождепяый подграф С(А) является полным, а С(В) — пустым.
Это разбиение называется полярным. Множество А называется верхней долей графа С, а В— нижней; одна из этих долей метнет быть пустой. Как подтверждает простая проверка, все графы порядка и ~ 3 расщепляемы, по уже среди четырехвершинпых графов есть и расщепляемые и пе расщепляемые. Для правильной графической последовательности д введем параметр т(с(), положив т(с() = шах(й д,) ( — 1). Например, т(с() = 3 для И =(4-', 2г, 1г). Теорема 49.1 (П. Хаммер, Б.
Симеоне, 1981 г.). Пусть д — правильная графическая п-последовательность, С вЂ” ее произвольная реализация. 1'роф С раси епляем тогда и только тогда, когда верно равенство ~ дг = т(т — 1)+ ~ с(п (2) а=тч-1 где тп = т(д). > Пусть С вЂ” расщепляемый граф. Среди всех полярных разбиений множества (тС выберем разбиение (1) с максимальным числом вершин в верхней доле. Очевидно, что если а ~н А, Ь ~н В и ~А ~ = й, то дед а > й — 1, дед 6 < ( (г.
Следовательно, т = )г. Поскольку С(А) = К, С(В) = О„ , то верно равенство (2). Обратно, пусть для некоторого графа С РС = (1, 2, ... и), с(ед ( = дь Положим А = (1, 2, ..., т), В = (т+ 1, ..., п) и сумму степеней вершин из А разобьем па две части: ;з аг = С + р. в=1 где С вЂ” вклад, вносимый в эту сумму ребрами вида а,ам а,~Л, а Р— тот вклад, который вносят ребра вида ад, а сн Л, б сн В. Очевидно, что верны неравенства п С(т(пс — 1), Р~ ~,' дп (3) с=-~и.ьг Равенство (2) верно только тогда, когда оба неравенства (3) являются равенствами. Но это и означает, что С(А) =- =К., С(В)=О„..
э Очевидно С л е д с т в и е 49.2. Если одна из реализаоий граб) ической последовательности расщепляелса, то и все ее реализас1ии расщепляемы. Графическая последовательность называется расщепляемой, если опа имеет расщепляемую реализацию.
При доказательстве достаточности выполнения условия (2) для расщепляемости графической последовательности а пе были использованы ни смысл параметра т(а), нп то, что последовательность с( не возрастает. Поэтому верно Утверждение 49.3. Для расщепляемости граусической и-последовательности й необходимо и достаточно, чтобы для какого-либо т, 1 < пь < и, выполнялось равенство (2). Расщеплнемые графы составляют ванспый и содерпсательпый класс графов. В частности, оп включает в себя все пороговые графы, рассматриваемые в следующем параграфе. некоторые задачи, сложные в общей ситуации (например, задача построения наибольшего ссезависссмого мнонсества), стаповятсн тривиальными в классе расщепляемых графов. Другие задачи для этого класса графов столь гке сложны, как и для произвольных графов. Известно, например, что проблема изоморфизма произвольных графов просто сводится к аналогичной проблеме для расщепляемых графов (см.
118) ). Характеризация расщепляелсых графов в терминах запрещенных порожденных подграфов приведена в з 62. з 50. Пороговые графы Среди расщепляемых графов важссый класс составляют пороговые графы. Вершины произвольного графа С порядка и занумеруем числамн 1, 2, ..., и, т. с. положим )тб = (1, 2, ..., и). Как и в 2 28, обозначим через т6 222 множество, элементами которого служат все независимые подмножества вершин графа С и пустое множество.
Если существуют такие неотрицательные вещественные числа аь аь ..., а„, р, что множество всех (О, 1)-решений неравенства а~х1 + агхг + .. +а х„ ~ р совпадает с множеством характеристических векторов элементов множества л С, то граф С называется пороговым, а неравенство (1) — разделяющим неравенством. Папример, граф, изображепяый па рис.
50.1, является пороговым, Зх4+ 2хг+ хз+ 2х4 ( 3 — разделяющее нера- Д Ряс. 50.2 Рнс. 503 венство. Очевидно, что полный н пустой графы также являются пороговыми. Отметим некоторые свойства пороговых графов. Очевидно следующее Утверждение 50.1. Любой пороледепный подграф порогового графа таклсе является пороговыз4. Лемма 50.2. Ррафы 2Кг, Р4 и С4 пе являются пороговыми. Г' В самом деле, изобразим схематично все три рассматриваемых графа на одном рисунке 50.2. Пусть теперь какой-либо из этих графов пороговый и а1х~ + агхг + азхз + а4х4 < 44 — разделяющее неравенство. Тогда а1 + аг > р, а4 + аз -= р, аз+ а4 ~ ~, аз+ а4 ~ ~. Но последняя система неравенств противоречива.
Тем самым лемма доказана. з Пепосредствепно из предыдущего вытекает Следствие 50.3. Любой пороговый граф пе имеет порозкдепиых подграфов вида 2Кг, Р4 и С4. Обозначим через К С н О ° С графы, полученные из графа С присоединением позой доминирующей и, соответственно, изолированной вершины. Лемма 50.4. Если 6 — пороговый граф, то оба, графа К. 6 и О ° С таклсе являготся пороговыми.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
