@iiilll01
###问题陈述
存在具有
N 个顶点和
M 条边的简单无向图。
图由顶点
1, 顶点
2,…, 顶点
N 组成,第
i 条边
(1≤i≤M) 连接顶点
u
i
和
v
i
。您将执行以下操作零次或多次:
-选择一个尚未删除的边,并将其删除。
你的目标是使图二分。找出在二部图运算后生成图所需的最少运算次数。
图表简单意味着什么?
一个图是简单的当且仅当它没有自环(
u
i
=v
i
的边)
或多条边(
u
i
=u
j
和
v
i
=v
j
的边对)。
什么是二部图?
二部图是可以将满足以下条件的每个顶点着色为黑色或白色的图:
-对于每个边缘,
由该边连接的两个顶点具有不同的颜色。###问题陈述有一个简单的无向图,它有
N 个顶点和
M 条边。
图由顶点
1, 顶点
2,…, 顶点
N 组成,第
i 条边
(1≤i≤M) 连接顶点
u_i 和
v_i 。您将执行以下操作零次或多次:-选择一个尚未删除的边,并将其删除。你的目标是使图二分。找出在二部图运算后生成图所需的最少运算次数。图表简单意味着什么?一个图是简单的当且仅当它没有自环(边,其中
u_i=v_i )或多边缘(
u_i=u_j 和
v_i=v_j 的边缘对)。什么是二部图?二分图是可以将满足以下条件的每个顶点着色为黑色或白色的图:-对于每条边,由该边连接的两个顶点具有不同的颜色。