2,443
个编辑
更改
跳到导航
跳到搜索
第10行：
第10行： − 若图包含由顶点v和w组成的边(v,w)，则称顶点w邻接于adjacent to顶点v;由所有邻接于v的顶点而组成 的图，被称为这些顶点的导出'''子图induced subgraph'''，它也被称为顶点v的'''邻域 neighborhood'''。+ 第17行：
第17行： − '''<font color="#32cd32">图中顶点的</font><font color="#ff8000">度数</font><font color="#32cd32">（用𝛿(v)表示）是关联到它的边的数目</font>'''。一个'''<font color="#ff8000">孤立顶点</font>'''是一个度为零的顶点，也就是说，是一个不是任何边的端点的顶点（示例图片中有一个'''<font color="#ff8000">孤立顶点</font>'''的例子）。<ref>[[:File:Small Network.png]]; example image of a network with 8 vertices and 10 edges</ref>'''<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="32cd32">k- 顶点连通图</font>是指一类去掉少于 k 个顶点后，剩余部分仍然连通的图。一个<font color="32cd32">独立的集合</font>是一组任意二者均不相邻的顶点群。<font color="32cd32">顶点覆盖</font>是一组顶点，它们均包含图中任意边的至少一个端点。图的'''<font color="#ff8000">顶点空间</font>'''是一个向量空间，它的基向量与图的顶点相对应。+ + − 如果一个图具有将任何顶点映射到任何其他顶点的对称性，则该图是'''<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>'''是仅基于其在图中的邻接顶点而不基于任何其他信息就能被其他任意顶点替换的一类顶点。 + − 在图中的顶点类似但不等同于多面体的顶点：多面体的骨架构成一个图，其顶点是多面体的顶点，但多面体的顶点有无法在图论中假定存在的其他结构(几何位置) 。多面体中顶点的<font color="32cd32">顶点图形</font>类似于图中顶点的邻域。+ + + + + + + + + + + + + + + + + + +
无编辑摘要
若图包含由顶点<math>v</math>和<math>w</math>组成的边<math>(v,w)</math>，则称顶点<math>w</math>邻接于adjacent to顶点<math>v</math>;由所有邻接于<math>v</math>的顶点而组成 的图，被称为这些顶点的导出'''子图induced subgraph'''，它也被称为顶点<math>v</math>的'''邻域 neighborhood'''。
</br></br>
</br></br>
[[File:Small Network.png|alt=A small example network with 8 vertices and 10 edges.|thumb|用具有8个顶点(其中一个是孤立的)和10条边的网络示意。]]
[[File:Small Network.png|alt=A small example network with 8 vertices and 10 edges.|thumb|用具有8个顶点(其中一个是孤立的)和10条边的网络示意。]]
在抽象图中，顶点<math>v</math>的[[度 degree]]，记作<math>𝛿(v)</math>，是所有关联于<math>v</math>的边的数量。度为0的顶点被称作'''孤立顶点 isolated vertex'''，这样的顶点不是任何边的端点(如图2所示，这一抽象图中含有一个孤立顶点)<ref>[[:File:Small Network.png]]; example image of a network with 8 vertices and 10 edges</ref>
度为1的顶点被称为'''叶顶点 leaf vertex'''，也称<font color="#ff8000">叶子顶点、叶节点、悬挂顶点 pendant vertex</font>。
在有向图中，我们可以根据边的方向，把顶点的度分为出度 outdegree(也称出次数)，记作<math>𝛿<sup> +</sup>(v)</math>和入度 indegree(也称入次数)，记作<math>𝛿<sup>−</sup>(v)</math>。一个顶点的出度指的是，所有从这个顶点出发，连接其他顶点的箭头的数量。与此相反，一个顶点的入度指的是，所有从其他顶点出发，连接到这个顶点的箭头的数量。在有向图中，有可能出现两种顶点：源顶点 source vertex 和汇顶点 sink vertex。前者指入度为0的顶点，后者指出度为0的顶点。
若一个顶点的邻域恰好能构成[[团 clique]]，即这个顶点邻域中的任意两个顶点都是相邻的，那么这个顶点被称为'''单纯形顶点 simplicial vertex'''，也译为单纯顶点。与所有其他顶点相邻的顶点，被称为'''泛顶点 universal vertex'''。
若移除某一顶点(和所有以这个顶点为端点的边)后，图被分离为若干个彼此互不相连的子图，那么这 一顶点就被称为'''割顶点 cut vertex''';由割顶点构成的集合被称为顶点分离集。若一个连通图被移除少于<math>k</math>个顶点后，总能保持连通，那么这个图被称为<math>k-顶点连通图</math>。由两两不相邻的顶点所构成的集合，被称为独立集。由图中每条边的一个或两个端点所构成的集合，被称为顶点覆盖。图的顶点空间是向量空间，它的基向量与图的顶点相对应。
如果一个图具有将任何顶点映射到任何其他顶点的对称性，则该图是'''<font color="#ff8000">顶点传递</font>'''的。
如果一个图上存在某种<font color="#ff8000">自同构映射automorphism</font> <math>f: </math>，能把图中任意一个顶点<math>v</math>映射为图中的某个其他顶点<math>u</math> ，同时保持边不变，即若顶点<math>v<sub>1</sub>,v<sub>2</sub></math>相邻，那么顶点<math>f(v<sub>1</sub>)=u<sub>1</sub></math>和<math>f(v<sub>2</sub>)=u<sub>2</sub></math>也相邻，那么我们认为这个图是顶点传递的，这样的图具有某种相应的对称性质。
在<font color="32cd32">图计数</font>和'''<font color="#ff8000">图同构</font>'''的语境下，要注意区分'''有标注的顶点'''和'''无标注的顶点'''。有标注的顶点被关联了额外的信息，以区分这个顶点和其他有标注的顶点;这样一来，只有两个图顶点之间的对应关系是把具有相同标注的顶点配对起来，才能称这两个图是同构的。无标注的顶点，就是只能由其相邻关系而被区分的顶点。
在图计数或者图同构的语境中，若图中的顶点都是无标注的顶点，则可以不用考虑上面那样额外信息的影响。只要两个图之间存在顶点之间的映射<math>f: </math>，使得原来连通的顶点，在映射之后依然连通，就可以说这两个图是同构的。
图的顶点类似于但不等同于(高维)多面体的顶点。但多面体的顶点有额外的结构(几何位置)，在图论中未能被假定存在。换句话说，作为概念，图的顶点比多面体的顶点，要更抽象。多面体的骨架构成一个图，其顶点是多面体的顶点，但多面体的顶点有无法在图论中假定存在的其他结构(几何位置) 。多面体中顶点的<font color="32cd32">顶点图形</font>类似于图中顶点的邻域。
<br>
<br>