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

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

Пусть G – простой граф (без петель и циклов), пусть PG (K) – число способов, которыми можно окрасить вершины графа G, используя К красок и соблюдая условие: никакие две смежные вершины не должны иметь один и тот же цвет.

Пусть PG – хроматическая функция графа G.

Рассмотрим все возможные крайние случаи:

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

 

то PG (K)=K(K-1)2 , т.к. среднюю вершину можно окрасить К способами и каждую из концевых вершин (К-1)-способами. Всего К(К-1)2 способов.

Обобщение.

Если T- произвольное дерево с n вершинами, то Pt(K)=K(K-1)n-1.

Если G-полный граф K3,то PG(K)=K(K-1)(K-2); K4, то PG(K)=K(K-1)(K-2)(K-3) и т.д. Если Кn , то PG(K)= K(K-1)(K-2). . . . . (K-n+1).

Ясно, что если K<X(G), то PG(K)=0, если же K≥X(G):PG(K)>0.

Теорема 7. Пусть G-простой граф, а V и W- его смежные вершины.

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

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

 

По теореме: К (К-1)(К-2)2=К (К-1)(К-2)(К-3)+К(К-1)(К-2)

(К (К-1)(К-2)[K-3+1])=K(K-1)(K-2)2;)

Доказательство. При любой допустимой раскраске вершин графа G либо V и W имеют разные цвета, либо они окрашены в один цвет. Число раскрасок, при которых V и W имеют разные цвета не изменится, если добавить ребро, соединяющее V и W,следовательно оно равно PG1(K).Аналогично, число раскрасок, при которых V и W окрашены одним цветом , не изменится ,если отождествить V и W,следовательно оно равно PG2(K).(G1=G+l-граф полученный из G добавлением l; G2=G l- замыкание вершин V и W).

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

Доказательство.

Следствие из теоремы 7. Если l=(V,W)-ребро простого графа G, то P(G,K)=P(G-l,k)-P(G*l,k)(3),где… Если повторно применить формулу (2) к графу G, то процесс закончится на графах: Н1,Н2,. . . ,Нk,поэтому…

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

Пусть множество вершин угла вершины этого множества.

1)Окрасить хi в цвет 1.

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

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

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

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