图

维库，知识与思想的自由文库

在數學上，一个图是表示物件與物件之間的關係的方法，是圖論的基本研究對象。

目录 1 定義 1.1 二元組的定義 1.2 三元組的定義 2 基本术语 2.1 路徑 2.2 其他 3 分類 3.1 有/無 向图 3.2 单图 4 图的存储表示 5 图的遍历 6 重要的图 7 參考 8 参阅 9 外部連結

[编辑] 定義

[编辑] 二元組的定義

图G是一個有序二元组(V,E)，其中V称为顶集，E称为边集。它們亦可寫成V(G)和E(G)。

E的元素是一個二元組數對，用(x,y)表示，其中。

[编辑] 三元組的定義

一个图（Graph），是指一个三元组(V,E,I)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与G不相交；I称为关联函数，I将E中的每一个元素映射到。如果那么称边e连接顶点u,v，而u,v则称作e的端点，u,v此时关于e相邻。同时，若两条边i,j有一个公共顶点u，则称i,j关于u相邻。

[编辑] 基本术语

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

[编辑] 路徑

• 环(Loop)：若一条边的两个顶点为同一顶，则此边称作环。
• 路径（Path）：从u到v的一条路径是指一个序列v₀,e₁,v₁,e₂,v₂,...e_k,v_k，其中e_i的顶点为v_i及v_{i − 1}，k称作路径的长度。如果它的起止顶点相同，該路径是「闭」的，反之，則稱為「開」的。一条路径称为一简单路径(simple path)，如果路径中除起始与终止顶点可以重合外，所有顶点两两不等。
• 行迹（Trace）：如果路径P(u,v)中边各不相同，则该路径称为u到v的一条行迹。
• 轨道（Track）：如果路径P(u,v)中顶各不相同，则该路径称为u到v的一条轨道。
• 闭的行迹称作回路（circuit），闭的轨称作圈（Cycle）。

（另一種定義是：walk對應上述的path，path對應上述的track。Trail對應trace。）

[编辑] 其他

• 橋（bridge）：若去掉一條邊，便會使得整個圖不連通，該邊稱為橋。

[编辑] 分類

[编辑] 有/無 向图

如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反，邊沒有方向的圖稱為無向圖。

度（Degree）是一个顶点的度是指与该边相关联的边的条数，顶点v的度记作d(v)。显然有：

有向圖的頂點的度可分In degree和out degree。一个顶点的In Degree是指与該边相关联的入边的条数，Out Degree則指与該边相关联的出边的条数。

[编辑] 单图

一个图如果

1. 任意两顶点之间只有一条边（在有向图中為两顶点之间每個方向只有一条边）；
2. 边集中不含环

则称为单图。

[编辑] 图的存储表示

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

一个不带权图中若两点不相邻，邻接矩阵相应位置为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);
                                        }
                        }
                }
}

[编辑] 重要的图

• 树
• 平面图
• 连通图
  • 强连通图
• 有向无环图
  • AOV网
  • AOE网
• 完全图：每一对不同顶点间都有边相连的的图，记作K_n。
• 二分图：顶集，且每一条边都有一个顶点在X中，而另一个顶点在Y中。
  • 完全二分图：二分图G中若任意两个X和Y中的顶点都有边相连。若，则图G记作K_m,n。
• 正则图：如果图中所有顶点的度皆相等，则此图称为正则图

[编辑] 參考

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

[编辑] 参阅

• 图论
• 邻接矩阵

[编辑] 外部連結

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