Lekcja – Problem 2 klik
def is_bipartite(graph, clique1, clique2):
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
clique1.append([i for i in range(len(graph)) if color[i] == 0 or color[i] == -1])
clique2.append([i for i in range(len(graph)) if color[i] == 1 or color[i] == -1])
return True
def can_be_divided_2clique(graph, clique1, clique2):
complement_graph = [[None] * len(graph) for i in range(len(graph))]
for i in range(len(graph)):
for j in range(len(graph)):
complement_graph[i][j] = (graph[i][j]+1) % 2 if i != j else 0
return is_bipartite(complement_graph, clique1, clique2)
# graph = [
# [0, 1, 1, 1, 0],
# [1, 0, 1, 0, 0],
# [1, 1, 0, 0, 0],
# [0, 1, 0, 0, 1],
# [0, 0, 0, 1, 0]
# ]
# D1 D2 P K Q H
graph = [[0, 1, 1, 0, 0, 0],
[1, 0, 1, 0, 0, 0],
[1, 1, 0, 1, 1, 1],
[0, 0, 1, 0, 1, 1],
[0, 0, 1, 1, 0, 1],
[0, 0, 1, 1, 1, 0]
]
clique1 = []
clique2 = []
if can_be_divided_2clique(graph, clique1, clique2):
print("Yes:")
print(clique1)
print(clique2)
else:
print("No")
Lab
g1 = [
[0,1,1,0,0,0,1,1],
[1,0,0,0,0,0,1,1],
[1,0,0,1,1,1,0,0],
[0,0,1,0,1,1,0,0],
[0,0,1,1,0,1,0,0],
[0,0,1,1,1,0,0,0],
[1,1,0,0,0,0,0,1],
[1,1,0,0,0,0,1,0]
]
g2 = [
[0,1,1,0,0,0,1,1],
[1,0,0,0,0,0,1,0],
[1,0,0,1,1,1,0,0],
[0,0,1,0,1,1,0,0],
[0,0,1,1,0,1,0,0],
[0,0,1,1,1,0,0,0],
[1,1,0,0,0,0,0,1],
[1,0,0,0,0,0,1,0]
]
def is_bipartite(graph, clique1, clique2):
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
clique1.append([i for i in range(len(graph)) if color[i] == 0 or color[i] == -1])
clique2.append([i for i in range(len(graph)) if color[i] == 1 or color[i] == -1])
return True
def can_be_divided_2clique(graph, clique1, clique2):
complement_graph = [[None] * len(graph) for i in range(len(graph))]
for i in range(len(graph)):
for j in range(len(graph)):
complement_graph[i][j] = (graph[i][j]+1) % 2 if i != j else 0
return is_bipartite(complement_graph, clique1, clique2)
clique1 = []
clique2 = []
if can_be_divided_2clique(g1, clique1, clique2):
print("Yes:")
print(clique1)
print(clique2)
else:
print("No")
clique1 = []
clique2 = []
if can_be_divided_2clique(g2, clique1, clique2):
print("Yes:")
print(clique1)
print(clique2)
else:
print("No")