Хроматические многочлены - раздел Математика, При каких условиях вершины графа можно раскрасить так, чтобы каждое ребро было инцидентно вершинам разного цвета Пустьg – Простой Граф, Пусть Рg(К) – Число Способов, Которым Можно Окрасить В...
ПустьG – простой граф, пусть РG(К) – число способов, которым можно окрасить вершины графа G, используя К красок и соблюдая условие: никакие 2 смежные вершины не должны иметь один и тот же цвет. Пусть РG -хроматическая функция графа G.
Рассмотрим все возможные крайние случаи.
Пусть имеется граф: .i____.g____k., то РG(К)=К(К-1)² , т.к. среднюю вершину можно окрасить К способами и каждую из концевых вершин (К-1) способами. Всего (К-1)² способов. п-1
При каких условиях вершины графа можно раскрасить так чтобы каждое ребро было инцидентно вершинам разного цвета Хроматическое... Обобщение Если Т произвольное дерево с п вершинами то Pt К К К Если... РG К К К К К п...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Хроматические многочлены
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Хроматическое число
Пусть граф G петель, тогда G – K – раскрашиваемый, если каждой его вершине можно приписать один из К цветов, так чтобы никакие 2 смежные вершины не оказались одного цвета.
Если G – К – рас
Раскраска
Граф G – ребро К- раскрашиваем, если его ребра можно раскрасить К красками таким образом, что никакие 2 смежных ребра не окажутся одного цвета. Если граф G ребро К – раскрашиваем, но не являются ре
Теоретико- множественное произведение: Понятие 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+…
Предположим, что всегда су
Новости и инфо для студентов