Реферат Курсовая Конспект
Доказательство. - раздел Медицина, Хроматические многочлены Повторим Процедуру, Описанную В Теореме 7,выбирая Несмежные Вершины В G1...
|
Повторим процедуру, описанную в теореме 7,выбирая несмежные вершины в G1 и G2 соединяя и отождествляя их, в результате получим 4 новых графа. Снова повторяем. Процесс заканчивается, когда каждый граф- полный.
Следствие из теоремы 7.
Если l=(V,W)-ребро простого графа G, то P(G,K)=P(G-l,k)-P(G*l,k)(3),где G-l-получается из G удалением ребра l, a G*l- замыкание вершин V и W и замена параллельных ребер одним ребром.
Если повторно применить формулу (2) к графу G, то процесс закончится на графах: Н1,Н2,. . . ,Нk,поэтому P(G,K)=P(H1,k)+P(H2,k)+. . .+P(Hk,k);
Если использовать формулу (3), то процесс закончится на пустых графах без ребер => хроматический полином – множество комбинаций полиномов пустых графов.
Теорема Карона.
Граф G – двух раскрашиваемый тогда и только тогда, когда G- Эйлеров граф.
1)нижние оценки:
γ(G)≥ρ(G),
γ(G)≥, где n-число вершин
m- число ребер.
2)верхние оценки:
γ(G)≤1+max[P(xi)+1]
xi Є x
– Конец работы –
Эта тема принадлежит разделу:
Пусть G простой граф без петель и циклов пусть PG K число способов которыми можно окрасить вершины графа G используя К красок и соблюдая... Пусть PG хроматическая функция графа G... Рассмотрим все возможные крайние случаи...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Доказательство.
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов