Графы и алгоритмы

Рационализация переборных алгоритмов

Разбить на страницы
Показывать лекцию целиком

Рационализация поиска наибольшего независимого множества

Известны различные приемы сокращения перебора при использовании описанной стратегии исчерпывающего поиска. Один из них основан на следующем наблюдении. Допустим, в графе $$G$$, для которого нужно найти наибольшее независимое множество, имеются две вершины $$a$$ и $$b$$, такие, что каждая вершина, отличная от $$b$$ и смежная с вершиной $$a$$, смежна и с вершиной $$b$$. Иначе говоря, $$V(a)-\{b\} \subseteq V(b)$$. Будем говорить в этом случае, что вершина $$b$$ поглощает вершину $$a$$. Если при этом вершины $$a$$ и $$b$$ смежны, то скажем, что вершина $$b$$ смежно поглощает вершину $$a$$. Вершину $$b$$ в этом случае назовем смежно поглощающей. Например, в графе, изображенном на рис. 11.1, вершина 2 смежно поглощает вершины 1 и 3. Вершины 5 и 6 в этом графе тоже являются смежно поглощающими.

(рис 11.1)

Теорема 1. Если вершина $$b$$ является смежно поглощающей в графе $$G$$, то $$\alpha (G-b)=\alpha (G)$$.

Доказательство. Допустим, вершина $$b$$ смежно поглощает вершину $$a$$ в графе $$G$$. Пусть $$X$$ - наибольшее независимое множество графа $$G$$. Если $$X$$ не содержит вершину $$b$$, то оно является наибольшим независимым множеством и в графе $$G-b$$, так что в этом случае $$\alpha (G-b)=\alpha (G)$$. Предположим, что множество $$X$$ содержит вершину $$b$$. Тогда ни одна вершина из множества $$V(b)$$ не принадлежит $$X$$. Значит, $$X$$ не содержит вершину $$a$$ и ни одну вершину из множества $$V(a)$$. Но тогда множество $$(X-\{ b\})\cup \{ a\}$$ тоже будет независимым, причем оно целиком содержится в графе $$G-b$$, а число элементов в нем такое же, как в множестве $$X$$. Значит, и в этом случае $$\alpha (G-b)=\alpha(G)$$.

Итак, если мы удалим из графа смежно поглощающую вершину $$b$$, то получим граф с тем же числом независимости. Так как новый граф является порожденным подграфом исходного графа $$G$$, то каждое наибольшее независимое множество нового графа будет наибольшим независимым множеством исходного. Этот прием называется "сжатием по включению". Исследование применимости и применение операции сжатия по включению к каждому встречающемуся подграфу требуют, конечно, дополнительных расходов времени (каких?), но могут привести к существенному сокращению дерева подзадач. Для некоторых графов задача о независимом множестве может быть решена с помощью одних только сжатий по включению. Таков, например, граф $$pK_{2}$$, и вообще любой лес. Действительно, любая вершина, смежная с листом, поглощает этот лист. Рассмотрим более широкий класс графов, для которых этот прием эффективен.

Хордальные графы

Граф называется хордальным (или триангулированным ), если в нем нет порожденных простых циклов длины $$\ge 4$$. Иначе говоря, в хордальном графе для каждого простого цикла длины 4 или больше имеется хотя бы одна хорда - ребро, не принадлежащее циклу, но соединяющее две вершины цикла.

Теорема 2. В любом непустом хордальном графе имеется смежно поглощающая вершина.

