图论术语

图论中最有名图之一。

一条边一般表示为连接其两个端点的曲线。以两个顶点${\displaystyle u}$、${\displaystyle v}$为端点的边一般记作${\displaystyle (u,v)}$、${\displaystyle \{u,v\}}$或${\displaystyle uv}$。一条边连接两个顶点u、v时，称u与v相邻。图${\displaystyle G}$的边集一般记作${\displaystyle E(G)}$，当不发生混淆时可简记为${\displaystyle E}$。

图${\displaystyle G}$的补图${\displaystyle {\bar {G}}}$是这样一的图，它的点集与${\displaystyle G}$相同，而每条边${\displaystyle (u,v)}$存在于${\displaystyle {\bar {G}}}$中当且仅当它不存在于${\displaystyle G}$中。

一个顶点一般表示为一个点或小圆圈。一个图${\displaystyle G}$的顶点集（点集）一般记作${\displaystyle V(G)}$，当不发生混淆时可简记为${\displaystyle V}$。图${\displaystyle G}$的阶为其顶点数目，亦即|${\displaystyle V(G)}$|。

若两个点之间有一条边，则这两个点相邻。关联一个点${\displaystyle v}$的边的条数称为是${\displaystyle v}$度数（degree）或价（valency）。特别的，若${\displaystyle G}$不是多重图时，它等于这一点的邻点个数。

一个顶点被称作孤立顶点，当它的度数为${\displaystyle 0}$。

${\displaystyle G}$的最小度记为${\displaystyle \delta (G):=min\left\{d(v)|v\in V\right\}}$

${\displaystyle G}$的最大度记为${\displaystyle \Delta (G):=max\left\{d(v)|v\in V\right\}}$

${\displaystyle G}$的平均度记为${\displaystyle d(G):={\frac {\sum _{v\in V}d(v)}{|V|}}}$

称${\displaystyle G}$为k-正则的，当${\displaystyle G}$的所有顶点都有相同的顶点度k。特别的，3-正则图被称作立方图。

一個圖的獨立集是圖中一些兩兩不相鄰的頂點所形成的集合。

图G是二分图当且仅当它的点集V能被划分成两块X和Y，使得对于G中的任意一条边，它有一个端点属于X而另一个端点属于Y。

看环（图论）。

距离是两个顶点之间经过最短路径的边的数目，通常用${\displaystyle d_{G}(u,v)}$表示。

顶点${\displaystyle v}$的偏心率（eccentricity），用来表示连接图${\displaystyle G}$中的顶点${\displaystyle v}$到图${\displaystyle G}$中其它顶点之间的最大距离，用符号${\displaystyle \epsilon _{G}(v)}$表示。

图的直径（diameter），表示取遍图的所有顶点，得到的偏心率的最大值，记作${\displaystyle diam(G)}$。相对于直径的一个概念是图的半径（radius），表示图的所有点的偏心率的最小值，记作${\displaystyle rad(G)}$。这两者间的关系是：${\displaystyle diam(G)\leqslant 2rad(G)}$

图论中著名的问题。

称${\displaystyle G}$是连通的，如果非空图${\displaystyle G}$的任意两个顶点之间均有一条路相连。

称${\displaystyle G}$是k-连通的，如果非空图${\displaystyle G}$的任意两个顶点之间都有${\displaystyle k}$条独立路相连。k-连通的的另外一个定义是：若${\displaystyle \mid G\mid >k\in \mathbb {N} }$,且对任意满足${\displaystyle |X|<k}$的子集${\displaystyle X\subseteq V}$均有${\displaystyle G-X}$是连通的，则称${\displaystyle G}$是k-连通的。由门格尔定理，易知这两个定义是等价的。通过k-连通的概念，定义使得${\displaystyle G}$是k-连通的最大整数${\displaystyle k}$称作${\displaystyle G}$的连通度。

类似的，还可以引入k-边连通的概念：称一个${\displaystyle \mid G\mid }$的图${\displaystyle G}$是k-边连通的，如果对任意一个满足${\displaystyle \mid F\mid <k}$的边的集合${\displaystyle F}$，${\displaystyle G-F}$均是连通的。同样，${\displaystyle G}$的边连通度是使得${\displaystyle G}$是k-边连通的最大整数。

计算机科学中最有名的问题之一。

一笔画问题、也看哈密尔顿环。

库拉托夫斯基定理描述了有点平面图。有名的欧拉公式也说：V-E+F=2. 这是欧拉示性数。

路径（walk），又译作途径。一个长度为${\displaystyle k}$的路径是一个非空的顶点和边的交错序列${\displaystyle v_{0}e_{0}v_{1}e_{1}...e_{k-1}v_{k}}$，使得对于所有${\displaystyle i<k}$均有${\displaystyle e_{i}={v_{i}v_{i+1}}}$。特别的，当${\displaystyle v_{0}=v_{k}}$时，称这个路径是闭的（closed）；当路径中的顶点互不相同，得到${\displaystyle G}$的一条路。[1]

有标号的树，有6个顶点和5条边。

连通无圈图称为树，一般记为T。其中，度数为1的顶点称为叶子，否则称为内点。有时我们会从树中选出一个顶点作为特殊顶点，称之为根以示区分，此时称此树为有根树。有根树常作为有向无环图来处理。

树T的连通子图称为T的子树。

树也是一个团的森林。

无环（不一定连通）图称为森林，森林F的子图称为F的子森林。

如果图G的一个生成子图是树，则称该子图为生成树。

星是仅有一个顶点不是叶子的树。星也可以表示为完全二分图K_1,n。

完全图K₅

图中的团是由图中两两相邻的顶点构成的集合。

完全图是所有顶点两两相邻的图。n阶完全图，记作K_n。如图所示为K₅。n阶完全图有n(n-1)/2条边。

重要的计算机科学、最优化理论、与算法学的题目。也看最大流最小割定理。

圍長定義為圖所包含的最短環長，也被称为"girth"。

看以上的树术语。

一个自环是两个端点为同一顶点的边。如果有多于一条边连接同一对顶点，则它们均被称为重边。一个图的重数是重复次数最多的边的重复次数。如果一个图不含自环或重边，则称为简单图。多数情况下，如无特殊说明，可以假定“图”总是指简单图。

图着色问题包含四色定理，数学中最有名的问题之一。现代的证明用电脑、文章很长。

两个图G和H，如果V(H)是V(G)的子集且E(H)是E(G)的子集（当然，E(H)中只能包含将V(H)中的顶点相连的边）则称H是G的子图。如果图G和H不相等，即V(H)是V(G)的真子集或E（H）是E（G）的真子集，则称H是G的真子图。如果H是G的子图或者存在一个G的子图与H同构，则称G包含H。

如果图G的子图H满足V(H)=V(G)，即图H包含图G的所有顶点，则称H是G的支撑子图或生成子图。

如果图G的子图H满足边(u,v)在图H中当且仅当边(u,v)在图G中，即图H包含了图G中所有两个端点都在V(H)中的边，则称H是G的导出子图。

对于图的某个性质而言，如果图G具有此性质而G的任一真子图都不具有此性质，则称G是具有该性质的极小图。类似地，如果图G具有此性质而任一以G为真子图的图都不具有此性质，则称G是具有该性质的极大图。

重要的计算机科学、与算法学的题目。也看Dijkstra算法、Kruskal算法、等。

看以上的平面图。