通用頂點

帶有通用頂點的圖, u

圖理論中,通用頂點是與圖形所有其他頂點相鄰的無向圖頂點。它也可以稱為主導頂點,因為它在圖中形成了一個單元的主導集。 (不應與圖形邏輯普遍量化的頂點混淆。)

包含通用頂點的圖可以稱為錐體。在這種情況下,通用頂點也可以稱為錐形的頂點。但是,該術語與Apex圖的術語衝突,其中頂點是一個頂點,其去除留下了平面子圖。

在特殊圖表中

恆星正好是具有通用頂點的,可以通過將通用頂點添加到獨立的集合中來構造。類似地,可以通過將通用頂點添加到循環圖中形成車輪圖。在幾何形狀中,三維金字塔具有車輪圖作為其骨骼,更普遍的圖表具有任何較高維的金字塔的圖形,具有通用頂點作為金字塔的頂點

瑣碎的完美圖訂單理論樹可比性圖)始終包含一個通用頂點,樹的根,更強烈地將它們表徵為每個連接的誘導子圖都包含通用頂點的圖。連接的閾值圖構成了瑣碎的完美圖的子類,因此它們還包含一個通用頂點。它們可以定義為可以通過重複添加通用頂點或孤立的頂點(一個沒有入射邊緣)形成的圖。

PaulErdősAlfrédRényiVeraT.Sós1966 )的友誼定理指出,如果有限圖中的每個兩個頂點都具有一個共享的鄰居,則該圖將包含一個通用的頂點。該定理描述的圖是友誼圖,由在通用頂點(通用頂點)上連接在一起的三角形系統形成。

每個具有通用頂點的圖形都是可拆卸的圖,這意味著它可以通過反复刪除其封閉的鄰域是其他頂點封閉社區的子集的頂點,從而將其簡化為單個頂點。將通用頂點置於適當的任何去除順序,刪除所有其他頂點,都適合此定義。幾乎所有可拆除的圖形都有一個通用頂點,從某種意義上說 - 具有通用頂點的vertex拆卸圖趨向於極限一個去無窮大。

作為觀察到的特殊情況,即統治數在強大的圖中最大程度地增加了,當且僅當其兩個因素都這樣做時,強產物具有通用頂點。

認出

在具有N頂點的圖表中,通用頂點是一個頂點,其完全n -1 。因此,像拆分圖一樣,具有通用頂點的圖形可以純粹通過其度序列識別,而無需查看圖的結構。

具有通用頂點的屬性可以通過圖表的一階邏輯中的公式表示。使用要指示圖中的鄰接關係,圖形當且僅當它對公式建模時,具有通用頂點

該公式的存在及其在通用量化器存在性量化器之間的少量交替,可用於固定參數可拖動算法中,用於測試圖形的所有組件是否可以通過通過使用的所有組件來通過commisition Pertices 。 從每個組件中刪除頂點的步驟。