Доказательство. Пусть $$G$$ - непустой граф, в котором нет смежно поглощающих вершин. Докажем, что $$G$$ - не хордальный. Рассмотрим в нем простой путь $$P=x_{1},x_{2} \ldots x_{k}$$ наибольшей длины, не имеющий хорд, то есть ребер, соединяющих две вершины пути и не принадлежащих пути. Так как граф непустой, то $$k\ge 2$$. Рассмотрим вершину $$x_{k}$$. Так как она не поглощает вершину $$x_{k-1}$$, то существует вершина $$y\ne x_{k-1}$$, смежная с вершиной $$x_{k}$$, но не смежная с $$x_{k-1}$$. Вершина $$y$$ не принадлежит пути $$P$$, так как иначе ребро $$(x_{k}, y)$$ было бы хордой этого пути. Таким образом, последовательность $$P'=x_{1},x_{2}\ldots x_{k},y$$ является простым путем. Но длина этого пути больше, чем длина пути $$P$$, поэтому, в силу выбора пути $$P$$, у пути $$P'$$ должна существовать хорда. Такой хордой может быть только ребро вида $$(y,x_{i})$$, где $$i\le k-2$$. Пусть $$i$$ - наибольшее, при котором ребро $$(y,x_{i})$$ является хордой пути $$P'$$. Тогда последовательность $$y,x_{i},x_{i+1} \ldots x_{k},y$$ является циклом без хорд длины не менее 4.

Итак, для хордального графа наибольшее независимое множество можно найти с помощью одних только сжатий по включению. Нужно только находить смежно поглощающие вершины и удалять их из графа до тех пор, пока оставшийся граф не станет пустым. Множество оставшихся вершин и является наибольшим независимым множеством.

Рационализация алгоритма для задачи о раскраске вершин

В описанную схему решения задачи о раскраске можно включить тот же прием сжатия по включению, что и для задачи о независимом множестве. Небольшое отличие состоит в том, что теперь вершины $$a$$ и $$b$$ должны быть несмежны. Итак, пусть в графе $$G$$ имеются две несмежные вершины $$a$$ и $$b$$, такие, что $$V(a)\subseteq V(b)$$. Будем говорить, что вершина $$b$$ несмежно поглощает вершину $$a$$, а вершину $$a$$ называть несмежно поглощаемой. В графе на рис. 11.1 вершина 1 несмежно поглощает вершину 4, а вершина 3 - вершину 7.

Теорема 3. Если вершина $$a$$ является несмежно поглощаемой в графе $$G$$, то $$\chi (G-a)=\chi (G)$$.

Доказательство. Допустим, вершина $$a$$ несмежно поглощается вершиной $$b$$. Рассмотрим правильную раскраску графа $$G-a$$ в наименьшее число цветов. Применим эту же раскраску к графу $$G$$, окрасим вершину $$a$$ в тот цвет, который имеет вершина $$b$$. Так как вершина $$a$$ смежна только с такими вершинами, с которыми смежна $$b$$, то получится правильная раскраска графа $$G$$ в то же самое число цветов. Следовательно, $$\chi (G)=\chi (G-a)$$.

Как и для задачи о независимом множестве, для некоторых графов этот прием позволяет находить решение, совсем не прибегая к перебору. Допустим, вершина $$b$$ смежно поглощает вершину $$a$$ в графе $$G$$. Тогда в дополнительном графе $$\overline{G}$$, очевидно, вершина $$a$$ будет несмежно поглощать вершину $$b$$. Верно и обратное утверждение. Поэтому из теоремы 2 следует

Теорема 4. В любом графе, дополнительном к хордальному и не являющемся полным, имеется несмежно поглощаемая вершина.

Таким образом, для графов, дополнительных к хордальным, раскраска в минимальное число цветов может быть найдена с помощью одних только сжатий по включению. Оказывается, и для хордальных графов существует эффективное решение задачи о раскраске.

Установим сначала некоторые свойства хордальных графов. Подмножество множества вершин графа называется разделяющим множеством, если удаление всех этих вершин приводит к увеличению числа компонент связности. Таким образом, понятие разделяющего множества является обобщением понятия шарнира. Разделяющее множество называется минимальным, если оно не содержится в большем разделяющем множестве.

Теорема 5. В хордальном графе всякое минимальное разделяющее множество является кликой.

