一些特殊的图.ppt

第八章一些特殊的图§§§§§(偶图):若无向图G=<V,E>的顶点集V能划分成两个子集V1和V2,使得G中任何一条边的两个端点一个属于V1,另一个属于V2,则称G为二部图(偶图)。V1,V2称为互补顶点子集。§(完全偶图):若V1中任一顶点与V2中每个顶点均有且仅有一条边相关联,则称G为完全二部图(完全偶图)。若|V1|=n,|V2|=m,则记完全二部图G为Kn,mDate2离散数学二部图(续)K2,3K3,3一个无向图G=<V,E>是二部图当且仅当G中无奇数长度的回路。二部图判定定理Date3离散数学二部图(续)例1:判断下列图是否为二部图。v4v3v2v1v5v6v7v8同构于v4v3v2v1v5v6同构于v6v4v3v2v1v5v7v8v4v3v2v1v5v6Date4离散数学§(欧拉回路):经过图中每条边一次且仅一次并且行遍每个顶点的通路(回路),称为欧拉通路(欧拉回路)。欧拉图:存在欧拉回路的图。Date6离散数学欧拉图(续)(1)无向图G具有欧拉通路当且仅当G是连通图且有零个或两个奇数度顶点。欧拉图的判定定理:(2)无向图G是欧拉图(具有欧拉回路)当且仅当G是连通图且所有顶点的度数全为偶数。Date7离散数学欧拉图(续)欧拉图的判定定理:(4)有向图D是欧拉图(具有欧拉回路)当且仅当D是连通图,且所有顶点的入度等于出度。(3)有向图D具有欧拉通路当且仅当D是连通图,且除了两个顶点外,其余顶点的入度均等于出度。这两个特殊的顶点中,一个顶点的入度比出度大1,另一个顶点的出度比入度大1。Date8离散数学欧拉图(续)例2:判断下列图是否为欧拉图。fdbaecghijdbaecdbaec是欧拉图不是欧拉图,但有欧拉通路是欧拉图Date9离散数学§(哈密尔顿回路):经过图中每个顶点一次且仅一次的通路(回路),称为哈密尔顿通路(哈密尔顿回路)。哈密尔顿图:存在哈密尔顿回路的图。dbaecdbaecdbaecfDate10离散数学