图论基础溯源

发布于 2021-07-23  12 次阅读


大部分内容摘自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), EV不相交; I称为关联函数, IE中的每一个元素映射到 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。实际上可以将 EI看作一个新的二元组 (E,I),这样三元组也可以表示为 (V,(E,I))

相关概念:类型论有类型lambda运算全序关系多重集