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

Раздел Электротехника
/
Теорема

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

Выберите учебное заведение

Теорема

Теорема - раздел Электротехника, Раскраска графа. Хроматические полиномы. Алгоритм раскраски Хроматический Полином. Р(G,...

Хроматический полином. Р(G,) графа G на вершинах имеет степень n с главным членом

и const.=0 Все коэффициенты целые и чередуются …….

Пусть граф G с n вершинами и m рёбрами. е – ребро G .Тогда G- е -граф на n вершинах с m-1 рёбрами , а G* е - граф на n-1 вершинах с m-1 или менее рёбрами.

Оценки:

Нижние:

Верхние оценки:

Алгоритм раскраски

Пусть множество вершин упорядочено и -я вершина этого множества

окрасить в цвет 1
Каждую из оставшихся вершин окрасить : в цвет с наименьшим возможным номером ( не используя при окраске вершин смежной с .

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

4-хроматический граф, цвета ()

Развернуть

Открыть в широком формате

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

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

Раскраска графа. Хроматические полиномы. Алгоритм раскраски

Вершинная К раскраска графа присвоения его вершинам К различных цветов...

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

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

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

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

Теорема
Простой граф G –() раскрашиваемый (

Следствие
Если е(U,V)- ребро простого графа G, то Р(G,)= Р(G+е,

Гипотеза 4-х красок
Всякий планарный граф 4-раскрашиваемый. I. Всякий планарный граф, имеющий менее 52 вершин -4раскрашиваемый II. Любой, не содержащий треугольников планарный граф 3-раскрашиваемый

Теорема Визинга
Пусть G –простой граф, а V и W – его несмежные вершины. Пусть граф получается из G путём соединения ребром вер