如何定义连通的二分图？

Question

我知道什么是连通图 - "A graph is connected when there is a path between every pair of vertices"。但是我对如何定义连通的二分图持怀疑态度。以下是正确的吗？ "When every vertex in the first subset has a edge with every vertex in the second subset"

请评论。需要帮助！

Answer 1

连通二分图是满足以下两个条件的图：

1. 顶点可以分为两个不相交的集合 U 和 V（即 U 和 V 各自是独立的集合），这样图中的每条边都将 U 中的一个顶点连接到 V 中的一个顶点。
2. 每对顶点之间都有一条路径，不管它们在哪个集合中。

Is the following correct? "When every vertex in the first subset has a edge with every vertex in the second subset"

不，不是：

o----o
    / 
   /
  /
o----o

这是一个连通的二分图，不符合您的定义。