頂點 (圖論)

形成圖形(圖論)的基本單位

數學中,更確切地說,在圖論中,一個頂點vertex,或多個頂點vertices)或節點node)是構成圖的基本單位:一個無向圖包括一個頂點的集合和一個(頂點的無序對)的集合,而一個有向圖包括一個頂點的集合和一個弧(頂點的有序對)的集合。在一個圖的示意圖中,一個頂點通常表示為一個帶標號的圓形,而一條邊表示為連接兩個頂點的一條直線或一個箭頭。

一個有六個頂點和七條邊的圖,其中最左邊標號為6的頂點是一個葉子頂點,或稱終端頂點

站在圖論的角度上,頂點被視為無特徵且不可分割的對象,雖然因為該圖的用途不同,他們可能有額外的結構;例如,一個語義網絡是一個圖,其頂點表示的是概念或對象的類別。

兩個被一條邊所連接的頂點稱作該邊的端點,且可以說該邊從一個點入射向另一個點。如果一個圖包含一條邊(v,w),則可以說頂點w相鄰頂點v。頂點v鄰域是該圖的一個導出子圖,由所有與v相鄰的頂點組成。

頂點的類型

編輯
 
有八個點(其中一個點為孤立頂點)和十條邊的樣例網絡。

一個頂點的,表示為𝛿(v),指的是在圖中與這個頂點相連的邊的數量。 一個孤立頂點是一個度為0的頂點:即不是任何一條邊的端點的頂點(樣例圖像描述了一個孤立頂點)。[1] 一個葉子頂點(亦稱終端頂點)是一個度為1的頂點。在一個有向圖中,可以分清某個節點的出度(從該節點指向其他節點的邊的數量),表示為𝛿 +(v),入度(從其他節點指向該節點的邊的數量),表示𝛿(v);源點是一個入度為0的頂點,而匯點則是一個出度為0的頂點。簡單點是其鄰接點形成一個的點,團中任意兩個點均相連。 完全點是一個連接了其餘頂點的頂點。

分割點是一個刪去後會導致剩餘圖不再連通的頂點;頂點分割集是一個刪去後會導致剩餘圖不再連通的頂點集合。 K-頂點連通圖是指一個刪去少於k個點總會使剩餘圖保持連通的圖。獨立集是一個沒有任意一對頂點相連的集合,而覆蓋是一個頂點的集合,圖中任意一條邊都至少有一個端點在此集合中。

如果圖的對稱性能使得任何頂點映射到任何其他頂點,則該圖是頂點傳遞圖。在圖枚舉圖同構的討論中,區分已標記頂點未標記頂點是很重要的。已標記頂點是一個帶有額外信息的頂點,使其能夠區別於其他標記的頂點;只有當兩個圖的頂點能有相同的標記節點時,兩個圖才認為是同構的。僅當基於其於圖中的鄰接點而不基於任何額外信息時,一個未標記的頂點才可以替代任何其他的頂點。

圖的頂點和多邊形的頂點有需多的相似之處,因此容易被混淆。多邊形的頂點和邊可以合起來被視為是一個圖,但是多邊形還額外描述了頂點的幾何位置,事實上,多邊形定義出來的圖一定是平面圖。多邊形的點的頂點圖則類似於圖的頂點的鄰居。

圖論中的頂點類似於多面體中的頂點,但還是有區別:多面體的網絡骨架形成的圖形其頂點為多面體的頂點,但多面體頂點具有圖理論中不存在的附加結構(其幾何位置)。多面體的頂點圖類似於圖論中的頂點鄰域。

參見

編輯

參考文獻

編輯
  1. ^ File:Small Network.png; example image of a network with 8 vertices and 10 edges

外部連結

編輯