Lekcja – Kolorowanie grafu

```# graph = [
#     [0,1,1,1,1],
#     [1,0,1,0,1],
#     [1,1,0,1,0],
#     [1,0,1,0,1],
#     [1,1,0,1,0]
# ]

# graph = [
#     [0,1,1,1],
#     [1,0,1,1],
#     [1,1,0,1],
#     [1,1,1,0]
# ]

graph = [
[0,1,1,0,0],
[1,0,1,1,0],
[1,1,0,1,0],
[0,1,1,0,1],
[0,0,0,1,0]
]

graph = [
[0,1,1,0,0],
[1,0,1,0,1],
[1,1,0,0,1],
[0,0,0,0,1],
[0,1,1,1,0]
]

color_names = ['red', 'green', 'blue', 'yellow', 'orange', 'black', 'white', 'gray']

number_of_colors = 3
colors =  [None for i in range(len(graph))]

def is_no_conflict(graph, vertex_idx, colors, color):
for i in range(len(graph)):
if graph[vertex_idx][i] == 1 and colors[i] == color:
return False
return True

def try_paint(graph, number_of_colors, colors, vertex_idx):

if vertex_idx == len(graph):
return True

for color in range(number_of_colors):
if is_no_conflict(graph, vertex_idx, colors, color):
colors[vertex_idx] = color
if try_paint(graph, number_of_colors, colors, vertex_idx + 1):
return True
colors[vertex_idx] = None

return False

result = try_paint(graph, number_of_colors, colors, 0)

if result:
print(f"Solution found: {colors}")
print([color_names[i] for i in colors])
else:

Lab

```family = {
'Ann' : ['John', 'Betty', 'Sophie'],
'Oliver' : ['Lucas','Sophie'],
'Sophie' : ['Ann', 'Oliver'],
'John' : ['Ann'],
'Betty' : ['Ann'],
'Lucas' : ['Oliver'],
'Emma' :[],
'Charlotte' : ['James'],
'James': ['Charlotte']
}

family = {
'Ann' : ['John', 'Betty', 'Sophie'],
'Oliver' : ['Lucas','Sophie'],
'Sophie' : ['Ann', 'Oliver'],
'John' : ['Ann', 'Betty'],
'Betty' : ['Ann','John'],
'Lucas' : ['Oliver'],
'Emma' :[],
'Charlotte' : ['James'],
'James': ['Charlotte']
}

number_of_tables = 3
assigments =  {name: None for name in family.keys()}

def is_no_conflict(family, person, assigments, proposed_assigment):
for v,e in family.items():
if v in family[person] and proposed_assigment == assigments[v]:
return False
return True

def try_assign_tables(family, number_of_tables, assigments):

# get first unassigned person from the family
person = None
for p in assigments.keys():
if assigments[p] == None:
person = p
break
# if all persons have already table assigment
if person == None:
return True

# try assign to table just one after another
for table_no in range(number_of_tables):
# if there is no conflict with the new assigment
if is_no_conflict(family, person, assigments, table_no):
assigments[person] = table_no
# try to continue with next assigments (keep in mind, we can fail...)
if try_assign_tables(family, number_of_tables, assigments):
return True
# if we failed, the assigment was a bad one and we need to take step back
assigments[person] = None

return False

result = try_assign_tables(family, number_of_tables, assigments)

if result:
print(f"Solution found: {assigments}")
else: