9
个编辑
更改
无编辑摘要
The degree of a vertex, denoted 𝛿(v) in a graph is the number of edges incident to it. An isolated vertex is a vertex with degree zero; that is, a vertex that is not an endpoint of any edge (the example image illustrates one isolated vertex). A leaf vertex (also pendant vertex) is a vertex with degree one. In a directed graph, one can distinguish the outdegree (number of outgoing edges), denoted 𝛿<sup> +</sup>(v), from the indegree (number of incoming edges), denoted 𝛿<sup>−</sup>(v); a source vertex is a vertex with indegree zero, while a sink vertex is a vertex with outdegree zero. A simplicial vertex is one whose neighbors form a clique: every two neighbors are adjacent. A universal vertex is a vertex that is adjacent to every other vertex in the graph.
The degree of a vertex, denoted 𝛿(v) in a graph is the number of edges incident to it. An isolated vertex is a vertex with degree zero; that is, a vertex that is not an endpoint of any edge (the example image illustrates one isolated vertex). A leaf vertex (also pendant vertex) is a vertex with degree one. In a directed graph, one can distinguish the outdegree (number of outgoing edges), denoted 𝛿<sup> +</sup>(v), from the indegree (number of incoming edges), denoted 𝛿<sup>−</sup>(v); a source vertex is a vertex with indegree zero, while a sink vertex is a vertex with outdegree zero. A simplicial vertex is one whose neighbors form a clique: every two neighbors are adjacent. A universal vertex is a vertex that is adjacent to every other vertex in the graph.
<font color="#32cd32">图中顶点的’’’</font><font color="#ff8000">度数</font><font color="#32cd32">’’’（用𝛿(v)表示）是关联到它的边的数目</font>。一个’’’<font color="#ff8000">孤立顶点</font>’’’是一个度为零的顶点，也就是说，是一个不是任何边的端点的顶点(示例图片中有一个’’’<font color="#ff8000">孤立顶点</font>’’’的例子)。’’’<font color="#ff8000">叶顶点</font>’’’(也称作’’’<font color="#ff8000">悬挂点</font>’’’)是度数为1的顶点。在有向图中，我们可以区分<font color="#32cd32">外度(外出边数)</font>（用 𝛿<sup> +</sup>(v) 表示），和<font color="#32cd32">外度(外入边数) </font>（用𝛿<sup>−</sup>(v)表示） ; <font color="#32cd32">源顶点</font>是外度为零的顶点，而<font color="#32cd32">汇顶点</font>是具有外度为零的顶点。<font color="#32cd32">单纯形顶点</font>是<font color="#32cd32">邻接</font>成团的顶点：每两个<font color="#32cd32">邻接</font>都是相邻的。<font color="#32cd32">通用顶点</font>是在图中与其他所有顶点都相邻的顶点。
<font color="#32cd32">图中顶点的'''</font><font color="#ff8000">度数</font><font color="#32cd32">'''（用𝛿(v)表示）是关联到它的边的数目</font>。一个'''<font color="#ff8000">孤立顶点</font>'''是一个度为零的顶点，也就是说，是一个不是任何边的端点的顶点(示例图片中有一个'''<font color="#ff8000">孤立顶点</font>'''的例子)。'''<font color="#ff8000">叶顶点</font>'''(也称作'''<font color="#ff8000">悬挂点</font>''')是度数为1的顶点。在有向图中，我们可以区分<font color="#32cd32">外度(外出边数)</font>（用 𝛿<sup> +</sup>(v) 表示），和<font color="#32cd32">外度(外入边数) </font>（用𝛿<sup>−</sup>(v)表示） ; <font color="#32cd32">源顶点</font>是外度为零的顶点，而<font color="#32cd32">汇顶点</font>是具有外度为零的顶点。<font color="#32cd32">单纯形顶点</font>是<font color="#32cd32">邻接</font>成团的顶点：每两个<font color="#32cd32">邻接</font>都是相邻的。<font color="#32cd32">通用顶点</font>是在图中与其他所有顶点都相邻的顶点。
A cut vertex is a vertex the removal of which would disconnect the remaining graph; a vertex separator is a collection of vertices the removal of which would disconnect the remaining graph into small pieces. A k-vertex-connected graph is a graph in which removing fewer than k vertices always leaves the remaining graph connected. An independent set is a set of vertices no two of which are adjacent, and a vertex cover is a set of vertices that includes at least one endpoint of each edge in the graph. The vertex space of a graph is a vector space having a set of basis vectors corresponding with the graph's vertices.
A cut vertex is a vertex the removal of which would disconnect the remaining graph; a vertex separator is a collection of vertices the removal of which would disconnect the remaining graph into small pieces. A k-vertex-connected graph is a graph in which removing fewer than k vertices always leaves the remaining graph connected. An independent set is a set of vertices no two of which are adjacent, and a vertex cover is a set of vertices that includes at least one endpoint of each edge in the graph. The vertex space of a graph is a vector space having a set of basis vectors corresponding with the graph's vertices.
'''<font color="#ff8000">割点</font>'''是一类顶点，如果去掉它，就会断开剩余图的连接; <font color="32cd32">顶点分隔符</font>是一组顶点的集合，如果去掉这些顶点，就会将剩余图断裂成小片段。一个<font color="32cd32">k- 顶点连通图</font>是指一类去掉少于 k 个顶点后，剩余部分仍然连通的图。一个<font color="32cd32">独立的集合</font>是一组任意二者均不相邻的顶点群。<font color="32cd32">顶点覆盖</font>是一组顶点，它们均包含图中任意边的至少一个端点。图的'''<font color="#ff8000">顶点空间</font>'''是一个向量空间，它的基向量与图的顶点相对应。
A graph is vertex-transitive if it has symmetries that map any vertex to any other vertex. In the context of graph enumeration and graph isomorphism it is important to distinguish between labeled vertices and unlabeled vertices. A labeled vertex is a vertex that is associated with extra information that enables it to be distinguished from other labeled vertices; two graphs can be considered isomorphic only if the correspondence between their vertices pairs up vertices with equal labels. An unlabeled vertex is one that can be substituted for any other vertex based only on its adjacencies in the graph and not based on any additional information.
A graph is vertex-transitive if it has symmetries that map any vertex to any other vertex. In the context of graph enumeration and graph isomorphism it is important to distinguish between labeled vertices and unlabeled vertices. A labeled vertex is a vertex that is associated with extra information that enables it to be distinguished from other labeled vertices; two graphs can be considered isomorphic only if the correspondence between their vertices pairs up vertices with equal labels. An unlabeled vertex is one that can be substituted for any other vertex based only on its adjacencies in the graph and not based on any additional information.
如果一个图具有将任何顶点映射到任何其他顶点的对称性，则该图是'''<font color="#ff8000">顶点传递</font>'''的。在<font color="32cd32">图计数</font>和'''<font color="#ff8000">图同构</font>'''的情况下，区分'''<font color="#ff8000">标记顶点</font>'''和'''<font color="#ff8000">非标记顶点</font>'''非常重要。'''<font color="#ff8000">标记顶点</font>'''是与能使其区别于其他'''<font color="#ff8000">标记顶点</font>'''的额外信息相关联的顶点; <font color="32cd32">只有当其顶点之间的对应关系与有相同标记的顶点配对时</font>，两个图才可以被认为是同构的。'''<font color="#ff8000">非标记顶点</font>'''是仅基于其在图中的邻接顶点而不基于任何其他信息就能被其他任意顶点替换的一类顶点。