Graph m coloring problem - Ostap2003/backtracking-team-project Wiki

Розфарбування графів

У теці m_coloring_problem знаходиться модуль graph_coloring.py, який містить клас Graph для знаходження розфарбування графа за його матрицею суміжності.

Ідея полягає в тому, щоб присвоювати кольори по одному різним вершинам. Перш ніж призначати колір, перевіряємо безпеку даного кольора для вже призначених кольорів суміжних вершин, тобто перевіряємо, чи мають сусідні вершини однаковий колір чи ні. Якщо існує призначення кольору, яке не порушує умови, то додаємо це присвоєння до часткового розв'язку. Якщо призначення кольору неможливе, то повертаємось назад і повертаємо false.

Що таке Розфарбування графа?

Розфарбуванням простого графа називають таке приписування кольорів (або натуральних чисел) його вершинам, що ніякі дві суміжні вершини не набувають однакового кольору.

Приклад використання:

>>> adj_matrix = [[0, 1, 1, 1],
                  [1, 0, 1, 0],
                  [1, 1, 0, 1],
                  [1, 0, 1, 0]]
>>> graph = Graph(adj_matrix)

>>> graph.get_graph_coloring(4)
>>> Solution for coloring current graph with 4 colors:
>>> [1, 2, 3, 2]

>>> graph.get_graph_coloring(1)
>>> Coloring current graph with 1 colors is impossible
>>> False