1:26
它可以被分成两个部分 所有的边都跨两边，
这么一个性质。 二部图这两个部分的大小可以一样也可以不一样
特别值得一提的是呢，
有些图 它看起来不是二部图，
但实际上是二部图。 因为它们的节点可以被分成两组，
这个可以很重要。 可以被分成两组
满足刚才说的性质。比方说图A
它看起来不是二部图， 但是如果我们把 1,3,算一组，
2,4，算一组就可以把它 看成这个样子， 那么我们就有两组了。
我们看到原来这些边， 都是在两组之间。
这个就， 我们就，体会了我们前面说过的
一个观念。那就是一个图，可能被画成各种不同的样子。
但是只要它们的结构保持一致， 那么它们实际上就是同一个图。
在这个几个例子中， 我们看看这个图C。看这个图C怎么样。
图C， 它不是一个二部图。不管你怎么弄，你也没办法把它的节点
分成两组。满足我们刚才说的二部图的性质。
图D呢， 我们看看
看起来好像也不是。但是只要我们稍微注意一下，我们就发现，如果我们把
节点1，节点3，节点5 算作一组。
2,4,6,算做另外一组。那么这个图就可以被画成
重新画成现在这个样子。我们就看到， 它也是
被分成两组， 所有的边只是跨在两组之间
那么， 当看到一个图，如何判断它是二部图呢?
上面这些简单的例子容易直接看出来 但是，
面对一个比较复杂的图， 怎么判断它是二部图呢？比方我们现在看的两个图
我们就一眼， 我们很难 来说， 是不是能够把它的
这些个节点分成两部分， 使得这个每个部分 内部没有边，
这边都在两部分之间。为此，我们看几个简单的情况，
看从中能不能得到一点启发。 第一个情况就是由3个节点，
3条边勾成的图， 这样的呢， 我们管它叫
一个长部为三的圈。 那么我们看看能不能有办法把这样一个图的三个节点
安排成两组满足我们刚刚说的要求。
假定说我们从1开始，从1开始。1 放在左边，
2放在什么地方？ 2 只能放在右边。应为1和2
之间有个边。我们的边是跨两边 不能是同一个组内。
那么这个时候3要放在什么地方呢？我们就很难知道这个3， 3 现在该怎么办？ 3
不好放了。如果放在左边， 它和1之间是有边的。
造成了问题。放在右边也不行， 它和2之间是有边的，所以它没地儿放。所以我们就说这样一个图
这样一个图没有办法画成这样一个形式，
也就是说它不是一个二部图。
下面看第二个例子。 第二个例子，
长度为四个圈。 我们看看这个1放这个地方。
二只能放另一边。3 怎么办？ 3
看起来应该放这边。放这边不行。 你看看，
3 如果放在1边， 不行的， 我们只有放在跟2一边。 放这边是可以的。你看这个，
它是可以。 这个1 和3 有边， 那是没问题。那么4这个时候就放在右边。
4和3 有边， 4 和2 有边。
我们相当于就把这个图变成了我们希望看到的一个形式， 满足我们所说的性质。
下面看这个长度为5的这样一个圈。
我们看1可以放这边。2 该放什么地方？ 2该放这里， 有个边。3
该放什么地方？ 3 只能放这儿。 对不对， 相反的。4该放什么地方？
4 只能放这儿。 好，
放完了以后 我们， 看看这5， 5
怎么办？ 5 现在看起来没地儿可放。因为它如果放左边
它跟1有个边。这是冲突。 放右边它和2有个边， 这也是冲突。
所以我们说这个图也不是个二部图。那么这3个里头，
这个图也不是二部图，那么，这三个图中，只有中间这个是二部图。刚才这个过程实际上给了我们一个启发。
就是这样。一个图是不是二部图
就要看它里头
圈的长度的奇偶数。 如果里头有一个长度为奇数的圈
也就意味着它没办法把它有关的接点分成我们这两部分，满足我们所说的性质。
这就是我们从这几个例子能够得到的启发。得到的结论。
可是， 怎么判断
一个图是不是包含长度， 是不是包含有长度奇数的圈呢？
简单情况也是容易看， 复杂情况也是有点费劲的。
比方说我们看左边那个图。左边这个图包含很国圈。
比方说，我们说这算一个圈，这算一个圈，这个长度为偶数，
是这个，4。比方说我们还可以看看这个。 看看这个大的。这个大的。
这是个偶数。我们的问题是，我们能不能找到
一个长度为奇数的圈。
你看，这个地方有一个。这也不是啊，
这个长度为偶数， 有4个节点。 看起来三角形，实际上4个节点。
但是我们仔细看看这中间还真有一个长度为奇数的圈。这个长度是5。
也就是说它相关的5个接点是没办法安排成我们两部分那种形式。
所以这个图我们就判断说它不是一个二部图。
一般来说我们也需要有个办法来判断一个图是不是有长度为奇数的圈。
计算机科学给我们提供了一个方法。
这个方法叫做图上的广度优先搜索。或者叫
图上的广度优先遍历。 它的基本要点是从一个节点开始，
从任何一个节点开始， 沿着相连的边。
将图的节点一一列举出来这么一个过程。在这个过程中就能够发现，我们希望发现
或者说发现不了我们希望发现的情况。我们已下面这个图为例。
下面这个图为例。从一个节点开始，
比方我们就从F开始。什么叫广度优先搜索呢，
第一步就是要把和它直接相连的邻居， 把它连起来。比方说 这个是G， 这还有一个H,
这是直接和F有关系的。 列出来。 其它的， 还有那么些接点，
都跟它没有直接的关系。 那我们以后再说。紧接着我们就要看
和这个G和H 直接有关系的节点。那么有几个呢？
有一个I，还有一个J，有一个I，有一个J， 那么还有一个M
还有一个L。 我们注意了，我们现在就讲连接关系。
我们有这样的一个情况。
有I, J, L,M。这个H 当然还跟J是有关系的。
最后一个我们看到就是这个K。K是最后一个。 K 跟 I 有关系。
这样一个做法就叫广度优先搜索的做法。
那么它对我们求这个长度为奇数的圈有什么帮助呢？
我们注意到这样一个过程实际上将这个图的节点分成了 层。
比方说这是第零层， 就F自己。 这叫第一层，
包括两个节点。这个叫第二层， 包括4 个节点。 这个叫第三层。
在这个搜索过程中它有四个层次的节点。把它做了重新安排。
我们注意到所有的边， 现在看， 现在画出来的边
都是在层之间的相邻的两个层之间的。
那么我们仔细看看我们漏掉一条边
就是这中间的一条边。这个边我们刚刚漏了。这个边应该是在这儿的。 对于这样一条边
我们叫层内边。
而且我们能够意识到，如果任何层内有一条边，
那就意味着这个图中存在着一个长度为奇数的圈
比方说这就是， 因为这个边可以往上走
走到它们这两个相关节点的共同节点，导致这么一个圈，那一定就是一个长度为奇数的圈。
对应着这么一个圈。
这个事情可以从任何一个节点开始。
比方我们再换一个节点开始。 我们有一个I，从I开始。
紧跟着I 的是G, K。
我们从任何一个节点都可以来做这个事情。
第二层是什么呢？有这么几个 这有3
个， F, J, L G, J,
K 和 G 都连接。L 就连这个。 还有没有呢，
那么第二层。 第三层是H
还有一个M。H 连到的是F,
还连到J 这个还有L
这个M 呢 只是连到L。我们又发现这4个层次
零层，1层，2层， 3 层， 我们发现这中间又有一条边。 这条边，
现在是对应着这个。不管怎们样它在这里面是层内的一条边。
凡是层内有一条边，
那就意味这这个图中一定存在一个长度为奇数的圈。
这个办法就告诉我们从任何节点开始
在广度优先搜索的这么一个过程中， 一旦发现同一层的节点的之间有边
那么图中就一定存在长度为奇数的圈。也就是说这个图就一定不会是一个二部图。
这一段里 小结，
我们说许多社会现象或者状态的结构都呈现出二部图的形式
那么怎么判断一个图是不是二部图呢， 就是要看他里头是不是有长度为奇数的圈。
有就不是， 没有就是。
广度优先搜索是考察一个图是不是长度为奇数圈的有效方法。
李晓明 （Li Xiaoming）教授（Professor）
邱泽奇 （Qiu Zeqi）教授 (Professor)
王卫红（Wang Weihong）lecturer
