|
图的边和顶点的关系 无向边和顶点关系 若(v i v j )是一条无向边则称顶点v i 和v j 互为邻接点(Adjacent)或称v i 和v j 相邻接;并称(v i v j )依附 或关联(Incident)于顶点v i 和v j 或称(v i v j )与顶点v i 和v j 相关联 【例】下图G 中 ① 与顶点v 相邻接的顶点是v v 和v ② 关联于顶点v 的边是(v v )(v v )和(v v ) 有向边和顶点关系 若是一条有向边则称顶点v i 邻接到v j 顶点v i 邻接于顶点v j ;并称边关联于v i 和v j 或称与顶点v i 和v j 相关联 【例】在下图G 中关联于顶点v 的弧是和 顶点的度(Degree) ()无向图中顶点v的度(Degree) 无向图中顶点v的度(Degree)是关联于该顶点的边的数目记为D(v) 【例】上图G 中顶点v 的度为 ()有向图顶点v的入度(InDegree) 有向图中以顶点v为终点的边的数目称为v的入度(Indegree)记为ID(v) 【例】上图G 中顶点v 的人度为l ()有向图顶点v的出度(Outdegree) 有向图中以顶点v为始点的边的数目称为v的出度(Outdegree)记为OD(v) 【例】上图G 中顶点v 的出度为 注意 ①有向图中顶点v的度定义为该顶点的入度和出度之和即D(v)=ID(v)+OD(v) 【例】上图G 中顶点v 的人度为l出度为则度为 ②无论有向图还是无向图顶点数n边数e和度数之间有如下关系 |
