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

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

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

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

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

Пример: ρ

а в а

б

4 – хроматический и К≥4 – раскрашиваемый граф

Граф может иметь кратные ребра. Ясно, что Х( К п)=п

С другой стороны Х(6)=1, если G – вполне несвязный граф. Х(6)=2, если G – двудольный граф, отличный от вполне несвязного графа. Любое дерево, имеющее не менее 2-х вершин, является2-хроматическим.

Теорема 1:

Если наибольшая из степеней вершин графа G равна Р, то граф (ρ+1) – раскрашиваем

Док-во. По индукции. Пусть 6 – граф с п – вершинами. Если из него удалить производную вершину υ вместе с инцидентными ей ребрами, что в оставшемся графе будет и-1 вершин, причем, степени вершин не превосходят ρ. По предположению индукции этот граф (ρ+1) – раскрашиваем получается (ρ+1) – раскраска для G, если окрасить вершину υ цветом, отличные с ней вершины ( а их не более чем ρ).

Теорема 2:

(Брукс). Пусть наибольшая из степеней вершин графа G равна Р. Тогда G –P раскрашиваемый, за исключением тех случаев, когда:

1. G содержит в качестве компонента граф Кρ+1

2. Ρ=2 и цикл нечетной длин является компонент G

Теорема 3:

Любой планарный граф 5-раскрашиваем.

Гипотеза 4-х красок. Всякий планарный граф 4-раскрашиваем. Известно,

а) что всякий планарный граф, имеющий менее 52 вершин, 4-раскрашиваем

б) любой, не содержащий треугольников планарный граф 3-раскрашиваем. (теория Грега)

Теорема 4:

Пусть G-простой связный граф, не являющийся полным, если наибольшая из степеней его вершин равна ρ (ρ≥3), то он ρ-раскрашиваем.

? раскраска

Граф G – ребро К- раскрашиваем, если его ребра можно раскрасить К красками таким образом, что никакие 2 смежных ребра не окажутся одного цвета. Если граф G ребро К – раскрашиваем, но не являются ребро (К-1) раскрашиваем, то К хроматическое число (хроматический класс или хроматический индекс) графа G. Хе(G)=К

3

1 4

2 2 Х(G)=4

3 1 4

Ясно, что если наибольшая из степеней вершин графа G равна ρ, то Хе(G)≥ρ

Теорема 5:

(Визинг). Пусть в графе G, не имеющем петель, наибольшая из степеней вершин равна ρ, тогда ρ≤Хе(в)≤ρ+1. Пример, известно, что Хе(Сп)=2, если п – четно, Хе(Сп)=3, если нечетно.

Теорема 6:

Хе(Км,п)=ρ=мах( м,п). Хроматический класс любого двудольного графа равен ρ

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

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

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

Пусть имеется граф: .i____.g____k., то РG(К)=К(К-1)² , т.к. среднюю вершину можно окрасить К способами и каждую из концевых вершин (К-1) способами. Всего (К-1)² способов. п-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), то процесс закончится на …………… графах без ребер

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