大部分内容摘自OIWIKI,为个人整理笔记
图是一个二元组 G=(V(G),E(G))。其中V(G)是非空集,称为点集(Vertex set),对于V中的每个元素,我们称其为顶点(Vertex)或节点(Node),简称点;E(G)为V(G)各结点之间边的集合,称为边集(Edge set)。
当一张图是简单图时可以用二元组进行定义,一张图 G 是一个二元组 (V,E),其中 V称为顶点集, E称为边集。它们亦可写成 V(G)和 E(G)。 E的元素是一个二元组数对,用 (x,y)表示,其中 x,y \in V。而当某张图为多重图时,则只能用三元组对其进行定义,一张图 G 是一个三元组 (V,E,I),其中 V称为顶集(Vertices set), E称为边集(Edges set), E与 V不相交; I称为关联函数, I将 E中的每一个元素映射到 V\times V。如果 I(e)=(u,v) (e\in E, u,v \in V)那么称边 e连接顶点 u,v,而 u,v则称作 e的端点, u,v此时关于 e相邻。同时,若两条边 i,j有一个公共顶点 u,则称 i,j关于 u相邻。
- 为什么多重图不能用二元组来表示?
当某张图为多重图时,图中存在自环与重边,二元组作为有序对定义时,是集合 V对集合 E的搜集,而若存在重边则会在二元组 (u,v)中出现重复元素(二元组中是允许出现重复元素的,但这里的重复元素出现在集合中所以是不被允许的),则不能用集合 E来表示所有与 V关联的边,因此需要引入一个新的关联函数 I。实际上可以将 E与 I看作一个新的二元组 (E,I),这样三元组也可以表示为 (V,(E,I))。
相关概念:类型论,有类型lambda运算,全序关系,多重集
Comments | 1 条评论
感谢博主的分享,支持了。