有关基本图论定义与术语的知识老是记不清楚,这里做一个归纳:

图与网络(Graph and Network):

二元组(V,E)称为图(graph)。V为结点(node)顶点(vertex)集。E为V中结点之间的边的集合。

点对(u,v)称为边(edge)或称弧(arc),其中u,v属于V,称u,v是相邻的(adjacent),称u,v,与边(u,v)相关联(incident) 或相邻。

若边的点对(u,v)有序则称为有向(directed)边,其中u为头(head),v称为尾(tail),所形成的图称为有向图(directedgraph),意即--对于u来说,(u,v)是出边(outgoing arc),对于v来说,(u,v)为入边(incoming arc),反之,若边的点对无序则称为无向(undirected )边,所形成的图称为无向图(undirected graph).

若图的边有一个权值(weight) ,则称为赋权边,所形成的图称为赋权图(weighted graph)网络(network),用三元组G(V,|E,W)表示网络,其中W表示权集

它的元素与边集E--对应,在流网络中(flow network),权集W友记作C,表示容量(capacity)

图的术语(Glossary of Graph):

简单图(simp graph): 没有环,且没有多重弧的图称作简单图。

领域(neighborhood ):在图中与u相邻的点的集合{v|v属于V,(u,v)属于E},称为u的领域,记为N(u)。

度:

度(degree )一个顶点的度是指与该边相关联的边的条数,顶点v的度记作deg(v)或d.

握手定理:无向图:

入度(indegree ):在有向图中,一个顶点v的入度是指与该条边相关联的入边(即边的尾是v)的条数,记作deg+(v)。

出度(outdegree):在有向图中,一个顶点v的入度是指与该条边相关联的出边(即边的头是V)的条数,记作deg-(v)。

孤立点(isolated vertex):度为0 的点。

叶(leaf):度为1 的点。

源点(source ):有向图中,deg+(v)=0的点。

汇点(sink) :有向图中,deg-(v)=0的点。

子图

子图(sub-graph): G'称作图G的子图:

点导出子图(induced subgraph): 设V∝V(G),已V'为顶点集,以两段点均在V‘中的全体边为边集所组成的子图,称为G的有顶点集V’导出的子图,简称为点导出子图,称为G[V']。

点集的补集:记

特殊的图:

零图(null graph)即只有孤立点的图,n阶零图记为Nn。

二分图(bipartite graph):若图G的顶点集可以划分两个非空子集X和Y,即V=X∪Y且X∩Y=空集,且每一条边都有一个顶点在X中,而另一个顶点在Y中,那么这样的图称为二分图。

Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