При каких условиях вершины графа можно раскрасить так, чтобы каждое ребро было инцидентно вершинам разного цвета

Проектирование графов.

При каких условиях вершины графа можно раскрасить так, чтобы каждое ребро было инцидентно вершинам разного цвета.

Хроматическое число

Если G – К – раскрашиваемый, но не является (К-1)-раскрашиваемым, то назовем его К - хроматическим, а число К – хроматическим числом графа G и…  

Раскраска

    1 4

Хроматические многочлены

Рассмотрим все возможные крайние случаи. Пусть имеется граф: .i____.g____k., то РG(К)=К(К-1)² , т.к. среднюю…

Обобщение. Если Т – произвольное дерево с п вершинами, то Pt(К)=К(К-1) . Если G -полный граф К3, то РG(К)=К*(К-1)(К-2); К4, то РG(К)=К(К-1)(К-2)(К-3), и т.д. Если Кп, то

РG(К)=К(К-1)(К-2)…(К-п+1).

Ясно, что если К<X(G), то РG(К)=0, если же К≥Х(G): РG(К)>0

Теорема 7:

Пусть G – простой граф, а V и W – его смежные вершины. Пусть G1 получены из G путем соединения ребром вершин V и W, а граф G2- путем отождествления вершин V и W (и кратных ребер, если они при этом получается). Тогда РG(К)= РG1(К)+ РG2(К).(2)

 

Пусть имеем граф:

i i

i

G: V W G1: V W G2:

(VW)

g g g

 

 

Док-во:

При любой допустимой раскраске вершин графа G либоV и W имеют разные цвета, либо они окрашены в один цвет. Число раскрасок при которых V и W имеют разные цвета не изменяются, если добавить ребро, соединяющее V и W, следовательно, оно равно РG1(К). Аналогично, число раскрасок, при которых V иW окрашены одним цветом, не изменится, если отождествлять V и W, следовательно оно равно РG2(К)

Следствие: Хроматическая функция графа есть многочлен.

Док-во:

Повторим процедуру описанную в Теореме 7, выбираем несмежные вершины в G1 и G2 и соединяя и отождествляя их, в результате получим 4 новых графа. Снова повторяем. Процесс заканчивается, когда каждый граф – полный.

 

Следствие теоремы 7:

Если L=(M,V) – ребро простого графа, то Р(G,К)=Р(G-L,K)-P(G*L,K),(1),. где G-L получается из G удаление ребра L, а G*L – замыкание вершин М и W и замена параллельных ребер одним ребром.

Если повторно применить формулу(2) и графу G, то процесс закончится на таких графах: Н1, Н2..,Нк, поэтому Р(G,K)=P(H1,п)+P(H2,п)+P(H4,п);

Если использовать формулу (1), то процесс закончится на …………… графах без ребер

хроматическим поленом множества комбинаций полиномов пустых графов.

 

Теорема Карона:

Граф G – 2-х раскрашиваемый тогда и только тогда, когда G – Эйлеров граф.

 

 

Некоторые оценки:

1) Нижние оценки

S(G)≥ρ(G),

S(G)≥п²/п²-2м, где п -число вершин, м –число ребер.

 

2) Верхние оценки

S(G)≤1+max ρ(xi)+1

Xi принадлежит Х

 

Алгоритм раскраски

Пусть множество вершин упорядочено и xi-xi-я вершины этого множества.

1) Окрасить Xi в цвет 1

2) Каждую из оставшихся вершин окрасить: Xi- в цвет с наименьшей возможной номером ( не использовать при окраске вершины, смежные с Xi).

Связь с задачей расписания

Пусть нужно выбрать время проведенное лекцией по разным принципам с учетом того, что…………………………………… и те, и другие. Строим граф, вершины его лягут по разным предметам, а ребра соединяют те пары лекций, которые не должны налагаться на одно и то же время.. Если каждому приемлемому для лекции времени сопоставить некоторый цвет, то раскраска - ……….

Теоретико- множественное произведение: Понятие 2-выборки.

Если Еi, Eg,…Ee –элементы Е, то будем обозначать 2 – выборки из Р следующим образом: Рα=(Ei, Eg,…Ee) Имеем 2-выборка не множество, а элемент теоретико – множественного произведения. В 2 – выборке каждый элемент…

