Проверьте наименьшее количество цветов, необходимое для раскраски графа (хроматическое число в 2-регулярном графе) - PullRequest
Новая
       32

Проверьте наименьшее количество цветов, необходимое для раскраски графа (хроматическое число в 2-регулярном графе)

0 голосов
/ 26 июня 2019

Моя задача - проверить наименьшее количество цветов, используемых при раскраске графа, которое является просто хроматическим числом графа.Мой неориентированный граф 2-регулярный (каждая вершина 2-градусная).Я нашел решение, что

(максимальное число независимых наборов) / количество вершин = количество цветов (хроматическое число)

https://imgur.com/a/ZtyP4v9 - как это выглядиткак

Как видите, он может быть 2-цветным, если результат 2 или 3-цветным, если результат больше 2.

Но я понятия не имею, как я мог найти максимумнезависимое множество в таком графе.

1 Ответ

1 голос
/ 26 июня 2019

2-регулярный граф - не более чем объединение непересекающихся циклов. Если любой из циклов имеет нечетную длину, то хроматическое число равно 3, в противном случае - 2. Это так просто. Вам не нужен алгоритм для этого.

...