рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Хроматическое число - раздел Математика, При каких условиях вершины графа можно раскрасить так, чтобы каждое ребро было инцидентно вершинам разного цвета Пусть Граф G Петель, Тогда G – K – Раскрашиваемый, Если Каждой Его Вершине Мо...

Пусть граф 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), то он ρ-раскрашиваем.
Развернуть
Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

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

При каких условиях вершины графа можно раскрасить так чтобы каждое ребро было инцидентно вершинам разного цвета Хроматическое... Обобщение Если Т произвольное дерево с п вершинами то Pt К К К Если... РG К К К К К п...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Хроматическое число

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

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

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

Теоретико- множественное произведение: Понятие 2-выборки.
Пусть заданы 2 множеств (конечных или нет) Е, Е,...Е, причем Еi принадлежит Е, Еg принадлежит Е,…Еe принадлежит Е. Упорядоченная совокупность Рα=(Еi, Еg,…Ee)называется 2-выборной, и множество

Упорядочение 2-выборки
2-выборку, которая определена как Рα=(Ei, Eg,…Ee) и в которой порядок компонент фиксирован по определению, будем называть упорядоченной 2 –выборкой. Говорят, что 2 упорядоченный 2-выб

Неупорядоченные 2 – выборки.
Неупорядоченная 2-выборка не есть 2-выборка в смысле данного определения. Если в определении упорядоченной 2-выборки не учитывать порядок компонент, то приходим к неупорядоченной 2-выборке, которую

Производящая функция
Пусть ап, п принадлежит N – последовательность. Этой последовательности поставим в соответствии ряд по целым числам Z. F*(z)=a+az+az +…+az+… Предположим, что всегда су

Порядковая функция графа без контуров
Рассмотрим граф без контуровG=(E,R) и определим подмножества N0, N1,…, N2: N0=

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги