查看“︁图论术语”︁的源代码

{{expand english}}
[[图论]]中有许多专有名词，此处总结了一些名词的一般意义和用法。

== 基本术语 ==

一个'''[[图]]'''（一般记作<math>G</math>）由两类元素构成，分别称为“[[顶点_(图论)|顶点]]”（或节点、结点）和“[[邊 (圖論)|边]]”。每条边有两个顶点作为其'''端点'''，我们称这条边“连接”了它的两个端点。因此，边可定义为由两个顶点构成的[[集合 (数学)|集合]]（在有向图中为[[有序对]]，见下文“[[#图的方向|方向]]”一节）。

图也可以用其他模型来表示，如定义在顶点集合上的[[二元函数|二元]][[布尔函数]]，或者方形(0,1)-[[矩阵]]。

顶点或边上有标号的图称为'''有标号的'''，否则为'''无标号的'''。它们的区别在于，无标号的图并没有为顶点或边指定一个特定的顺序。

'''图的标号'''一般指按某一规则为图的顶点或边指定一个标号。标号通常是[[自然数]]，且一般互不相同。

[[File:6n-graf.svg|thumb|一个有标号的简单图，点集''V'' = {1, 2, 3, 4, 5, 6}，边集''E'' = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}}。]]

一个'''[[超边]]'''是允许连接任意多个（可以多于两个）顶点的“[[邊 (圖論)|边]]”。含有超边的“图”称为'''[[超图]]'''。边可视为恰连接两个顶点的超边，因此图可视为一种特殊的超图。

'''空图'''或'''秃图'''是没有边的图。

如果一个图有无穷多的顶点和/或边，则称其为'''无穷'''的，否则为'''有穷'''的。如果一个图是无穷的，但每个顶点的度（见下）是有限的，则称为'''局部有穷'''的。一般假定“图”指有穷图。

两个图<math>G</math>和<math>H</math>，如果存在<math>V(G)</math>与<math>V(H)</math>之间的一一对应，使得图<math>G</math>中两个顶点相连当且仅当它们在图<math>H</math>中的对应顶点相连，则称图<math>G</math>和<math>H</math> '''[[图同构|同构]]'''，记作<math>G\simeq H</math>。类似地，如果仅仅是<math>V(G)</math>到<math>V(H)</math>的映射而不一定是一一对应，则称此映射是<math>G</math>到<math>H</math>的'''同态'''。

=== [[佩特森圖|彼得森图]] ===
图论中最有名图之一。

=== 边 ===
{{main|邊 (圖論)}}
一条'''边'''一般表示为连接其两个端点的曲线。以两个顶点<math>u</math>、<math>v</math>为端点的边一般记作<math>(u,v)</math>、<math>\{u,v\}</math>或<math>uv</math>。一条边连接两个顶点''u''、''v''时，称''u''与''v''相邻。图<math>G</math>的边集一般记作<math>E(G)</math>，当不发生混淆时可简记为<math>E</math>。

=== 补图 ===
图<math>G</math>的'''[[補圖|补图]]'''<math>\bar{G}</math>是这样一的图，它的点集与<math>G</math>相同，而每条边<math>(u,v)</math>存在于<math>\bar{G}</math>中当且仅当它不存在于<math>G</math>中。

=== 顶点 ===
{{main|顶点 (图论)}}
一个'''顶点'''一般表示为一个点或小圆圈。一个图<math>G</math>的'''顶点集'''（点集）一般记作<math>V(G)</math>，当不发生混淆时可简记为<math>V</math>。图<math>G</math>的'''阶'''为其顶点数目，亦即|<math>V(G)</math>|。

=== 度 ===
{{main|度 (图论)}}若两个点之间有一条边，则这两个点相邻。关联一个点<math>v</math>的边的条数称为是<math>v</math>度数（degree）或价（valency）。特别的，若<math>G</math>不是多重图时，它等于这一点的邻点个数。

一个顶点被称作'''孤立顶点'''，当它的度数为<math>0</math>。

<math> G </math>的'''最小度'''记为<math> \delta(G) := min\left\{d(v)|v\in V\right\}</math>

<math> G </math>的'''最大度'''记为<math> \Delta(G) := max\left\{d(v)|v\in V\right\}</math>

<math> G </math>的'''平均度'''记为<math> d(G) := \frac{\sum_{v \in V} d(v)} {|V|}</math>

称<math> G </math>为'''k-[[正則圖|正则]]的'''，当<math>G</math>的所有顶点都有相同的顶点度k。特别的，3-正则图被称作'''[[立方图]]'''。

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

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

=== [[哈密顿图|哈密尔顿图]] ===

=== 环 ===
看[[環 (圖論)|环（图论）]]。

=== 结 ===

