Created
September 4, 2022 10:45
-
-
Save AsyaMatveeva/dfbc5d671e9045052dd2f7462640bcdb to your computer and use it in GitHub Desktop.
Naive algorithm for coloring a planar graph in 5 colors.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
G = {0:[1, 2, 3, 4, 5, 6], | |
1:[2, 0, 6], | |
2:[1, 0, 3], | |
3:[2, 0, 4], | |
4:[3, 0, 5], | |
5:[4, 0, 6], | |
6:[1, 0, 5] | |
} | |
deg_5 = [] #список вершин со степенями не больше пяти | |
for key, val in G.items(): | |
if len(val) <= 5: | |
deg_5.append(key) | |
is_end = False #флаг, сигнализирующий о наличии цикла нечётной длины | |
def dfs(G, coloring, c1, c2, current_v, v): | |
global is_end | |
if is_end: | |
return coloring | |
coloring[current_v] = c1 | |
for vertex in G[current_v]: | |
if vertex == v and coloring[v] == c1: | |
is_end = True | |
elif not is_end and coloring[vertex] == c1: | |
coloring = dfs(G, coloring, c2, c1, vertex, v) | |
return coloring | |
def graph_5_coloring(G, deg_5): | |
global is_end | |
if len(G) <= 5: #если вершин не больше пяти, то для покраски n вершин используем n цветов | |
coloring = {} | |
color = 0 | |
for key in G.keys(): | |
coloring[key] = color | |
color += 1 | |
return coloring | |
else: | |
v = deg_5[-1] #выбираем вершину степени не больше пяти | |
deg_5.pop() | |
adjacent = G[v] #cохраняем вершины, соединённые с v | |
for vertex in adjacent: | |
vertex = vertex | |
G[vertex].remove(v) | |
if len(G[vertex]) == 5: #обновление deg_5 | |
deg_5.append(vertex) | |
del G[v] | |
coloring = graph_5_coloring(G, deg_5) | |
G[v] = adjacent #после покраски графа с меньшим количеством вершин возвращаем v | |
deg_5.append(v) | |
for vertex in adjacent: | |
G[vertex].append(v) | |
colors = [coloring[k] for k in adjacent] #составляем список цветов, в которые покрашены соседи v | |
vertex_color = 0 | |
while vertex_color in colors and vertex_color < 5: | |
vertex_color += 1 | |
if vertex_color < 5: #если соседи v были покрашены в не более чем 4 цвета, то красим v в неиспользованный цвет | |
coloring[v] = vertex_color | |
return coloring | |
for c1 in [0, 4]: #ищем цвет, в который можно покрасить v | |
for c2 in [1, 2, 3]: | |
is_end = False | |
recoloring = dfs(G, coloring, c1, c2, v, v) | |
if not is_end: | |
return recoloring | |
coloring = graph_5_coloring(G, deg_5) | |
print(coloring) | |
#Проверяем: | |
correct_coloring = True | |
for key, val in G.items(): | |
for v in val: | |
if coloring[key] == coloring[v]: | |
correct_coloring = False | |
break | |
print("Coloring is correct:", correct_coloring) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment