二部图二部图完全二部图1二部图定义设无向图G=,若能将V划分成V1和V2(V1V2=V,V1V2=),使得G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图,记为,称V1和V2为互补顶点子集
又若G是简单图,且V1中每个顶点都与V2中每个顶点相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|
注意:n阶零图为二部图
2二部图的判别法定理无向图G=是二部图当且仅当G中无奇圈例下述各图都是二部图3欧拉图历史上的哥尼斯堡七桥问题是著名的图论问题
问题是这样的：18世纪的东普鲁士有个哥尼斯堡城，在横贯全城的普雷格尔河两岸和两个岛之间架设了7座桥，它们把河的两岸和两个岛连接起来（如图1）
每逢假日，城中居民进行环城游玩，人们对此提出了一个“遍游”问题，即能否有这样一种走法，使得从某地出发通过且只通过每座桥一次后又回到原地呢
4我们将图1中的哥尼斯堡城的4块陆地部分分别标以A，B，Ｃ，D，将陆地设想为图的结点，而把桥画成相应的连接边，这样图1可简化成图2
于是七桥“遍游”问题等价于在图2中，从某一结点出发找到一条回路，通过它的每条边一次且仅一次，并回到原来的结点
5定义1给定无孤立结点的图G，若存在一条经过G中每边一次且仅一次的回路，则该回路为欧拉回路
具有欧拉回路的图称为欧拉图
例如，给出如图3所示的两个图，容易看出，(a)是欧拉图，而(b)不是欧拉图
6下图中，(a)图的每个结点的度数都为４，所以它是欧拉图；(b)图不是欧拉图
但我们继续考察(b)图可以发现，该图中有一条路v2v3v4v5v2v1v5，它经过(b)图中的每条边一次且仅一次，我们把这样的路称为欧拉路
定理1连通图G是欧拉图的充要条件是G的所有结点的度数都是偶数
7定义2通过图G的每条边一次且仅一次的路称为图G的欧拉路
对于欧拉路有下面的判定方法
定理2连通图G具有一
