图

在數學上，一个图（Graph）是表示物件與物件之間的關係的方法，是圖論的基本研究對象。一個圖看起來是由一些小圓點（稱為頂點或結點）和連結這些圓點的直線或曲線（稱為邊）組成的。

定義

圖又有各種變體，包括簡單圖/多重圖;有向圖/無向圖等，但大體上有以下兩種定義方式。

二元組的定義

图$G$是一個二元组$(V,E)$，其中$V$称为顶點集，$E$称为边集。它們亦可寫成$V(G)$和$E(G)$。 $E$的元素是一個二元組數對，用$(x,y)$表示，其中$x,y \in V$。

三元組的定義

一个图，是指一个三元组$(V,E,I)$，其中$V$称为顶集（Vertices set），$E$称为边集（Edges set），$E$与$V$不相交；$I$称为关联函数，$I$将$E$中的每一个元素映射到$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$相邻。

分類

有/無 向图

如果给图的每条边规定一个方向，那么得到的图称为有向图，其邊也稱為有向邊。在有向图中，与一个节点相关联的边有出边和入边之分，而與一個有向邊關聯的兩個點也有始點和終點之分。相反，邊沒有方向的圖稱為無向圖。

简单图

一个图如果

1. 没有兩條邊，它們所關聯的兩個點都相同（在有向图中，没有兩條邊的起點終點都分別相同）；
2. 每條邊所關聯的是兩個不同的頂點

则称为简单图（Simple graph）。簡單的有向圖和無向圖都可以使用以上的「二元組的定義」，但形如$(x,x)$的序對不能屬於E。而無向圖的邊集必須是對稱的，即如果$(x,y)\in E$，那么$(y,x)\in E$。

多重圖

若允許兩結點間的邊數多於一條，又允許頂點通過同一條邊和自己關聯，則為多重圖的概念。它只能用「三元組的定義」。

基本术语

在頂點1有一個環

