离散数学是什么?
定义1:
若能将无向图G= 的顶点集V划分成两个子集 V1和V2(V1交V2为空集),使得G中任何一条边的两个端点一个属于V1,另一个属于V2,则称G为二部图(也称偶图),V
1、V2称为互补顶点子集,此时可将G记成G= 。
若V1中任一顶点与V2中每一个顶点均有且仅有一条边相关联,则称二部图G为完全二部图(或完全偶图)。
定理1:
一个无向图G=是二部图当且仅当G中无奇数长度的回路。
定义2:
设G=为无向图,E*属于E,若E*中任意两条边均不相邻,则称E*为G中的匹配(或边独立集)。 若在E*中再加入任何1条边就都不是匹配了,则称E*为极大匹配。边数最多的极大匹配称 最大匹配,最...全部
定义1:
若能将无向图G= 的顶点集V划分成两个子集 V1和V2(V1交V2为空集),使得G中任何一条边的两个端点一个属于V1,另一个属于V2,则称G为二部图(也称偶图),V
1、V2称为互补顶点子集,此时可将G记成G= 。
若V1中任一顶点与V2中每一个顶点均有且仅有一条边相关联,则称二部图G为完全二部图(或完全偶图)。
定理1:
一个无向图G=是二部图当且仅当G中无奇数长度的回路。
定义2:
设G=为无向图,E*属于E,若E*中任意两条边均不相邻,则称E*为G中的匹配(或边独立集)。
若在E*中再加入任何1条边就都不是匹配了,则称E*为极大匹配。边数最多的极大匹配称 最大匹配,最大匹配中的元素(边)的个数称为G的匹配数。
设M为G中一个匹配。v属于V(G),若存在M中的边与v关联, 则称v为M饱和点,否则称v为M非饱和点。
若G中每个顶点都是M饱和点,则称M为G中完美匹配。
定义3:
设G=为一个二部图,M为G中一个最大匹配,若|M|=min{|V1|,|V2|},则M为G中一个完备匹配,此时若|V1|0)条边; 2,V2中每个顶点至多关联t条边,则G中存在V1到V2的完备匹配。
Hall定理中的条件为“相异性条件”,定理3中的条件为“t条件”。 满足t条件的二部图,一定满足相异性条件,事实上,由条件
(1)可知,V1中k个顶点至少关联 kt条边。由条件
(2)可知,这 kt条边至少关联V2中的k个顶点,于是若G满足t条件,则G一定满足相异性条件,但反之不真。
收起