图 (数学)

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

在頂點1有一個環

• 阶（Order）：图${\displaystyle G}$中顶集${\displaystyle V}$的大小称作图${\displaystyle G}$的阶。
• 子图（Sub-Graph）：圖${\displaystyle G'}$称作图${\displaystyle G}$的子图如果${\displaystyle V(G')\subseteq V(G)}$以及${\displaystyle E(G')\subseteq E(G)}$。
• 生成子图（Spanning Sub-Graph）：指满足条件${\displaystyle V(G')=V(G)}$的${\displaystyle G}$的子图${\displaystyle G'}$。
• 度（Degree）：一个顶点的度是指与该頂點相关联的總边数，顶点${\displaystyle v}$的度记作${\displaystyle d(v)}$。度和邊有如下關係：${\displaystyle \sum _{v\in V}d(v)=2\left|E\right|}$。
• 出度（Out-degree）和入度（In-degree）：對有向圖而言，頂點的度還可分為出度和入度。一個頂點的出度為${\displaystyle d_{o}}$，是指有${\displaystyle d_{o}}$條邊以該頂點為起點，或說與該點關聯的出邊共有${\displaystyle d_{o}}$條。入度的概念也類似。
• 鄰接矩陣（Adjacency matrix）
• 自环（Loop）：若一条边的两个顶点相同，则此边称作自环。
• 路径（Path）：从頂點u到頂點v的一条路径是指一个序列${\displaystyle v_{0},e_{1},v_{1},e_{2},v_{2},...e_{k},v_{k}}$，${\displaystyle e_{i}}$的起點終點为${\displaystyle v_{i-1}}$及${\displaystyle v_{i}}$；${\displaystyle k}$称作路径的长度；${\displaystyle v_{0}=u}$，稱為路徑的起點；${\displaystyle v_{k}=v}$，稱為路徑的終點。如果${\displaystyle u=v}$，稱該路径是闭的，反之則稱為開的；如果${\displaystyle v_{1},...,v_{k}}$兩兩不等，則称之为简单路径（Simple path，注意，${\displaystyle u=v}$是允許的）。
• 行迹（Trace）：如果路径${\displaystyle P(u,v)}$中边各不相同，则该路径称为${\displaystyle u}$到${\displaystyle v}$的一条行迹。
• 轨道（Track）：即簡單路徑。
• 闭的行迹称作回路（Circuit），闭的轨道稱作圈（Cycle）。（現存文獻中的命名法並無統一標準。比如在另一種定義中，walk對應上述的path，path對應上述的track，trail對應上述的trace。）
• 距離（Distance）： 从頂點${\displaystyle u}$出發到頂點${\displaystyle v}$的最短路徑若存在，則此路徑的長度稱作從${\displaystyle u}$到${\displaystyle v}$的距離。若從${\displaystyle u}$到${\displaystyle v}$根本不存在路徑，則記該距離為無窮（${\displaystyle \infty }$）。
• 距離矩陣（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出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：

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网
• 完全图：每一对不同顶点间都有边相连的的图，记作${\displaystyle K_{n}}$。
• 二分图：顶集${\displaystyle V=X\cup Y(X\cap Y=\phi )}$，且每一条边都有一个顶点在${\displaystyle X}$中，而另一个顶点在${\displaystyle Y}$中。
  • 完全二分图：二分图${\displaystyle G}$中若任意两个${\displaystyle X}$和${\displaystyle Y}$中的顶点都有边相连。若${\displaystyle \left|X\right|=m,\left|Y\right|=n}$，则图${\displaystyle G}$记作${\displaystyle K_{m,n}}$。
• 正则图：如果图中所有顶点的度皆相等，则此图称为正则图
• 欧拉图:存在经过所有边一次（可以多次经过点）的路径的图
• 哈密顿图:存在经过所有点一次的路径的图
• 加权图（weighted graph）：一个加权图在图中的每条边上给出一个值（权重）

对于图${\displaystyle G(V,E)}$与图${\displaystyle G'(V',E')}$，若存在从${\displaystyle V}$到${\displaystyle V'}$的一一映射f，使任意${\displaystyle (u,v)\in E}$,都有${\displaystyle (f(u),f(v))\in E'}$，则称${\displaystyle G}$与${\displaystyle G'}$同构

• Springer-Verlag, Heidelberg. . 2016 [20190722]. （原始内容存档于2012-02-08）. 请检查|access-date=中的日期值 (帮助) （可下載的書籍，英語）

• 图论
• 邻接矩阵