• 阶（Order）：图$G$中顶集$V$的大小称作图$G$的阶。
• 子图（Sub-Graph）：圖$G'$称作图$G$的子图如果$V(G')\subseteq V(G)$以及$E(G')\subseteq E(G)$。
• 生成子图（Spanning Sub-Graph）：指满足条件$V(G')=V(G)$的$G$的子图$G$。

• 度（Degree）是一个顶点的度是指与该頂點相关联的總边数，顶点$v$的度记作$d(v)$。度和邊有如下關係：$\sum_{v\in V} d(v)=2\left|E\right|$。
• 出度（Out-degree）和入度（In-degree）：對有向圖而言，頂點的度還可分為出度和入度。一個頂點的出度為$d_o$，是指有$d_o$條邊以該頂點為起點，或說與該點關聯的出邊共有$d_o$條。入度的概念也類似。
• 鄰接矩陣
• 自环（Loop）：若一条边的两个顶点相同，则此边称作自环。
• 路径（Path）：从頂點u到頂點v的一条路径是指一个序列$v_0,e_1,v_1,e_2,v_2,...e_k,v_k$，$e_i$的起點終點为$v_{i-1}$及$v_i$；$k$称作路径的长度；$v_0=u$，稱為路徑的起點；$v_k=v$，稱為路徑的終點。如果$u=v$，稱該路径是闭的，反之則稱為開的；如果$v_1,...,v_k$兩兩不等，則称之为简单路径（Simple path，注意，$u=v$是允許的）。
• 行迹（Trace）：如果路径$P(u,v)$中边各不相同，则该路径称为$u$到$v$的一条行迹。
• 轨道（Track）：即簡單路徑。
• 闭的行迹称作回路（Circuit），闭的轨道稱作圈（Cycle）。

（現存文獻中的命名法並無統一標準。比如在另一種定義中，walk對應上述的path，path對應上述的track，trail對應上述的trace。）

• 距離（Distance）： 从頂點u出發到頂點v的最短路徑若存在，則此路徑的長度稱作從u到v的距離。若從u到v根本不存在路徑，則記該距離為無窮（∞）。
• 距離矩陣
• 橋（Bridge）：若去掉一條邊，便會使得整個圖不連通，該邊稱為橋。

图的存储表示

• 数组（邻接矩阵）存储表示（有向或无向）
• 邻接表存储表示
• 前向星存储表示
• 有向图的十字链表存储表示
• 无向图的邻接多重表存储表示

一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图（网），相应位置为∞。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶点建立一个单链表（并按建立的次序编号），第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧）。每个结点由两个域组成：邻接点域（Adjvex），用以指示与vi邻接的点在图中的位置，链域（Nextarc）用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域（Info）。每个顶点的单链表中结点的个数即为该顶点的出度（与该顶点连接的边的总数）。无论是存储图或网，都需要在每个单链表前设一表头结点，这些表头结点的第一个域data用于存放结点vi的编号i，第二个域firstarc用于指向链表中第一个结点。

图的遍历

图的遍历方法有深度优先搜索法和广度（宽度）优先搜索法。

深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：

Boolean visited[MAX_VERTEX_NUM];        //访问标志数组
Status (*VisitFunc)(int v);     //VisitFunc是访问函数，对图的每个顶点调用该函数
void DFSTraverse (Graph G, Status(*Visit)(int v)){
        VisitFunc = Visit;
        for(v=0; v<G.vexnum; ++v)
                visited[v] = FALSE;     //访问标志数组初始化
        for(v=0; v<G.vexnum; ++v)
                if(!visited[v])
                        DFS(G, v);      //对尚未访问的顶点调用DFS
}
void DFS(Graph G, int v){ //从第v个顶点出发递归地深度优先遍历图G
visited[v]=TRUE;        VisitFunc(v);   //访问第v个顶点
for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0）。
//若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。
//若w是v的最后一个邻接点，则返回空（0）。
                if(!visited[w])
                        DFS(G, w);      //对v的尚未访问的邻接顶点w调用DFS
}

图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t，并均标记已访问过，然后再按照vi1,vi2,…, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：

Boolean visited[MAX_VERTEX_NUM];        //访问标志数组
Status (*VisitFunc)(int v);     //VisitFunc是访问函数，对图的每个顶点调用该函数
void BFSTraverse (Graph G, Status(*Visit)(int v)){
        VisitFunc = Visit;
for(v=0; v<G.vexnum, ++v)
                visited[v] = FALSE;
                initQueue(Q);   //置空辅助队列Q
        for(v=0; v<G.vexnum; ++v)
                if(!visited[v]){
                        visited[v]=TRUE;        VisitFunc(v);
                        EnQueue(Q, v);  //v入队列
                        while(!QueueEmpty(Q)){
                                DeQueue(Q, u);  //队头元素出队并置为u
                                for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
                                        if(!Visited[w]){        //w为u的尚未访问的邻接顶点
                                                Visited[w]=TRUE;        VisitFunc(w);
                                                EnQueue(Q, w);
                                        }
                        }
                }
}

圖的重要類型

• 补图：与G拥有相同的点的完全图删除原图G的边所得到的图成为G的补图
• 树状图
• 平面图
• 连通图
  • 强连通图
  • 强连通分量
• 有向无环图
  • AOV网
  • AOE网
• 完全图：每一对不同顶点间都有边相连的的图，记作$K_n$。
• 二分图：顶集$V=X\cup Y(X\cap Y=\phi)$，且每一条边都有一个顶点在$X$中，而另一个顶点在$Y$中。
  • 完全二分图：二分图$G$中若任意两个$X$和$Y$中的顶点都有边相连。若$\left|X\right|=m,\left|Y\right|=n$，则图$G$记作$K_{m,n}$。
• 正则图：如果图中所有顶点的度皆相等，则此图称为正则图
• 欧拉图:存在经过所有边一次（可以多次经过点）的路径的图
• 哈密顿图:存在经过所有点一次的路径的图

参考文献

1. Introduction To Graph Theory, Gary Chartrand and Ping Zhang, McGraw Hill

外部链接

• Graph Theory（可下載的書籍，英語）

参见

• 图论
• 邻接矩阵