Доказательство. Допустим, что в некотором графе $$G$$ есть минимальное разделяющее множество $$X$$, не являющееся кликой. Это означает, что в $$X$$ имеются несмежные вершины $$a$$ и $$b$$. При удалении множества $$X$$ образуется не менее двух новых компонент связности. Пусть $$C_{1}$$ и $$C_{2}$$ - такие компоненты. Вершина $$a$$ смежна, по крайней мере, с одной вершиной в каждой из этих компонент. Действительно, если $$a$$ была бы не смежна, скажем, ни с одной из вершин компоненты $$C_{1}$$, то множество $$X-\{a\}$$ тоже было бы разделяющим, а это противоречит минимальности разделяющего множества $$X$$. То же относится к вершине $$b$$. Выберем в компоненте $$C_{1}$$ такие вершины $$x_{1}$$ и $$y_{1}$$, чтобы $$x_{1}$$ была смежна с вершиной $$a$$, $$y_{1}$$ - с вершиной $$b$$ и при этом расстояние между $$x_{1}$$ и $$y_{1}$$ в $$C_{1}$$ было минимальным (возможно $$x_{1} =y_{1}$$ ). Аналогично выберем $$x_{2}$$ и $$y_{2}$$ в компоненте $$C_{2}$$. Пусть $$P_{1}$$ - кратчайший путь из $$x_{1}$$ в $$y_{1}$$ в компоненте $$C_{1}$$, а $$P_{2}$$ - кратчайший путь из $$y_{2}$$ в $$x_{2}$$ в компоненте $$C_{2}$$ (каждый из этих путей может состоять из одной вершины). Тогда последовательность $$a,P_{1},b,P_{2},a$$ является простым циклом без хорд длины не менее 4. Следовательно, граф $$G$$ - не хордальный.

Вершина графа называется симплициальной, если множество всех смежных с ней вершин является кликой или пустым множеством.

Теорема 6. В любом хордальном графе имеется симплициальная вершина.

Доказательство. В полном графе любая вершина является симплициальной. Докажем индукцией по числу вершин $$n$$, что в любом хордальном графе, не являющемся полным, есть две несмежные симплициальные вершины. При $$n=2$$ это, очевидно, так. Пусть $$G$$ - хордальный граф с $$n$$ вершинами, $$n>2$$, не являющийся полным. Если $$G$$ несвязен, то, по предположению индукции, во всех компонентах связности есть симплициальные вершины. Допустим, что граф $$G$$ связен. Так как он не полный, то в нем есть разделяющее множество, а по теореме 5 есть разделяющая клика. Пусть $$C$$ - такая клика, $$A$$ и $$B$$ - две новые компоненты связности, появляющиеся при удалении из графа всех вершин клики $$C$$. Рассмотрим подграф $$G_{A}$$, порожденный множеством $$A\cup C$$. Если он полный, то в нем любая вершина симплициальна. Если же он не полный, то по предположению индукции в нем есть две несмежные симплициальные вершины. Хотя бы одна из этих двух вершин принадлежит множеству $$A$$. Итак, в любом случае в множестве $$A$$ имеется вершина $$a$$, являющаяся симплициальной в графе $$G_{A}$$. Окрестность вершины $$a$$ во всем графе $$G$$ совпадает с ее окрестностью в подграфе $$G_{A}$$. Следовательно, $$a$$ - симплициальная вершина графа $$G$$. Аналогично, в множестве $$B$$ имеется симплициальная вершина графа $$G$$ и она не смежна с вершиной $$a$$.

Существование симплициальных вершин можно использовать для создания эффективного алгоритма раскрашивания хордального графа в наименьшее число цветов. План такого алгоритма содержится в доказательстве следующей теоремы:

Теорема 7. Для любого хордального графа $$\chi (G)=\omega(G)$$.

