图的基本概念

图是由称为节点或顶点的点集以及由称为边的线连接的点集组成。图的研究，或图论，是数学、工程和计算机科学领域许多学科的重要组成部分。

图论

定义 − 图（表示为 G = (V, E)）由非空顶点集或节点 V 和边集 E 组成。顶点a表示边的端点。一条边连接两个顶点a, b，并由它连接的顶点集表示。

示例 − 让我们考虑一个图 G = (V, E)，其中 V = {a, b, c, d}，E = {{a, b}, {a, c}, {b, c}, {c, d}}

顶点的度 − 图 G 的顶点 V 的度（用 deg (V) 表示）是与顶点 V 关联的边的数量。

偶数顶点和奇数顶点 − 如果顶点的度是偶数，则该顶点称为偶数顶点；如果顶点的度是奇数，则该顶点称为奇数顶点。

图的度 − 图的度是该图中最大的顶点度。对于上面的图，图的度为 3。

握手引理 − 在一个图中，所有顶点的度之和等于边数的两倍。例如，在上述情况下，所有顶点的度之和为 8，总边数为 4。

Mahesh Parahar

更新于：2019年8月23日

4K+ 次浏览

启动您的职业生涯

通过完成课程获得认证

开始