独立集 编辑
独立集是图论中的概念。一个独立集是一个图中一些两两不相邻的顶点所形成的集合。换句话说，独立集



S


{\displaystyle S}

由图中若干顶点组成，且



S


{\displaystyle S}

中任两个顶点之间没有边。等价地，图中的每条边至多有一个端点属于



S


{\displaystyle S}

。一个独立集的基数是它包含顶点的数目。
1
相关
在图论中，是一类特殊的图，又称为、偶图、双分图。二分图的顶点可以分成两个互斥的独立集 U 和 V 的图，使得所有边都是连结一个 U 中的点和一个 V 中的点。顶点集 U、V 被称为是图的两个部分。等价的，二分图可以被定义成图中所有的环都有偶数个顶点。
在图论中，是一类特殊的图，又称为、偶图、双分图。二分图的顶点可以分成两个互斥的独立集 U 和 V 的图，使得所有边都是连结一个 U 中的点和一个 V 中的点。顶点集 U、V 被称为是图的两个部分。等价的，二分图可以被定义成图中所有的环都有偶数个顶点。
在数学的分支图论中，一个 k-分图是一个图，其点集被分成 k 部分，各部分各自形成独立集。换句话说，可以把图的所有点着色，使得相邻的点着不同色且总共用了k 个颜色。k = 2 的情况被称作二分图，而 k = 3 的情况被称作三分图。
在图论中，是一类特殊的图，又称为、偶图、双分图。二分图的顶点可以分成两个互斥的独立集 U 和 V 的图，使得所有边都是连结一个 U 中的点和一个 V 中的点。顶点集 U、V 被称为是图的两个部分。等价的，二分图可以被定义成图中所有的环都有偶数个顶点。