Доказательство. Пусть $$G$$ - хордальный граф с $$n$$ вершинами и $$\omega (G)=k$$. Покажем, что граф $$G$$ можно правильно раскрасить в $$k$$ цветов. Найдем в нем симплициальную вершину и обозначим ее через $$x_{n}$$, а граф, полученный удалением этой вершины, через $$G_{n-1}$$. Этот граф тоже хордальный, значит, в нем тоже есть симплициальная вершина. Пусть $$x_{n-1}$$ - симплициальная вершина в графе $$G_{n-1}$$, а $$G_{n-2}$$ - граф, получаемый из него удалением этой вершины. Продолжая действовать таким образом, получим последовательность вершин $$x_{n},x_{n-1}\ldots x_{1}$$ и последовательность графов $$G_{n},G_{n-1}\ldots G_{1}$$ (здесь $$G_{n} =G$$ ), причем при каждом $$i$$ вершина $$x_{i}$$ является симплициальной в графе $$G_{i}$$, а граф $$G_{i-1}$$ получается из $$G_{i}$$ удалением этой вершины.

Допустим, что граф $$G_{i-1}$$ правильно раскрашен в $$k$$ цветов. Покажем, что вершину $$x_{i}$$ можно покрасить в один из этих цветов, сохраняя правильность раскраски. Действительно, $$x_{i}$$ - симплициальная вершина графа $$G_{i}$$, значит, множество $$C$$ всех смежных с ней в этом графе вершин является кликой. Так как при добавлении к множеству $$C$$ вершины $$x_{i}$$ тоже получается клика, а мощность наибольшей клики в графе $$G$$ равна $$k$$, то $$|C|\le k-1$$. Значит, для окрашивания вершин множества $$C$$ использовано не более $$k-1$$ цвета. Поэтому для вершины $$x_{i}$$ можно использовать один из оставшихся цветов.

Итак, каждый из графов $$G_{i}$$, а значит, и исходный граф $$G$$, можно правильно раскрасить в $$k$$ цветов. Отсюда следует, что $$\chi (G)\le \omega (G)$$. Обратное неравенство было установлено в предыдущей лекции.
Страницы:

Рационализация поиска наибольшего независимого множества

Известны различные приемы сокращения перебора при использовании описанной стратегии исчерпывающего поиска. Один из них основан на следующем наблюдении. Допустим, в графе $$G$$, для которого нужно найти наибольшее независимое множество, имеются две вершины $$a$$ и $$b$$, такие, что каждая вершина, отличная от $$b$$ и смежная с вершиной $$a$$, смежна и с вершиной $$b$$. Иначе говоря, $$V(a)-\{b\} \subseteq V(b)$$. Будем говорить в этом случае, что вершина $$b$$ поглощает вершину $$a$$. Если при этом вершины $$a$$ и $$b$$ смежны, то скажем, что вершина $$b$$ смежно поглощает вершину $$a$$. Вершину $$b$$ в этом случае назовем смежно поглощающей. Например, в графе, изображенном на рис. 11.1, вершина 2 смежно поглощает вершины 1 и 3. Вершины 5 и 6 в этом графе тоже являются смежно поглощающими.

(рис 11.1)

Теорема 1. Если вершина $$b$$ является смежно поглощающей в графе $$G$$, то $$\alpha (G-b)=\alpha (G)$$.

Доказательство. Допустим, вершина $$b$$ смежно поглощает вершину $$a$$ в графе $$G$$. Пусть $$X$$ - наибольшее независимое множество графа $$G$$. Если $$X$$ не содержит вершину $$b$$, то оно является наибольшим независимым множеством и в графе $$G-b$$, так что в этом случае $$\alpha (G-b)=\alpha (G)$$. Предположим, что множество $$X$$ содержит вершину $$b$$. Тогда ни одна вершина из множества $$V(b)$$ не принадлежит $$X$$. Значит, $$X$$ не содержит вершину $$a$$ и ни одну вершину из множества $$V(a)$$. Но тогда множество $$(X-\{ b\})\cup \{ a\}$$ тоже будет независимым, причем оно целиком содержится в графе $$G-b$$, а число элементов в нем такое же, как в множестве $$X$$. Значит, и в этом случае $$\alpha (G-b)=\alpha(G)$$.

