导出子图
在图论中，一个图的导出子图（）是指由该图顶点的一个子集和该图中两端均在该子集的所有边的集合组成的图。 定义 其正式定义为：设图 G=(V,E)，令 S\subset V，使得 是 的任意顶点子集。则 的导出子图 G[S] 中，其顶点集为 ，边集为 的边集 中两个顶点均属于 的边的集合。该定义适用于无向图，有向图与多重图。与子图（subgraph）的不同之处在于，导出子图中的两顶点间若在原图中有边，则导出子图中一定包含此边，而子图可包含或…
标签：#图论组成结构
共 5 篇文章
图标号
在图论的数学学科中，图标号（）是对图的边和/或顶点的编号（传统上用整数表示）进行赋值。 其正式定义为：给定图，顶点标号（Vertex labeling）是V 中一个标号集的函数。这样定义出来的函数图被称为顶点标号图（Vertex-labeled graph）。同样地，边标号（Edge labeling）是E中一个标号集的函数，其对应函数图被称为边标号图（Edge-labeled graph）。 当边标号是有序集（例如实数）的成员时，它可…
重边
在图论中，重边（Multiple edges，又称平行边或多重边）是两条或多条与同一对顶点相连接的边。简单图中没有重边。 根据上下文的不同，一个图可能被定义为允许或不允许拥有重边（通常与允许或不允许拥有自环一致）： 当允许重边与自环存在于图中时，多重图通常指没有自环的图。 当不允许重边与自环存在于图中时，多重图或伪图通常指允许重边和自环存在的图。 例如，从图论的观点来看，重边在研究电路时是有帮助的。此外，重边可体现出多维网络中核心差异的…
自环
在图论中，自环（Loop）是一条顶点与自身连接的边。简单图中不包含自环。 根据上下文的不同，一个图或者多重图可能被定义为允许或不允许拥有自环（通常与允许或不允许拥有重边一致）： 当允许重边与自环存在于图中时，没有重边或自环的图通常被称为“简单图”与图区分开。 当不允许重边与自环存在于图中时，含有重边或自环的图通常被称为“多重图”或“伪图”与图区分开。 在只有一个顶点的图中，所有的边都必须是自环。这种图叫花束图。 度 在无向图中，顶点的度…
完全点
: 在图论中，完全点（universal vertex）是一个在无向图中与其余所有顶点有连接的顶点。其又称作支配点（dominating vertex），因为它在图中形成了一个单元素支配集。 仅有一个完全点的图又称为椎体。在这种情况下，完全点称为椎体的顶点。然而，这个术语与顶点图中的术语相冲突，在顶点图中顶点若被删除，留下的子图为平面图。 特殊图类 星图正是树图中含有一个完全点的图，且星图可以由向独立集中添加一个完全点来构造。类似地，轮…