数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究顶点覆盖
覆盖图是一个子图，它包含所有顶点或与某个其他图对应的所有边。包含所有顶点的子图称为线/边覆盖。包含所有边的子图称为顶点覆盖。
设 'G' = (V, E) 为一个图。V 的一个子集 K 称为 'G' 的顶点覆盖，如果 'G' 的每条边都与 K 中的一个顶点关联或被 K 中的一个顶点覆盖。
示例
查看以下图形 -
从上图可以导出的子图如下 -
K1 = {b, c}
K2 = {a, b, c}
K3 = {b, c, d}
K4 = {a, d}这里，K1、K2 和 K3 有顶点覆盖，而 K4 没有顶点覆盖，因为它没有覆盖边 {bc}。
最小顶点覆盖
如果图 'G' 的顶点 'K' 不能删除任何顶点，则称其为最小顶点覆盖。
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
示例
在上图中，具有顶点覆盖的子图如下 -
K1 = {b, c}
K2 = {a, b, c}
K3 = {b, c, d}
这里，K1 和 K2 是最小顶点覆盖，而在 K3 中，可以删除顶点 'd'。
最小顶点覆盖
也称为最小的最小顶点覆盖。具有最少顶点数的图 'G' 的最小顶点覆盖称为最小顶点覆盖。
'G' 的最小顶点覆盖中的顶点数称为 G 的顶点覆盖数 (α2)。
示例
在下图中，具有顶点覆盖的子图如下 -
K1 = {b, c}
K2 = {a, b, c}
K3 = {b, c, d}
这里，K1 是 G 的最小顶点覆盖，因为它只有两个顶点。α2 = 2。
更新于: 2020年1月21日
233 次查看
广告