基本图论定义与术语（Basic Definition and Glossary in Graph The）

2024-04-15 12:28:02　　点击量：

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

图与网络（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中，那么这样的图称为二分图。