"图"版本比较

TableOfContents

图的定义

图(Graph)G由两个集合V和E组成，记为G=(V, E)，其中：V是顶点的有穷非空集合，E是V中顶点偶对(称为边)的有穷集。

通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。

图中的结点之间是多对多的关系。

有向图：若图G中的每条边都是有方向的，则称G为有向图(Digraph)。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。

【例】<vi，vj>表示一条有向边，vi是边的始点(起点)，vj是边的终点。因此，<vi，vj>和<vj，vi>是两条不同的有向边。

【例】下面图中G1是一个有向图。图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为：

• V(G1)={v1，v2，v3} E(G1)={<v1，v2>，<v2，v1>，<v2，v3>}

attachment:G1.jpg

无向图：若图G中的每条边都是没有方向的，则称G为无向图(Undigraph)。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。

【例】无序对(vi，vj)和(vj，vi)表示同一条边。

【例】下面图中的G2和G3均是无向图，它们的顶点集和边集分别为：

• V(G2)={v1，v2，v3，v4} E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)}
• V(G3)={v1，v2，v3，v4，v5，v6，v7} E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)}

attachment:G2.jpg

attachment:G3.jpg

注意：在以下讨论中，不考虑顶点到其自身的边。即若(v1，v2)或<vl，v2>是E(G)中的一条边，则要求v1≠v2。此外，不允许一条边在图中重复出现，即只讨论简单的图。

图G的顶点数n和边数e的关系

• 若G是无向图，则0≤e≤n(n-1)/2。恰有n(n-1)/2条边的无向图称无向完全图(Undireet-ed Complete Graph)
• 若G是有向图，则0≤e≤n(n-1)。恰有n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。

注意：完全图具有最多的边数。任意一对顶点间均有边相连。

【例】上面图G2就是具有4个顶点的无向完全图。

图的边和顶点的关系

无向边和顶点关系：若(vi,vj)是一条无向边，则称顶点vi和vj互为邻接点(Adjacent)，或称vi和vj相邻接；并称(vi,vj)依附或关联(Incident)于顶点vi和vj，或称(vi，vj)与顶点vi和vj相关联。

【例】下图G2中：

• 与顶点v1相邻接的顶点是v2，v3和v4
• 关联于顶点v2的边是(v1，v2)，(v2，v3)和(v2，v4)　

有向边和顶点关系：若<vi，vj>是一条有向边，则称顶点vi邻接到vj，顶点vi邻接于顶点vj；并称边<vi，vj>关联于vi和vj或称<vi，vj>与顶点vi和vj相关联。

【例】在下图G1中，关联于顶点v2的弧是<v1，v2>，<v2，v1>和<v2，v3>。

无向图中顶点v的度(Degree)：无向图中顶点v的度(Degree)是关联于该顶点的边的数目，记为D(v)。

【例】上图G2中顶点v1的度为3

有向图顶点v的入度(In Degree)：有向图中，以顶点v为终点的边的数目称为v的入度，记为ID(v)。 【例】上图G1中顶点v2的人度为l

有向图顶点v的出度(Out Degree)：有向图中，以顶点v为始点的边的数目，称为v的出度，记为OD(v)

【例】上图G1中顶点v2的出度为2

有向图顶点v的度定义为该顶点的入度和出度之和，即D(v)=ID(v)+OD(v)。

【例】上图G1中顶点v2的人度为l，出度为2，则度为3。

无论有向图还是无向图，顶点数n、边数e和度数之间有如下关系： latex($$e=\frac{1}{2}\sum_{i=1}^nD(v_i)$$)

图的存储结构

图的遍历

图的应用