Реферат Курсовая Конспект
Раскраска - раздел Математика, При каких условиях вершины графа можно раскрасить так, чтобы каждое ребро было инцидентно вершинам разного цвета Граф G – Ребро К- Раскрашиваем, Если Его Ребра Можно Раскрасить К Красками Та...
|
Граф G – ребро К- раскрашиваем, если его ребра можно раскрасить К красками таким образом, что никакие 2 смежных ребра не окажутся одного цвета. Если граф G ребро К – раскрашиваем, но не являются ребро (К-1) раскрашиваем, то К хроматическое число (хроматический класс или хроматический индекс) графа G. Хе(G)=К
3
1 4
2 2 Х(G)=4
3 1 4
Ясно, что если наибольшая из степеней вершин графа G равна ρ, то Хе(G)≥ρ
Теорема 5:
(Визинг). Пусть в графе G, не имеющем петель, наибольшая из степеней вершин равна ρ, тогда ρ≤Хе(в)≤ρ+1. Пример, известно, что Хе(Сп)=2, если п – четно, Хе(Сп)=3, если нечетно.
Теорема 6:
Хе(Км,п)=ρ=мах( м,п). Хроматический класс любого двудольного графа равен ρ
– Конец работы –
Эта тема принадлежит разделу:
При каких условиях вершины графа можно раскрасить так чтобы каждое ребро было инцидентно вершинам разного цвета Хроматическое... Обобщение Если Т произвольное дерево с п вершинами то Pt К К К Если... РG К К К К К п...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Раскраска
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов