一些特殊的图.doc

、二部图的定义若能将无向图G=<V,E>的顶点集V划分成两个子集V1和V2(V1∩V2=Æ>,使得G中任何一条边的两个端点一个属于V1,另一个属于V2,则称G为二部图(也称为偶图>.V1,V2称为互补顶点子集,此时可将G记成G=<V1,V2,E>,若|V1|=n,|V2|=m,则记完全二部图G为Kn,,(1>所示为K2,3,(2>所示为K3,,3是重要的完全二部图,=<V,E>、匹配设G=<V,E>为无向图,E*ÍE,若E*中任意两条边均不相邻,则称E*为G中的匹配(或边独立集>.若在E*中再加入任何1条边就都不是匹配了,则称E*,最大匹配中的元素(边>的个数称为G的匹配数,记为b1(G>,∈V(G>,若存在M中的边与v关联,则称v为M饱和点,否则称v为M非饱和点,若G中每个顶点都是M饱和点,:设G=<V1,V2,E>为一个二部图,M为G中一个最大匹配,若|M|=min{|V1|,|V2|},|V1|≤|V2|,|V1|=|V2|,:1、Hall定理:设二部图G=<V1,V2,E>,|V1|≤|V2|,G中存在从V1到V2的完备匹配当且仅当V1中任意k个顶点(k=1,2,…|V1|>、设二部图G=<V1,V2,E>,如果(1>V1中每个顶点至少关联t(t>0>条边。(2>V2中每个顶点至多关联t条边,“相异性条件”,“t条件”,满足t条件的二部图,,由条件(1>可知,(2>可知,这kt条边至少关联V2中的k个顶点,于是若G满足t条件,则G一定满足相异性条件,但反之不真。:物理组、化学组、、王、李、赵、:(1>张、王为物理组成员,张、李、赵为化学组成员,李、赵、陈为生物组成员。(2>张为物理组成员,王、李、赵为化学组成员,王、李、赵、陈为生物组成员。(3>张为物理组和化学组成员,王、李、赵、?、定义哥尼斯堡七桥问题:经过图中每条边一次且仅一次并且行遍图中每个顶点的通路(回路>,称为欧拉通路或欧拉迹(欧拉回路或欧拉闭迹>.存在欧拉回路的图,,,则通路为回路。若有两个奇度顶点,(具有欧拉回路>当且仅当G是连通的,