图 (数学)
本條目介紹的是圖論中的基本研究對象。關於數學函數的圖，請見“函数图形”。關於其他主題，請見“图”。 | 本條目已列出參考文獻，但因為沒有文內引註而使來源仍然不明。（2018年5月24日） |
在數學的分支图论中，图（Graph）用于表示物件與物件之間的關係，是圖論的基本研究對象。一张圖由一些小圓點（稱為頂點或結點）和連結這些圓點的直線或曲線（稱為邊）組成。西尔维斯特在1878年首次提出“图”这一名词。
目录
1 定義
1.1 二元組的定義
1.2 三元組的定義
2 分類
2.1 有向图和無向图
2.2 简单图
2.3 多重圖
3 基本术语
4 图的存储表示
5 图的遍历
6 圖的重要類型
7 图的同构
8 参考文献
8.1 引用
8.2 来源
9 外部链接
10 参见
定義
圖有多種變體，包括簡單圖、多重圖、有向圖、無向圖等，但大體上有以下兩種定義方式。
二元組的定義
一张图 G{displaystyle G}
E{displaystyle E}
三元組的定義
一张图 G{displaystyle G}
分類
有向图和無向图
如果给图的每条边规定一个方向，那么得到的图称为有向图，其邊也稱為有向邊。在有向图中，与一个节点相关联的边有出边和入边之分，而與一個有向邊關聯的兩個點也有始點和終點之分。相反，邊沒有方向的圖稱為無向圖。
简单图
一个图如果
- 没有兩條邊，它們所關聯的兩個點都相同（在有向图中，没有兩條邊的起點終點都分別相同）；
- 每條邊所關聯的是兩個不同的頂點
- 则称为简单图（Simple graph）。簡單的有向圖和無向圖都可以使用以上的「二元組的定義」，但形如(x,x){displaystyle (x,x)}
的序對不能屬於E。而無向圖的邊集必須是對稱的，即如果(x,y)∈E{displaystyle (x,y)in E}
，那么(y,x)∈E{displaystyle (y,x)in E}
。
多重圖
若允許兩結點間的邊數多於一條，又允許頂點通過同一條邊和自己關聯，則為多重圖的概念。它只能用「三元組的定義」。
基本术语
阶（Order）：图G{displaystyle G}
子图（Sub-Graph）：圖G′{displaystyle G'}称作图G{displaystyle G}
以及E(G′)⊆E(G){displaystyle E(G')subseteq E(G)}
。
生成子图（Spanning Sub-Graph）：指满足条件V(G′)=V(G){displaystyle V(G')=V(G)}的G{displaystyle G}
度（Degree）：一个顶点的度是指与该頂點相关联的總边数，顶点v{displaystyle v}的度记作d(v){displaystyle d(v)}
。度和邊有如下關係：∑v∈Vd(v)=2|E|{displaystyle sum _{vin V}d(v)=2left|Eright|}
。
出度（Out-degree）和入度（In-degree）：對有向圖而言，頂點的度還可分為出度和入度。一個頂點的出度為do{displaystyle d_{o}}，是指有do{displaystyle d_{o}}
鄰接矩陣（Adjacency matrix）
自环（Loop）：若一条边的两个顶点相同，则此边称作自环。
路径（Path）：从頂點u到頂點v的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk{displaystyle v_{0},e_{1},v_{1},e_{2},v_{2},...e_{k},v_{k}}，ei{displaystyle e_{i}}
的起點終點为vi−1{displaystyle v_{i-1}}
及vi{displaystyle v_{i}}
；k{displaystyle k}
称作路径的长度；v0=u{displaystyle v_{0}=u}
，稱為路徑的起點；vk=v{displaystyle v_{k}=v}
，稱為路徑的終點。如果u=v{displaystyle u=v}
，稱該路径是闭的，反之則稱為開的；如果v1,...,vk{displaystyle v_{1},...,v_{k}}
兩兩不等，則称之为简单路径（Simple path，注意，u=v{displaystyle u=v}
行迹（Trace）：如果路径P(u,v){displaystyle P(u,v)}中边各不相同，则该路径称为u{displaystyle u}
轨道（Track）：即簡單路徑。- 闭的行迹称作回路（Circuit），闭的轨道稱作圈（Cycle）。（現存文獻中的命名法並無統一標準。比如在另一種定義中，walk對應上述的path，path對應上述的track，trail對應上述的trace。）
距離（Distance）： 从頂點u{displaystyle u}）。
距離矩陣（Distance matrix）
橋（Bridge）：若去掉一條邊，便會使得整個圖不連通，該邊稱為橋。
图的存储表示
数组（邻接矩阵）存储表示（有向或无向）
邻接表存储表示
前向星存储表示
有向图的十字链表存储表示
无向图的邻接多重表存储表示
一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图（网），相应位置为∞。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶点建立一个单链表（并按建立的次序编号），第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧）。每个结点由两个域组成：邻接点域（Adjvex），用以指示与vi邻接的点在图中的位置，链域（Nextarc）用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域（Info）。每个顶点的单链表中结点的个数即为该顶点的出度（与该顶点连接的边的总数）。无论是存储图或网，都需要在每个单链表前设一表头结点，这些表头结点的第一个域data用于存放结点vi的编号i，第二个域firstarc用于指向链表中第一个结点。
图的遍历
图与树 搜索算法 |
|---|
|
分类 |
|
相关主题 |
|
图的遍历方法有深度优先搜索法和广度（宽度）优先搜索法。
深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：
1 Boolean visited[MAX_VERTEX_NUM]; // 访问标志数组
2 Status (*VisitFunc)(int v); // VisitFunc是访问函数，对图的每个顶点调用该函数
3 void DFSTraverse (Graph G, Status(*Visit)(int v)) {
4 VisitFunc = Visit;
5 for (v = 0; v < G.vexnum; ++v)
6 visited[v] = FALSE; // 访问标志数组初始化
7 for (v = 0; v < G.vexnum; ++v)
8 if (!visited[v])
9 DFS(G, v); // 对尚未访问的顶点调用DFS
10 }
11 void DFS(Graph G, int v) { // 从第v个顶点出发递归地深度优先遍历图G
12 visited[v] = TRUE;
13 VisitFunc(v); // 访问第v个顶点
14 for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
15 // FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0）。
16 // 若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。
17 // 若w是v的最后一个邻接点，则返回空（0）。
18 if (!visited[w])
19 DFS(G, w); // 对v的尚未访问的邻接顶点w调用DFS
20 }
图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t，并均标记已访问过，然后再按照vi1,vi2,…, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：
1 Boolean visited[ MAX_VERTEX_NUM ]; // 访问标志数组
2 Status (* VisitFunc)(int v); // VisitFunc是访问函数，对图的每个顶点调用该函数
3
4 void BFSTraverse(Graph G, Status(* Visit)(int v)) {
5 VisitFunc = Visit;
6 for (v = 0; v < G.vexnum; ++v)
7 visited[v] = FALSE;
8 initQueue(Q); // 置空辅助队列Q
9 for (v = 0; v < G.vexnum; ++v) {
10 if (!visited[v]) {
11 visited[v] = TRUE;
12 VisitFunc(v);
13 EnQueue(Q, v); // v入队列
14 while (!QueueEmpty(Q)) {
15 DeQueue(Q, u); // 队头元素出队并置为u
16 for (w = FirstAdjVex(G, u);
17 w >= 0; w = NextAdjVex(G, u, w))
18 if (!Visited[w]) { // w为u的尚未访问的邻接顶点
19 Visited[w] = TRUE;
20 VisitFunc(w);
21 EnQueue(Q, w);
22 }
23 }
24 }
25 }
26 }
圖的重要類型
补图：与G拥有相同的点的完全图删除原图G的边所得到的图成为G的补图- 树状图
- 平面图
连通图
- 强连通图
- 强连通分量
有向无环图
- AOV网
- AOE网
完全图：每一对不同顶点间都有边相连的的图，记作Kn{displaystyle K_{n}}。
二分图：顶集V=X∪Y(X∩Y=ϕ){displaystyle V=Xcup Y(Xcap Y=phi )}，且每一条边都有一个顶点在X{displaystyle X}
中，而另一个顶点在Y{displaystyle Y}
中。
完全二分图：二分图G{displaystyle G}，则图G{displaystyle G}
。
正则图：如果图中所有顶点的度皆相等，则此图称为正则图
欧拉图:存在经过所有边一次（可以多次经过点）的路径的图
哈密顿图:存在经过所有点一次的路径的图
图的同构
对于图G(V,E){displaystyle G(V,E)}
参考文献
引用
来源
- 书籍
Introduction To Graph Theory, by Gary Chartrand and Ping Zhang, McGraw Hill
外部链接
Graph Theory（可下載的書籍，英語）
参见
- 图论
- 邻接矩阵
| ||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
