1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 23
Текст из файла (страница 23)
э. Алгогитмизхция наши подзадачи нахождения компонент связности информационного графа и построения отношения несовместимости. Если же мы по-прежнему считаем себя лишь адвокатами нашей конкретной задачи, то мы имеем право с определенным удовлетворением заметить, что хотя мы и не так много добавили к нашему знанию, добытому в первых главах, мы обогатили себя силой всеобщности разработанных нами процедур, приближающих нас к конечной цели: передать машине наше знание в эффективной, т. е.
доступной для реального употребления форме. 5 3.3. Раскраска вергпин графа, Общее исследование Дадим формальное определение задачи нахождения минимальной раскраски. Раскраской вершин неориентированного графа 6 = (Х, Л) называется любое отображение С: Х -~ К множества вершин Х (х„ ...,х„) на произвольное конечное множество К = (йп..., й~) (т ~ и).
Элементы множества К называются красками. Раскраска называется правильной, если для любых г и ) выполняется условие (х,, х;)~Л=>-й(х,) + й(хг). (Выражение А =:-В является сокращенной ааписью стандартной фразы: из того, что выполняется А, следует, что выполняется В.) Минимальной раскраской называется любая такая правильная раскраска, в которой число красок меньше или равно числу красок в любой другой правильной раскраске данного графа. Очевидно, что число красок, используемых в любой минимальной раскраске, одно и то же: оно характеризует сам граф, и обозначается Х(6) или просто Х, когда ясно, о каком графе идет речь, и называется хроматическим числом графа 6. Если нужно указать число красок, использованных при какой-то любой раскраске С графа 6, то его обозначают й(6, С).
Анализ тривиального решения. Иа определения непосредственно вытекает, что для доказательства минимальности некоторой раскраски С нуп1но уметь показывать, что не существует правильной раскраски в меньшее число цветов, нежели й(6, С). Не менее очевидно, что поскольку число различных раскрасок графа конечно, задача нахождения минимальной раскраски и хроматического числа в некотором смысле тривиальна: надо взять все раскраски, выбрать из них правильные и иэ правильных выбрать раскраску с наименьшим числом цветов.
В этот момент будет уместно оценить масштабы такого перебора. Пусть граф из и вершин можно раскрасить Я(п) разными способами. Если мы рассмотрим граф, содержащий на одну вершину больше, то при любой раскраске первых и вершин мы можем новую вершину окрасить либо любой иэ п использованных красок, 1 З.З. РАСКРАСКА ВЕРШИН ГРАФА.
ОБЩЕЕ ИССЛЕДОВАНИЕ с Ь а=3: аЬс 1 111 1' 2 121 112 1 22 113 123 а=1: а 1 а Ь с 1 1 1 1 1 2 1 1 3 1 2 1 1 2 2 1 2 3 1 3 1 1 3 2 1 3 3 2 1 1 2 1 2 2 1 3 2 2 1 2 2 2 2 2 3 а Ь с 2 3 1 2 3 2 2 3 3 3 1 1 3 1 2 3 1 3 3 2 1 3 2 2 3 2 3 3 3 1 3 3 2 3 3 3 либо использовать (и + 1)-ю краску. Таким образом, при переходе от графа с л вершннамн к графу с и + 1 вершиной каждая раскраска и-вершинного графа порождает и + 1 раскраску (и + 1)-вершинного, т. е.
Х(п + 1) = Х(п) Х(п+ 1). Если-сообразить, что Х(1) = 1, то сразу обнаруживаем, что Х(п) = иС Автор был бы счастлив, если в этом месте критически настроенный читатель прервал его наложение, задав хотя бы один нз трех вопросов по поводу этого подсчета: 1. Как учитываются такие раскраски (и + 1)-вершинных графов, в которых (п + 1)-я краска используется более одного раза? 2. Соотношение Х(и + 1) = Х(п) Х(л + 1) справедливо только в том случае, если разнме раскраски п-вершинных графов будут приводить по сделанному построению тоже к разным раскраскам. Так ли это? И, вообще, 3.
Что такое разные раскраски? Эти вопросы тем более уместны, что можно было бы существенно проще получить еще один подсчет числа раскрасок: имеем и-вершинный граф и и красок. Каждую вершину можно раскрасить любой из и красок, т. е. л способами. Все раскраски получим, сочетая все комбинации каждой раскраски для каждой вер.Обс Г() б хар х...х Сопоставим эти два способа подсчета для и = 3. Для случая оценки Х(п) способ получения раскрасок автоматически следует из индуктивного соотношения между Х(п) и Х(п + 1).
Способ получения раскрасок для оценки 1'(и) становится ясным, если рассмотреть любую раскраску как запись и-значного числа в причной системе, где роль разрядов играют вершины графа, а цифр — краски. В результате мы получим следующие раскраски (вершины будем рааличать символами а, Ь и с, а в качестве красок возьмем числа 1, 2 и 3).
2(ав 2(З(=а У(с(: У(З] =З7 ГЛ ». АЛГОРИТМНЭАЦИЯ И2 Сравнивая раскраски, мы обнаруживаем, что метод' У дает нам много «избыточных» раскрасок. Нас не интересуют все раскраски сами по себе; что нам важно — это иметь возможность среди всех правильных выбрать минимальную. Ксли мы можем раскрасить граф одной краской, нам не важно, будет ли это краска 1 или краска 2.
С этой точки арекия мы усматриваем, что хотя метод Я дает формально не все раскраски, он содержит тем не менее все «интересные» раскраски, т. е. такие, иа которых любая раскраска может быть получена тривиальным перекрашиванием, т. е; когда одна какая-то краска ааменяется другой, не присутствующей в исходной раскраске. Сопоставим каждой раскраске из Я(З) те раскраски из У(3), которые могут быть получены последовательностью таких перекрашиваннй: И1-а- И1 222 ЗЗЗ 121 -~ 121 13! 212 123 123 132 2!3 122 -1.
122 133 2И 232 313 3»3 233 ЗИ 322 23! 312 Зг«! И2-~ И2 223 331 ИЗ -~ ИЗ 221 332 с'= Й!, йю...,!«д, полученную путем замены каждого с, на ! ((= 1,..., 1). Втакой раскраске для любого 1 = 2,..., и краска й;. либо совпадает с одной из красок, красящих вершины к!,..., )«; «, либо имеет номер, на единицу болыпий, нежели максимальный из номеров этих красок. Отсюда следует, что с'~Сх „.
Итак, лемма доказан». ~ Вспомнив формулу Стирлинга для и( п! жп"е "ф'2лп, мы видим, что метод Я примерно в е" раа экономнее «тупого» пере- Обозначим множества раскрасок, получаемых по методу Я и методу У, Сх,„и Ст „соответственно. Докажем, что для любой раскраски «~Ст,„существует раскраска с'енС2,„, которая может быть получена иэ с путем некоторого тривиального перекрашивания.
Пусть с = !«„)««,..., й„. Пусть 1„!«,..., г, (! ~~ и) — краски, перечисленные в порядке их использования в раскраске. Рассмотрим раскраску В 33. РАСКРАСКА ВЕРШИН ГРАФА. ОБЩЕЕ ИССЛЕДОВАНИЕ ПЗ бора раскрасок по методу У. Однако даже он соадает раскраски с некоторым «запасом»: иа 6 раскрасок только 5 «по-настоящему рааличных» (чнтателя приглашаем подумать, чтб это в точности значит), а раскраски 112 и 113 сводятся одна к другой с помощью перекраски. Другой источник «запаса» состоит в том, что мы порождаем не только правильные раскраски, которые, собственно, нас и интересуют, но и любые.
Подсчет числа правильных раскрасок уже гораздо сложнее. Во-первых, число раскрасок уже не является функцией только числа вершин, а существенно зависит от графа: метод'Я даст для графа с п изолированными вершинами все и( раскрасок (каждая из которых является правильной), а для полного и-графа (и вершин, попарно смежных) только одну правильную раскраску 1, 2, ..., п.
Во-вторых, оценка оказывается не точной, а асимптотической (как формула Стирлинга), т. е. стремящейся к точной при л-~. Со. В нашем изложении нет возможности доказывать эту оценку, мы только скажем, что аснмптотически число правильных раскрасок связных графов с и вершинами оценивается функцией е". Этот небольшой экскурс в комбинаторику, каким бы поверхностным он ни был, достаточен для нас в одном: любая попытка поиска минимальной раскраски прямым перебором всех возможностей обречена на провал, если нас интересует эффективное решение задачи акономии памяти.
Необходимость общего рассмотрения. Прежде чем развивать менее тривиальный подход к поиску минимальных раскрасок, нам надо понятьл а нул«но лн рассматривать проблему в полной .всеобщности. При всей увлеченности очередной интересной математической задачей надо помнить, что в контексте нашего исследования раскраска верн»ин графа нам нужна не сама по себе, а как средство экономного распределения памяти. Может быть, графы несовместимости, получающиеся для операторных схем, обладают какими-нибудь специальными свойствами, которые мотли бы облегчить поиск минимальной раскраски.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
