Skip to content

Instantly share code, notes, and snippets.

@AsyaMatveeva
Created September 4, 2022 10:45
Show Gist options
  • Save AsyaMatveeva/dfbc5d671e9045052dd2f7462640bcdb to your computer and use it in GitHub Desktop.
Save AsyaMatveeva/dfbc5d671e9045052dd2f7462640bcdb to your computer and use it in GitHub Desktop.
Naive algorithm for coloring a planar graph in 5 colors.
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