离散数学是什么？
定义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一定满足相异性条件，但反之不真。
收起
