В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 38
Текст из файла (страница 38)
16. Приведите пример графа, для которого выполняются ус- ловия теоремы 44.2, но пе выполняются условия теоремы 44.3. 17. Пусть и-вершинный граф 6 удовлетворяет условиям тео- ремы 44.2. Докажите, что тогда ]КС( ) (п — 1] /4, 18. Найдите гамильтонов цикл в графе, изобрагггенпоьг па рис. 44Н. 19. Покажите, что всякий связный граф содержит маршрут, в котором как~две ребро графа повторяется не более двух раз. 20. Вадача Эйлера о шахматном коне. Найдите такую последо- вательность ходов шахматпого копя, чтобы, начав с произвольной клетки, пройти через каждую клетку шахматной доски один раз и вернуться в исходную. Главп РШ Степенные последовательности Зта глава посвящена теории степенных последовательностей.
Напомним, что степенной последовательностью графа пазываотся список степеней его вершин. Часто по степеням вершин графа можно судить о его строении. Например, граф, в котором полусумма степеней вершин (т. е. число ребер) пе меньше числа вершин, содержит цикл (следствие 13.6); граф, степень каждой вершины которого раппа двум, есть дизъюнктное объединение циклов; граф, степень каждой вершины которого — четное число, не равное нулю, является объединением циклов (теорема 43.1) и т.
д. В предыдущих главах есть и другие факты, поддающиеся иптервретации подобного рода. Гстествепно возникают следующие вопросы. Как связаны между собой степени вершин графа? Как по списку степеней вершин судить о свойствах графа? Какова связь между графами с совпадающими списками степеней верн|ни? Можно ли построить граф с задаяным списком степеней вершин и предписанными теоретпкографовыми свойствами и как это сделать? Подобные вопросы особенно интенсивно изучаются в настоящее время. Зто не только продиктовано внутренней логикой развития теории графов, но имеет и практическое значение. Воли в виде графа представляется коммуникационная схема, узлам которой соответству1от вершины графа, а ребрам — каналы связей между вершинами, то возникает задача построения графа с заданными степенями вершин и, например, максимально возмоягпой связностью.
Такои граф соответствовал бы схеме с заданными пропускными способностями узлов и максимальной падшкностью. Одна из исторически первых задач теории графов также относится к этому кругу проблем. Именно, в 1857 году А. Кали, изучая насыщенные углеводороды, пришел к задаче перечисления деревьев, степени вершин которых равны 1 и 4. 208 9 45. Графическая последовательность Последовательность (!1!, аг, ..., а„) целых неотрицательных чисел ниже называется п-последовательностью и обозпачаотса одной буквой а. и-последовательность й называется графической, если существует граф, степенная последовательность которого совпадает с г1.
Этот граф называется реализауией последовательности а!. Очевидно, что порядок члетюв в графической и-последовательности а несуществен, а каждый ое члоп й! удовлетворяет неравенствам 0 < д, ( и — 1. Часто удобно эти последовательности считать невозрастающими. Согласно лемме о рукопожатиях сумма всех членов графической послодовательности является четным числом. Назовем и-последовательность а правильной, если выполняются два следующих условия: 1) и — 1~!)! ~ !)з ~... ~д„, ь 2) ~~~ а! — четное число. т=! Вез ограничения общности графическую последовательность можно считать правильной.
Иногда последовательность г1 удобно записывать в ви/ ь! Аз ьр! де г1 = з,е! ез ° ° ° ер ), где числа е! попарно различпы,- а показатель Й! означает количество повторений числа с, в последовательности й. Так, (5, 2, 1з)=(5, 2, 1, 1, 1, 1,1,1). 1'ассмотрим последовательность а' = (2', 1') . Существуют ровно пять графов, являзощнхся реализациями последовательности е!. Они имеют следующие компоненты:1) С4,КзиКз,2) Кз,РзиКз,З) РзиКз,4) Рзи Рз, 5) Р4 и Р4. В общем случае графическая последовательность нмеот много реализаций и их число определить сложно.
В установлении связи между этими реализациями важную роль играет вводимое пипке понятие перекл)очепня. Пусть С вЂ” граф, а, Ь, с, а — четыре его попарно различные вергаины, причем аЬ ~ ЕС, ее)~ЕС, по неФЕС, ЫФЕС. Тогда говорят, что граф С допускает перепл!очение з=(аЬ, еа). Полученный е результате переключения з граф обозначается через зС; граф С превращается в зС в результате удаления ребер аЬ и ед и присоединения ребер ае и Ы: зС = С вЂ” аЬ вЂ” е!1+ ас+ Ы. Обратное переключение з ' =(ае, Ы) применимо к графу зС. 14 н, л, нмвлвчаз и лю 209 5 з гз Рвс. 454 Тогда для любой его вершины ( существует такая последовательность переключений зь ..., зо что в графе Н = = з,...з~6 окруасение вершины 1 совпадает с мполсеством из й, вершки наибольших степеней, т.
е, =(.:..; ". (1,2,..., д;), если г) до Хп(() = (1,2,...,( — 1,1+1,...,д;+1), если ((до с' Пусть (, у, й ьз 1'6, 1) 16 (1 ж Е6, (к Ф Е6. Так как д,Р-И„то существует четвертая вершина 1, смегкпая с к, но пе смежная с 1 (рис. 45.2, где, как и всюду в этой главе, пунктирными линиями обо- Х: значепы ребра, отсутствующие в графе).
Следовательно, граф 6 допускает переключение г = (ц, й(). 1"слн 6'= з6, то Й жЕ6', г) ФЕ6'. С слав несколько по обпых пе е- д д Р Рвс. 45.2 ключепий, придем к пуя1пому графуп,а ь' Доказательство теоремы 45.1. Пусть й — правильная графическая и-последовательность. Воспользуемся индукцией по и. Как подтверждает прямая проверка, при и ( 4 каждая графическая последовательность имеет только одну реализацию. Следовательно, для п(4 ут- 210 Тождественное преобразование ребер графа также по определептпо является перекл|очеппем. Например, па рнс.
45.1 изображены графы 6 и з6, где з =((1, 3), (4, 2)). Очевидно, что перек1почопие пе меняет степеней вер1ппп графа. 1'оль перекл1очепий определяется следующей теоремой. Теорема 45.1. Любил реилизацпя грифичсской последосательиости получается из любой другой ее рсали- 1 7 зации посредством прилепения подходящей цепочки переключений. Доказательство этой теоремы основано па следующей лемме.
Л е м м а 45.2. Пусть 6— граф, вершины которого занулеерованы ччьслами 1, 2, ..., и в порядке невозрастания степеней: 16=(1, 2, ..., и), ((еи(=й„А~й,ь 1=1, и — 1. верждение теоремы тривиально. Пусть и) 4 и это утверждение верно для всех графических (и — 1)-последовательностей. Пусть, далее, 6~ и 62 — две реализации последовательности лл. Для каждого из графов 6~ и 62 обозначим через и какую-либо вершину степени А. Согласно лемме 45.2 существуют такие цепочки переключений гь ..., 8, и 81,...,8„, что в графах К~ = 8~...8~6~ и Н, = 8„...
8162 окружения вершины и состоят из вершин степеней лез, алг,..., еле тп Поэтому степенные 1 последовательности графов Н~ — и и Нг — и совпадают. По индуктивному предполонлению существует такая цепочка пеРеключений вь ..., в„что Н1 — и 81 ° ° ° 81(Н2 и) ° Эти переключения не затрагивают вершины и, поэтому Н~ = 81... 8~Не. Далее имеем — 1 — 1 — 1 — 1 61 81 ° 81 Н1 = 81 ° ° ° 81 82 ° 81Н2 = — -1 81 81 81 8182 8162' Иногда, хотя и редко, граф определяется своей степенной последовательностью однозначно.
Гели все реализации графической последовательности изоморфны, то эта последовательность называется уииграфической, а ее реализация — униграфом. Строение униграфов известно, однако его описание слиогком сложно. Упиграфом является, например, простой цикл Се. 5 46. Критерии графичности последовательности Как отмечалось выше, графическую последовательность всегда можно считать правильной. Кроме того, в ней должны быть равные члены (если длина ее п ) 1), поскольку не существует графа, степени всех вершин которого попарно различны (см.
упражнение 11 в гл. 1). Однако указанные условия отнюдь не являются достаточными для графичности последовательности. Очевидно, например, что последовательность (3', 1') пе является графической, хотя и удовлетворяет упомянутым условиям. Известно несколько критериев графичности последовательности. Одной из важнейших теорем такого рода является критерий Гавела — Хакими, к изложеппло которого мы приступим. 14* 2П Пусть й — правильная и-последовательностгь и ) 1. Зафиксируем индекс 1, 1<1< и, и через с*' обоапачим (и — 1)-последовательностгь которая получается иа после- довательности а вычеркиванием инго члена.
Тем самым (дь, если й(1, с'=(сыс„...,с„,), с„= ~, ~аь.ь» если и:) Е Пусть, далее, последовательность с('=((и )г, ..., ~„~) получается пз последовательности с' в результате уменьшения па единицу каждого из первых 4 членов: сь — 1, если Й(ди сю если й) йп Тогда й' называется производной последовательностью. Например, если а =(3, 3, 1, 1), то ср =(2, О, 0) = У, с(г =(2, 3, 1)= сР. Т е о р е м а 46.1 (В. Гавел, 1955 г., С.
Хакими, 1962 г.). Пусть д — правильная п-последовательность, и) 1, Если для какого-либо индекса 1, 1 <1< п, производная последовательность д' является графической, то и й — графическая последовательность. Если последовательность д графическая, то каждая последовательность д' (1= — 1, и) является графической. > Пусть д' — графическая последовательность, Н— ее реализация.
Добавив к графу Н новую вершину и соединив ее ребрами с д; вершинами наибольших степеней, получим реализацию последовательности И. Следовательно, с) — графическая последовательность. Обратно, пусть последовательность й является графической. Согласно лемме 45.2 существует такая реализация С этой последовательности, в которой некоторая вершина о степени й; смежна с д; вершинами, степени которых наибольшие. Очевидно, что граф С вЂ” о является реализацией последователыюсти И'. 'З Предыдущий критерий вместе с леммой 45.2 подсказывают алгоритм распознавания графичности правильной последовательности и построения одной из ее реализаций.
Назовем этот алгоритм (-процедурой. Пусть д— правильная п-последовательпость, р — и-элементное множество вершин (будущего графа), каждому элементу о которого приписано неотрицательное целое число Й(о) — летка, причем д(о)< и. Пустьь далее, Я(о) — подмножество )т, составленное из а(о) отличных от вершины о вершин с максимальными метками (Я(о) оп- 212 ределено не однозначно), Шаг 1-проиедуры заключается в следующем: 4) фиксировать произвольную вершину о с положительной меткой (далее зта вершина называется ведуи1ей); 2) фиксировать одно из подмножеств Я(о); 3) вершину о соединить ребром с каждой вершиной из Я(о); 4) изменить метки вершины о и каждой из вершин и, входящих в Я(о), положив д(о):=О, а(и):= а(и) — 1.
Если в результато применения шага 1-процедуры какая-либо из меток стаяовится отрицательной, то говорят, что зтот шаг проваливается. 1-процедура применяется к правильной и-последовательности а и заключается в последовательном выполз.епии шагов. Берем )т = ($, 2, ..., п) и первоначально ~ ° ьп о ° и ьи г е нч вя ° .а~ Л ° ~Э Я Я ° ф! 1 «» ° . ° „Н 4 З Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