=== 距离 ===
'''[[距离 (图论)|距离]]'''是两个顶点之间经过最短路径的边的数目，通常用<math>d_G ( u, v )</math>表示。

顶点<math>v</math>的'''偏心率'''（eccentricity），用来表示连接图<math>G</math>中的顶点<math>v</math>到图<math>G</math>中其它顶点之间的最大距离，用符号<math>\epsilon_G (v)</math>表示。

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

=== [[柯尼斯堡七桥问题]] ===
[[图论]]中著名的问题。

=== 立方图 ===
{{main|立方图}}

=== 连通图／连通性 ===
{{main|连通图}}称<math>G</math>是'''连通的'''，如果非空图<math>G</math>的任意两个顶点之间均有一条路相连。

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

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

===[[旅行推销员问题]]===
[[计算机科学]]中最有名的问题之一。

=== 欧拉路径 ===
[[一笔画问题]]、也看[[哈密顿图|哈密尔顿]]环。

=== [[匹配 (图论)|匹配]] ===

=== [[平面图 (图论)|平面图]] ===
[[库拉托夫斯基定理]]描述了有点平面图。有名的[[萊昂哈德·歐拉|欧拉]]公式也说：V-E+F=2. 这是[[欧拉示性数]]。

=== 嵌入 ===

=== [[强连通分量]] ===

=== [[桥 (图论)|桥]] ===

=== 路径 ===
路径（walk），又译作途径。一个长度为<math>k</math>的路径是一个非空的顶点和边的交错序列<math>v_0 e_0 v_1 e_1 ... e_{k-1} v_k</math>，使得对于所有<math>i < k</math>均有<math>e_i={v_i v_{i+1}}</math>。特别的，当<math>v_0 = v_k</math>时，称这个路径是闭的（closed）；当路径中的顶点互不相同，得到<math>G</math>的一条路。<ref>{{cite book| author= R.Diestel| title= 图论| edition = 第四版|publisher= 高等教育出版社| page= 10}}</ref>

=== 树 ===

[[File:Tree graph.svg|thumb|有标号的树，有6个顶点和5条[[邊 (圖論)|边]]。]]
连通无圈图称为'''[[树 (图论)|树]]'''，一般记为''T''。其中，度数为1的顶点称为'''叶子'''，否则称为'''内点'''。有时我们会从树中选出一个顶点作为特殊顶点，称之为'''根'''以示区分，此时称此树为'''有根树'''。有根树常作为[[有向无环图]]来处理。

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

树也是一个团的森林。

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

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

'''星'''是仅有一个顶点不是叶子的树。星也可以表示为[[完全二分图]]''K''<sub>1,''n''</sub>。

=== 缩图 ===

=== [[随机图]] ===

=== 团 ===

[[File:Complete graph K5.svg|thumb|完全图K<sub>5</sub>]]

图中的'''[[团 (图论)|团]]'''是由图中两两相邻的顶点构成的集合。

=== [[三間小屋問題|Utility graph]] ===

=== [[完全圖|完全图]] ===
'''[[完全图]]'''是所有顶点两两相邻的图。''n''阶'''完全图'''，记作''K<sub>n</sub>''。如图所示为''K<sub>5</sub>''。''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算法]]、等。

== 定理术语 ==
*[[彼得森定理]]
*[[布鲁克斯定理]]
*[[柯尼格引理]]
*{{le|柯尼格定理 (圖論)|Kőnig's theorem (graph theory)}}
*[[库拉托夫斯基定理]]
*[[拉姆齐定理]]（而且看[[拉姆齐理论]]）
*[[门格尔定理]]（Menger's Theorem）
*[[图特定理]]
*[[Vizing定理]]
*[[最大流最小割定理]]

== 图的方向 ==

=== 有向无环图 ===

== 代数图论 ==
[[代数图论]]

== 不变量 ==

=== 亏格（[[几何学|几何]]、[[拓扑学|拓扑]]） ===
看以上的[[平面图 (图论)|平面图]]。

== 譜圖論 ==
{{main|譜圖論}}

== 参考来源 ==
{{reflist}}

== 参见 ==
*[[图 (数学)|图]]
*[[图论]]
*[[图论话题列表]]
*[[数学]]
*[[离散数学]]
*[[组合数学]]
*[[算法]]
*[[计算机科学]]
*[[最优化]]
*[[人工智能]]（[[神经网络|神经网格]]）
*[[连接组]]（[[承现峻]]，connectome）
*[[网络科学|网格科学]]
*[[费曼图]]（Feynman diagram、[[物理学|物理]]、[[量子力学]]、[[统计力学]]）

{{图论}}

[[Category:图论]]

[[he:גרף (תורת הגרפים)#תת גרף]]

[[cs:Podgraf]]
[[de:Teilgraph]]
[[pl:Podgraf]]
[[pt:Subgrafo]]
[[sk:Podgraf]]