圖的邊和頂點的關系
無向邊和頂點關系
若(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和度數之間有如下關系
From:http://tw.wingwit.com/Article/program/sjjg/201311/23859.html
