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))```