рефераты конспекты курсовые дипломные лекции шпоры
- Раздел Медицина
- /
- Хроматические многочлены
Реферат Курсовая Конспект
Хроматические многочлены
Хроматические многочлены - раздел Медицина, Хроматические Многочлены. Пусть G – Простой ...
Хроматические многочлены.
Пусть 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 ).
Связь с задачей расписание.
Пусть нужно выбрать время проведения лекций по разным предметам с учетом того, что студенты желают посещать и те, и другие.
Строим граф. Вершина его - лекции по разным предметам, а ребра соединяют те пары лекций, которое не должны назначаться на одно и то же время.
– Конец работы –
Используемые теги: Хроматические, Многочлены0.05
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Хроматические многочлены
Что будем делать с полученным материалом:
Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:
| Твитнуть |
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Реклама
Информация в виде рефератов, конспектов, лекций, курсовых и дипломных работ имеют своего автора, которому принадлежат права. Поэтому, прежде чем использовать какую либо информацию с этого сайта, убедитесь, что этим Вы не нарушаете чье либо право.
© copyright 1999 - 2024 allRefs.net. Все права защищены. Страница сгенерирована за: 0.116 сек.
Новости и инфо для студентов