##### 图结构 - 图结构 - **图结构**使用一系列概念来刻画[[图]]的性质, 主要是顶点和边的性质和关系 - 图 $G = (V, E)$ - 顶点集 $V=\{v_1,v_2,\dots,v_n\}$ - 边集 $E=\{e_1,e_2,\dots,e_m\}$ - 无向边, 边是无序对 $e=\{v_1,v_2\}$ - 有向边, 边是有序对 $e=(v_1,v_2)$ - 多重边, 指两个顶点之间存在多条边 - 自环, 指一条边连接顶点到其自身 - 邻接关系, 指两个顶点通过一条边直接相连 - 邻域, 指所有与某个顶点相邻的顶点所构成的集合 $N(v)$ - 度, 指连接到该顶点的边的数量 $\deg(v)$, 自环算作 $2$ - 入度, 指有向图中进入顶点的边的数量 $\deg^-(v)$ - 出度, 指有向图中从顶点出发的边的数量 $\deg^+(v)$ - 孤立点, 指顶点度为 $0$ - 悬挂点, 指顶点度为 $1$ - 路径, 指两个顶点之间的一系列连续边的序列 - 简单路径, 指顶点不重复出现的路径 - 欧拉路径, 经过图中每条边恰好一次的路径 - 哈密顿路径, 经过图中每个顶点恰好一次的路径 - 路径长度, 是路径中边的数量 - 环, 指路径起点和终点相同的回路, 且至少包含三条边的路径