Итак, если мы удалим из графа смежно поглощающую вершину $$b$$, то получим граф с тем же числом независимости. Так как новый граф является порожденным подграфом исходного графа $$G$$, то каждое наибольшее независимое множество нового графа будет наибольшим независимым множеством исходного. Этот прием называется "сжатием по включению". Исследование применимости и применение операции сжатия по включению к каждому встречающемуся подграфу требуют, конечно, дополнительных расходов времени (каких?), но могут привести к существенному сокращению дерева подзадач. Для некоторых графов задача о независимом множестве может быть решена с помощью одних только сжатий по включению. Таков, например, граф $$pK_{2}$$, и вообще любой лес. Действительно, любая вершина, смежная с листом, поглощает этот лист. Рассмотрим более широкий класс графов, для которых этот прием эффективен.

Хордальные графы

Граф называется хордальным (или триангулированным ), если в нем нет порожденных простых циклов длины $$\ge 4$$. Иначе говоря, в хордальном графе для каждого простого цикла длины 4 или больше имеется хотя бы одна хорда - ребро, не принадлежащее циклу, но соединяющее две вершины цикла.

Теорема 2. В любом непустом хордальном графе имеется смежно поглощающая вершина.

Доказательство. Пусть $$G$$ - непустой граф, в котором нет смежно поглощающих вершин. Докажем, что $$G$$ - не хордальный. Рассмотрим в нем простой путь $$P=x_{1},x_{2} \ldots x_{k}$$ наибольшей длины, не имеющий хорд, то есть ребер, соединяющих две вершины пути и не принадлежащих пути. Так как граф непустой, то $$k\ge 2$$. Рассмотрим вершину $$x_{k}$$. Так как она не поглощает вершину $$x_{k-1}$$, то существует вершина $$y\ne x_{k-1}$$, смежная с вершиной $$x_{k}$$, но не смежная с $$x_{k-1}$$. Вершина $$y$$ не принадлежит пути $$P$$, так как иначе ребро $$(x_{k}, y)$$ было бы хордой этого пути. Таким образом, последовательность $$P'=x_{1},x_{2}\ldots x_{k},y$$ является простым путем. Но длина этого пути больше, чем длина пути $$P$$, поэтому, в силу выбора пути $$P$$, у пути $$P'$$ должна существовать хорда. Такой хордой может быть только ребро вида $$(y,x_{i})$$, где $$i\le k-2$$. Пусть $$i$$ - наибольшее, при котором ребро $$(y,x_{i})$$ является хордой пути $$P'$$. Тогда последовательность $$y,x_{i},x_{i+1} \ldots x_{k},y$$ является циклом без хорд длины не менее 4.

Итак, для хордального графа наибольшее независимое множество можно найти с помощью одних только сжатий по включению. Нужно только находить смежно поглощающие вершины и удалять их из графа до тех пор, пока оставшийся граф не станет пустым. Множество оставшихся вершин и является наибольшим независимым множеством.

Рационализация алгоритма для задачи о раскраске вершин

В описанную схему решения задачи о раскраске можно включить тот же прием сжатия по включению, что и для задачи о независимом множестве. Небольшое отличие состоит в том, что теперь вершины $$a$$ и $$b$$ должны быть несмежны. Итак, пусть в графе $$G$$ имеются две несмежные вершины $$a$$ и $$b$$, такие, что $$V(a)\subseteq V(b)$$. Будем говорить, что вершина $$b$$ несмежно поглощает вершину $$a$$, а вершину $$a$$ называть несмежно поглощаемой. В графе на рис. 11.1 вершина 1 несмежно поглощает вершину 4, а вершина 3 - вершину 7.

Теорема 3. Если вершина $$a$$ является несмежно поглощаемой в графе $$G$$, то $$\chi (G-a)=\chi (G)$$.

