頂點(圖理論)

一個帶有6個頂點和7個邊緣的圖形,左側的頂點6是葉頂點或吊墜頂點

離散數學,更具體地說,在圖理論中,頂點(複數頂點)或節點是形成圖形的基本單元:一個無方向的圖由一組頂點和一組邊緣(無序的角度)組成,雖然有向圖由一組頂點和一組弧線組成(對頂點的有序對)。在圖的圖中,頂點通常由帶有標籤的圓表示,邊緣由從一個頂點延伸到另一個頂點的線或箭頭表示。

從圖理論的角度來看,頂點被視為無特徵和不可分割的對象,儘管它們可能取決於圖形的應用。例如,語義網絡是頂點代表概念或對像類別的圖形。

據說形成邊緣的兩個頂點是該邊緣的終點,據說邊緣被入射到頂點。如果該圖包含邊緣( VW ),則據說頂點w與另一個頂點V相鄰。頂點V鄰域是圖形的誘導子圖,由與V相鄰的所有頂點形成。

頂點類型

A small example network with 8 vertices and 10 edges.
具有8個頂點(其中一個是隔離的)和10個邊緣的示例網絡。

圖中表示𝛿(v)的頂點的程度是入射的邊緣數。孤立的頂點是一個零度的頂點。也就是說,一個不是任何邊緣端點的頂點(示例圖像說明了一個孤立的頂點)。葉頂點(也是吊墜頂點)是一個具有一度學位的頂點。在有向圖中,可以區分indegree(即傳入邊緣數)(表示+ (v))的超級(傳出邊緣數),表示𝛿 - (v);源頂點是一個固定零的頂點,而水槽頂點是一個具有超級零的頂點。一個簡單的頂點是一個鄰居形成一個集團的頂點:每兩個鄰居都相鄰。通用頂點是一個頂點,與圖中的其他每個頂點相鄰。

切割頂點是一個頂點,將其刪除將斷開其餘圖。頂點分離器是頂點的集合,將其刪除將其剩餘圖切成小塊。 k-vertex連接的圖是一個圖形,其中刪除少於k頂點的圖總是離開連接的剩餘圖。獨立集是一組頂點,沒有兩個是相鄰的,而頂點蓋是一組頂點,其中包含圖中每個邊緣的至少一個端點。圖的頂點空間是一個向量空間,其一組基礎向量與圖形的頂點相對應。

圖形是頂點傳遞的,如果它具有將任何頂點映射到任何其他頂點的對稱性。在圖表枚舉圖形同構的上下文中,區分標記的頂點未標記的頂點很重要。標記的頂點是一個與額外信息相關聯的頂點,可以將其與其他標記的頂點區分開。僅當其頂點之間的對應關係配對具有相等標記的頂點時,才能將兩個圖視為同構。一個未標記的頂點是僅基於圖中的鄰接而不是基於任何其他信息的任何其他頂點的頂點。

圖中的頂點類似於polyhedra的頂點:多面體的骨骼形成圖,其頂點是多面體的頂點,但是多面體頂點具有額外的結構(其幾何位置),這是不假定存在於圖理論中。多面體中頂點的頂點圖類似於圖中頂點的附近。

也可以看看