Размещение. Сочетание.

Рассмотрим конечное множество Е с числом элементов |Е|=п и образует теоретико – множественное произведение Р=Е*Е*…*Е

Упорядочение 2-выборки

Говорят, что 2 упорядоченный 2-выборки Рα=(E, E,…E) и Р=(E, E,…E) равны их эквиваленты тогда и только тогда, когда Е =Е , Е =Е , и Е =Е… Упорядоченная 2-выборка называется также размещение из п элементов по 2…

Неупорядоченные 2 – выборки.

Говорят, что две неупорядоченные 2-выборки равны, или эквивалентны, если каждая из них состоит из одних и тех же элементов Е, взятых одно и то же… Неупорядоченная 2-выборка, сочетаемая из п элементов по 2(п=|Е|).. Пример. Пусть Е=(А,В,С,Д)

Пересчет. Перечисление. Классификация. Оптимизация.

Основная задача комбинаторики – изучение вопросов следующего типа о конечных множествах. Если мы интересуемся тем, сколько элементов, принадлежащих конечному множеству, обладает некоторым свойством или некоторой совокупностью свойств, то это задача - пересчета. Если же при этом интересоваться списком элементов, обладающих этим (этими) свойством, то переходим к задаче перечисления. Если пересчет приводит к слишком большим числам, то число встречается в комбинаторике, то отказывается от соответствующего перечисления и только классифицируют элементы с помощью какого – либо соотношения; это задача классификации. В некоторых задачах на множество решений можно ввести функцию величины, и эта функция приводит к полному упорядочению на этом множестве, тогда можно рассматривать понятия максимума и минимума и мы приходим к задаче оптимизации, которая формируется следующим образом: каково подлинное множество решений, для которого функция величины максимальна (минимальна) и и число соответствующее максимум (минимум).

А
В
С
Д
Е

Пример: Рассмотрим квадрат, разделенный на 25 клеток.

Пусть в эти клетки размещаются пять кружков в каждую

строку и в каждый столбец, в конечном счете попадает по

одному кружку. Каждой клетке (хi, хg) сопоставим двойку

(хi, хg), изображаемую стрелкой. Размещать кружки по

клеткам , им будет соответствовать диаграмма следующего

вида

 

Сколько разных размещений можно реализовать?

5! =120

 

Задача перечисления решена. Вынимаем некоторые из этих 120 решений.

((А,А), (В,В), (С,С), (Д,Д), (Е,Е)),

((А,В), (В,А), (С,С), (Д,Д), (Е,Е)),

------------------------------------------

((А,В), (В,С), (С,Д), (Д,Е),(Е,А))

Это и есть перечисление.

Пусть нас интересует число решений (возможно и их список), обладающих специальной структурой. Рассмотрим (1) и наведем контуром замкнутый путь на этой диаграмме. Она состоит из двух контуров длин 3 и 2 соответственно (длин – число строк, образующих контур). Интересной является задача распределения на классы контуров, имеющих одинаковую структуру, например, 5 контуров длин 1: А В С Д Е,

Три контура длины 1 и один контур длины 2: С Д Е В и т.д.

Отыскание числа таких качеств и их состава – важная комбинаторики задача.

	А	В	С	Д	Е
А
В
С
Д
Е

Предположим, что каждой клетке (Xi, Xg) сопоставима числовая функция, а каждому решению – величина, равная сумме этих чисел; найдем решение с минимальной величиной. Если функция величины задана , например,

 

То решение

 

Е А

 

 

Или имеем величину

 

 

Д С В

3+3+9+1+2=18 3+9+2+3+1=18

Оценивая решение с минимальной величиной, мы приходим к одному из 2-х решений, для которых эта величина равна 9

 

	А	В	С	Д	Е
А
В
С
Д
Е

	А	В	С	Д	Е
А
В
С
Д
Е

 

или

 

Методы перечисления основаны на понятиях производящей функции.

Производящая функция

Предположим, что всегда существует неотрицательное α, для которого │ап│<α, и в этом случае всякой последовательности ап… Вводятся также производящие функции вида f(z)=a +a +a z/2+…+a z/п +п,… f* и f допускает следующее обобщение φ*(z)=a φ (z)+a φ (z)+…+a φ(z)

Порядковая функция графа без контуров

N0=, Ǿ}, N1=-, },