Доказательство. Допустим, вершина $$a$$ несмежно поглощается вершиной $$b$$. Рассмотрим правильную раскраску графа $$G-a$$ в наименьшее число цветов. Применим эту же раскраску к графу $$G$$, окрасим вершину $$a$$ в тот цвет, который имеет вершина $$b$$. Так как вершина $$a$$ смежна только с такими вершинами, с которыми смежна $$b$$, то получится правильная раскраска графа $$G$$ в то же самое число цветов. Следовательно, $$\chi (G)=\chi (G-a)$$.

Как и для задачи о независимом множестве, для некоторых графов этот прием позволяет находить решение, совсем не прибегая к перебору. Допустим, вершина $$b$$ смежно поглощает вершину $$a$$ в графе $$G$$. Тогда в дополнительном графе $$\overline{G}$$, очевидно, вершина $$a$$ будет несмежно поглощать вершину $$b$$. Верно и обратное утверждение. Поэтому из теоремы 2 следует

Теорема 4. В любом графе, дополнительном к хордальному и не являющемся полным, имеется несмежно поглощаемая вершина.

Таким образом, для графов, дополнительных к хордальным, раскраска в минимальное число цветов может быть найдена с помощью одних только сжатий по включению. Оказывается, и для хордальных графов существует эффективное решение задачи о раскраске.

Установим сначала некоторые свойства хордальных графов. Подмножество множества вершин графа называется разделяющим множеством, если удаление всех этих вершин приводит к увеличению числа компонент связности. Таким образом, понятие разделяющего множества является обобщением понятия шарнира. Разделяющее множество называется минимальным, если оно не содержится в большем разделяющем множестве.

Теорема 5. В хордальном графе всякое минимальное разделяющее множество является кликой.

Доказательство. Допустим, что в некотором графе $$G$$ есть минимальное разделяющее множество $$X$$, не являющееся кликой. Это означает, что в $$X$$ имеются несмежные вершины $$a$$ и $$b$$. При удалении множества $$X$$ образуется не менее двух новых компонент связности. Пусть $$C_{1}$$ и $$C_{2}$$ - такие компоненты. Вершина $$a$$ смежна, по крайней мере, с одной вершиной в каждой из этих компонент. Действительно, если $$a$$ была бы не смежна, скажем, ни с одной из вершин компоненты $$C_{1}$$, то множество $$X-\{a\}$$ тоже было бы разделяющим, а это противоречит минимальности разделяющего множества $$X$$. То же относится к вершине $$b$$. Выберем в компоненте $$C_{1}$$ такие вершины $$x_{1}$$ и $$y_{1}$$, чтобы $$x_{1}$$ была смежна с вершиной $$a$$, $$y_{1}$$ - с вершиной $$b$$ и при этом расстояние между $$x_{1}$$ и $$y_{1}$$ в $$C_{1}$$ было минимальным (возможно $$x_{1} =y_{1}$$ ). Аналогично выберем $$x_{2}$$ и $$y_{2}$$ в компоненте $$C_{2}$$. Пусть $$P_{1}$$ - кратчайший путь из $$x_{1}$$ в $$y_{1}$$ в компоненте $$C_{1}$$, а $$P_{2}$$ - кратчайший путь из $$y_{2}$$ в $$x_{2}$$ в компоненте $$C_{2}$$ (каждый из этих путей может состоять из одной вершины). Тогда последовательность $$a,P_{1},b,P_{2},a$$ является простым циклом без хорд длины не менее 4. Следовательно, граф $$G$$ - не хордальный.

Вершина графа называется симплициальной, если множество всех смежных с ней вершин является кликой или пустым множеством.

Теорема 6. В любом хордальном графе имеется симплициальная вершина.

