526
个编辑
更改
跳到导航
跳到搜索
第101行：
第101行： − 如果一个图中的所有顶点的度值都为k，该图被称为'''<font color="#ff8000">''k''-正则图 ''k''-regular graph</font>'''，该图的度值也为k。同样的，同侧每两个顶点都具有相同度值的二分图叫作'''<font color="#ff8000">二分正则图 Biregular Graph</font>'''。+ − 当且仅当具有0或2个奇数度的顶点时，无向连通图才具有'''<font color="#ff8000">欧拉路径 Eulerian Path</font>'''。 如果它具有0个奇数度的顶点，则欧拉路径为'''<font color="#ff8000">欧拉回路 Eulerian Circuit</font>'''。+ − 有向图是当且仅当每个顶点的度值最大为1时才是'''<font color="#ff8000">伪森林 Pseudoforest</font>'''。'''<font color="#ff8000">功能图 Functional Graph</font>'''是伪森林的特例，其中每个顶点的度数都恰好为1。+ − + −
→Global properties
全局属性
全局属性
*If each vertex of the graph has the same degree ''k'' the graph is called a [[regular graph|''k''-regular graph]] and the graph itself is said to have degree ''k''. Similarly, a [[bipartite graph]] in which every two vertices on the same side of the bipartition as each other have the same degree is called a [[biregular graph]].
*If each vertex of the graph has the same degree ''k'' the graph is called a [[regular graph|''k''-regular graph]] and the graph itself is said to have degree ''k''. Similarly, a [[bipartite graph]] in which every two vertices on the same side of the bipartition as each other have the same degree is called a [[biregular graph]].
如果一个图中的所有顶点的度值都为k，那么该图被称为'''<font color="#ff8000">''k''-正则图 ''k''-regular graph</font>'''，该图的度数也为k。同样的，同侧每两个顶点都具有相同度数的二分图叫作'''<font color="#ff8000">二分正则图 Biregular Graph</font>'''。
*An undirected, connected graph has an [[Eulerian path]] if and only if it has either 0 or 2 vertices of odd degree. If it has 0 vertices of odd degree, the Eulerian path is an Eulerian circuit.
*An undirected, connected graph has an [[Eulerian path]] if and only if it has either 0 or 2 vertices of odd degree. If it has 0 vertices of odd degree, the Eulerian path is an Eulerian circuit.
当且仅当一个图具有0或2个奇数度的顶点时，无向连通图才具有'''<font color="#ff8000">欧拉路径 Eulerian Path</font>'''。 如果它具有0个奇数度的顶点，则欧拉路径为'''<font color="#ff8000">欧拉回路 Eulerian Circuit</font>'''。
*A directed graph is a [[pseudoforest]] if and only if every vertex has outdegree at most 1. A [[functional graph]] is a special case of a pseudoforest in which every vertex has outdegree exactly 1.
*A directed graph is a [[pseudoforest]] if and only if every vertex has outdegree at most 1. A [[functional graph]] is a special case of a pseudoforest in which every vertex has outdegree exactly 1.
当且仅当每个顶点的度数最大值为1时称该图为有向图'''<font color="#ff8000">伪森林 Pseudoforest</font>'''。'''<font color="#ff8000">功能图 Functional Graph</font>'''是伪森林的特例，其中每个顶点的度数都恰好为1。
*By [[Brooks' theorem]], any graph other than a clique or an odd cycle has [[chromatic number]] at most Δ, and by [[Vizing's theorem]] any graph has [[chromatic index]] at most Δ + 1.
*By [[Brooks' theorem]], any graph other than a clique or an odd cycle has [[chromatic number]] at most Δ, and by [[Vizing's theorem]] any graph has [[chromatic index]] at most Δ + 1.
根据布鲁克斯定理，除团簇或奇数循环外，任何图的色度数最大为Δ，而根据维辛定理，任何图的色度指数最大为Δ+ 1。
根据布鲁克斯定理，除团簇或奇数循环外，任何图的色度数最大为Δ，而根据维辛定理，任何图的色度指数最大为Δ+ 1。
*A [[Degeneracy (graph theory)|''k''-degenerate graph]] is a graph in which each subgraph has a vertex of degree at most ''k''.
*A [[Degeneracy (graph theory)|''k''-degenerate graph]] is a graph in which each subgraph has a vertex of degree at most ''k''.
'''<font color="#ff8000">k简并图 K-Degenerate Graph </font>'''是其中每个子图最多具有度值为k的顶点的图。
'''<font color="#ff8000">k简并图 K-Degenerate Graph </font>'''是其中每个子图最多具有度数为k的顶点的图。
==See also==
==See also==