Дан граф: G=V,E Граф G=V,E – математический объект, состоящий из двух множеств. Одно из них (множество

Дан граф: G=V,E Граф G=V,E – математический объект, состоящий из двух множеств. Одно из них (множество вершин VG) – любое конечное множество, его элементы называются вершинами графа: VG=1;2;3;4;5;6 число вершин: nG=6 Другое множество состоит из пар вершин, эти пары называются ребрами (множество ребер EG) графа, соединяющих пары вершин: EG=12;14;15;25;34;36;45;56 число ребер: mG=8 Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными: 12∩14∩15 для вершины 1 2;4;521∩25 для вершины 2 1;534∩36 для вершины 3 4;6 41∩43∩45 для вершины 4 1;3;551∩52∩54∩56 для вершины 5 1;2;4;663∩65 для вершины 6 3;5 Определить хроматическое число графа.

Хроматическое число. Это понятие относится к неориентированным графам.
Граф называют r-хроматическим, если его вершины можно раскрасить r-различными цветами так, что никакие две смежные вершины не будут закрашены в один цвет.
Наименьшее число r, для которого граф является r-хроматическим, называется хроматическим числом неориентированного графа и обозначается через χG.
Нужно выбрать вершину максимально связанную с другими, то есть имеющую наибольшую степень –для всех связанных с ней вершин ее цвет заведомо использоваться не может.
deg1=3
deg2=2
deg3=2
deg4=3
deg5=4→max
Вершина 5 окрашивается в «синий цвет – цвет 1».
Все вершины графа смежные с вершиной a, не могут быть окрашены в «синий цвет – цвет 1».
Затем возвращаемся к первой в списке неокрашенных вершин, имеющую наибольшую степень . Просматривается список вершин сверху вниз
deg1=3→max
deg2=2
deg3=2
deg4=3→max
Выберем верхнюю вершин 4:
Окрашиваем ее в «зеленый цвет – цвет 2»

. Просматривается список вершин сверху вниз
deg1=3→max
deg2=2
deg3=2
deg4=3→max
Выберем верхнюю вершин 4:
Окрашиваем ее в «зеленый цвет – цвет 2»