Доказательство. В полном графе любая вершина является симплициальной. Докажем индукцией по числу вершин $$n$$, что в любом хордальном графе, не являющемся полным, есть две несмежные симплициальные вершины. При $$n=2$$ это, очевидно, так. Пусть $$G$$ - хордальный граф с $$n$$ вершинами, $$n>2$$, не являющийся полным. Если $$G$$ несвязен, то, по предположению индукции, во всех компонентах связности есть симплициальные вершины. Допустим, что граф $$G$$ связен. Так как он не полный, то в нем есть разделяющее множество, а по теореме 5 есть разделяющая клика. Пусть $$C$$ - такая клика, $$A$$ и $$B$$ - две новые компоненты связности, появляющиеся при удалении из графа всех вершин клики $$C$$. Рассмотрим подграф $$G_{A}$$, порожденный множеством $$A\cup C$$. Если он полный, то в нем любая вершина симплициальна. Если же он не полный, то по предположению индукции в нем есть две несмежные симплициальные вершины. Хотя бы одна из этих двух вершин принадлежит множеству $$A$$. Итак, в любом случае в множестве $$A$$ имеется вершина $$a$$, являющаяся симплициальной в графе $$G_{A}$$. Окрестность вершины $$a$$ во всем графе $$G$$ совпадает с ее окрестностью в подграфе $$G_{A}$$. Следовательно, $$a$$ - симплициальная вершина графа $$G$$. Аналогично, в множестве $$B$$ имеется симплициальная вершина графа $$G$$ и она не смежна с вершиной $$a$$.

Существование симплициальных вершин можно использовать для создания эффективного алгоритма раскрашивания хордального графа в наименьшее число цветов. План такого алгоритма содержится в доказательстве следующей теоремы:

Теорема 7. Для любого хордального графа $$\chi (G)=\omega(G)$$.

Доказательство. Пусть $$G$$ - хордальный граф с $$n$$ вершинами и $$\omega (G)=k$$. Покажем, что граф $$G$$ можно правильно раскрасить в $$k$$ цветов. Найдем в нем симплициальную вершину и обозначим ее через $$x_{n}$$, а граф, полученный удалением этой вершины, через $$G_{n-1}$$. Этот граф тоже хордальный, значит, в нем тоже есть симплициальная вершина. Пусть $$x_{n-1}$$ - симплициальная вершина в графе $$G_{n-1}$$, а $$G_{n-2}$$ - граф, получаемый из него удалением этой вершины. Продолжая действовать таким образом, получим последовательность вершин $$x_{n},x_{n-1}\ldots x_{1}$$ и последовательность графов $$G_{n},G_{n-1}\ldots G_{1}$$ (здесь $$G_{n} =G$$ ), причем при каждом $$i$$ вершина $$x_{i}$$ является симплициальной в графе $$G_{i}$$, а граф $$G_{i-1}$$ получается из $$G_{i}$$ удалением этой вершины.

Допустим, что граф $$G_{i-1}$$ правильно раскрашен в $$k$$ цветов. Покажем, что вершину $$x_{i}$$ можно покрасить в один из этих цветов, сохраняя правильность раскраски. Действительно, $$x_{i}$$ - симплициальная вершина графа $$G_{i}$$, значит, множество $$C$$ всех смежных с ней в этом графе вершин является кликой. Так как при добавлении к множеству $$C$$ вершины $$x_{i}$$ тоже получается клика, а мощность наибольшей клики в графе $$G$$ равна $$k$$, то $$|C|\le k-1$$. Значит, для окрашивания вершин множества $$C$$ использовано не более $$k-1$$ цвета. Поэтому для вершины $$x_{i}$$ можно использовать один из оставшихся цветов.

Итак, каждый из графов $$G_{i}$$, а значит, и исходный граф $$G$$, можно правильно раскрасить в $$k$$ цветов. Отсюда следует, что $$\chi (G)\le \omega (G)$$. Обратное неравенство было установлено в предыдущей лекции.
Предыдущее занятие Следующее занятие
Вернуться к учебному плану
^