頂點 (圖論)
在數學中，更確切地說，在圖論中，一個頂點（vertex，或多個頂點，vertices）或節點（node）是構成圖的基本單位：一個無向圖包括一個頂點的集合和一個邊（頂點的無序對）的集合，而一個有向圖包括一個頂點的集合和一個弧（頂點的有序對）的集合。在一個圖的示意圖中，一個頂點通常表示為一個帶標號的圓形，而一條邊表示為連接兩個頂點的一條直線或一個箭頭。
站在圖論的角度上，頂點被視為無特徵且不可分割的對象，雖然因為該圖的用途不同，他們可能有額外的結構；例如，一個語義網絡是一個圖，其頂點表示的是概念或對象的類別。
兩個被一條邊所連接的頂點稱作該邊的端點，且可以說該邊從一個點入射向另一個點。如果一個圖包含一條邊(v,w)，則可以說頂點w相鄰頂點v。頂點v的鄰域是該圖的一個導出子圖，由所有與v相鄰的頂點組成。
頂點的類型
[編輯]
一個頂點的度，表示為𝛿(v)，指的是在圖中與這個頂點相連的邊的數量。 一個孤立頂點是一個度為0的頂點：即不是任何一條邊的端點的頂點（樣例圖像描述了一個孤立頂點）。[1] 一個葉子頂點（亦稱終端頂點）是一個度為1的頂點。在一個有向圖中，可以分清某個節點的出度（從該節點指向其他節點的邊的數量），表示為𝛿 +(v)，入度（從其他節點指向該節點的邊的數量），表示𝛿−(v)；源點是一個入度為0的頂點，而匯點則是一個出度為0的頂點。簡單點是其鄰接點形成一個團的點，團中任意兩個點均相連。 完全點是一個連接了其餘頂點的頂點。
分割點是一個刪去後會導致剩餘圖不再連通的頂點；頂點分割集是一個刪去後會導致剩餘圖不再連通的頂點集合。 K-頂點連通圖是指一個刪去少於k個點總會使剩餘圖保持連通的圖。獨立集是一個沒有任意一對頂點相連的集合，而覆蓋是一個頂點的集合，圖中任意一條邊都至少有一個端點在此集合中。
如果圖的對稱性能使得任何頂點映射到任何其他頂點，則該圖是頂點傳遞圖。在圖枚舉和圖同構的討論中，區分已標記頂點和未標記頂點是很重要的。已標記頂點是一個帶有額外信息的頂點，使其能夠區別於其他標記的頂點；只有當兩個圖的頂點能有相同的標記節點時，兩個圖才認為是同構的。僅當基於其於圖中的鄰接點而不基於任何額外信息時，一個未標記的頂點才可以替代任何其他的頂點。
圖的頂點和多邊形的頂點有需多的相似之處，因此容易被混淆。多邊形的頂點和邊可以合起來被視為是一個圖，但是多邊形還額外描述了頂點的幾何位置，事實上，多邊形定義出來的圖一定是平面圖。多邊形的點的頂點圖則類似於圖的頂點的鄰居。
圖論中的頂點類似於多面體中的頂點，但還是有區別：多面體的網絡骨架形成的圖形其頂點為多面體的頂點，但多面體頂點具有圖理論中不存在的附加結構（其幾何位置）。多面體的頂點圖類似於圖論中的頂點鄰域。
參見
[編輯]參考文獻
[編輯]- ^ File:Small Network.png; example image of a network with 8 vertices and 10 edges
- Gallo, Giorgio; Pallotino, Stefano. Shortest path algorithms. Annals of Operations Research. 1988, 13 (1): 1–79. doi:10.1007/BF02288320.
- Berge, Claude, Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001)
- Chartrand, Gary. Introductory graph theory. New York: Dover. 1985. ISBN 0-486-24775-9.
- Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press. 1986. ISBN 0-19-853916-9.
- Harary, Frank. Graph theory. Reading, Mass.: Addison-Wesley Publishing. 1969. ISBN 0-201-41033-8.
- Harary, Frank; Palmer, Edgar M. Graphical enumeration. New York, Academic Press. 1973. ISBN 0-12-324245-2.