Lekcja – Graf dwudzielny
graph1 = [[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[1, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0]
]
graph2 = [[0, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0],
[0, 1, 0, 1, 0, 0],
[0, 0, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 1, 0]
]
graph3 = [[0, 1, 0, 0, 1],
[1, 0, 1, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 1, 0, 1],
[1, 0, 0, 1, 0]
]
def is_bipartite(graph):
color = [-1] * len(graph)
current_node = 0
color[current_node] = 1
queue = []
queue.append(current_node)
while queue:
current_node = queue.pop()
if graph[current_node][current_node] == 1:
return False
for neighbour in range(len(graph)):
if graph[current_node][neighbour] == 1 and color[neighbour] == -1:
color[neighbour] = 1 - color[current_node]
queue.append(neighbour)
elif graph[current_node][neighbour] == 1 and color[neighbour] == color[current_node]:
return False
return True
print(f'Graph1 - {is_bipartite(graph1)}')
print(f'Graph2 - {is_bipartite(graph2)}')
print(f'Graph3 - {is_bipartite(graph3)}')
Lab
net1 = {
0 : [1, 2, 6],
1 : [0, 3, 7],
2 : [0, 3, 4],
3 : [1, 2, 5],
4 : [2, 5, 6],
5 : [3, 4, 7],
6 : [0, 4, 7],
7 : [1, 5, 6]
}
net2 = {
0 : [1, 2, 6],
1 : [0, 3, 7],
2 : [0, 3, 4, 8],
3 : [1, 2, 5, 8],
4 : [2, 5, 6],
5 : [3, 4, 7],
6 : [0, 4, 7],
7 : [1, 5, 6],
8 : [2, 3]
}
net3 = {
0 : [1, 2, 6],
1 : [0, 3, 7],
2 : [0, 3, 4, 8],
3 : [1, 2, 5],
4 : [2, 5, 6],
5 : [3, 4, 7, 8],
6 : [0, 4, 7],
7 : [1, 5, 6],
8 : [2, 5]
}
def color_it(graph):
color = [-1] * len(graph)
current_node = 0
color[current_node] = 1
queue = []
queue.append(current_node)
while queue:
current_node = queue.pop()
if current_node in graph[current_node]:
return []
for neighbour in graph[current_node]:
if color[neighbour] == -1:
color[neighbour] = 1 - color[current_node]
queue.append(neighbour)
elif color[neighbour] == color[current_node]:
return []
return color
print(color_it(net1))
print(color_it(net2))
print(color_it(net3))