詞彙表

另請參閱：命名圖的畫廊

這是圖理論的詞彙表。圖理論是對按線或邊緣成對連接的圖的圖，節點或頂點系統的研究。

符號

方括號 [ ]
g [ s ]是頂點子集的圖G的誘導子圖。
主要符號'
素符號通常用於修改圖形不變的符號，以便將其應用於界限圖而不是給定圖。例如， α （ g ）是圖的獨立數。 α '（ g ）是圖的匹配數，它等於其線圖的獨立性數。同樣， χ （ G ）是圖的色數。 χ '（ g ）是該圖的色素指數，它等於其線圖的色數。

A

吸收
吸收套件有向圖是一組頂點 ，從走向一個頂點 。
可觀的
圖形的可觀數量是完整著色中的最大顏色數。
無環
1.如果沒有循環，則圖是無環。無方向的無環圖與森林相同。一個無環的圖形，它是一個沒有定向循環的挖掘圖，通常稱為有向無環圖，尤其是在計算機科學中。
2.無向圖的無環著色是一種適當的著色，每兩種顏色類別都會誘導森林。
鄰接矩陣
圖的鄰接矩陣是一個矩陣，其行和列都由圖的頂點索引，當頂點i和j相鄰時，第i和列的單元格中的一個矩陣，另一個是一個矩陣，否則為零。
鄰近的
1.兩個頂點之間的關係都是相同邊緣的端點。
2.兩個共享端頂點的兩個不同邊緣之間的關係。
α
對於圖G ， α （ g ） （使用希臘字母alpha）是其獨立數（請參閱獨立），而α '（ g ）是其匹配數（請參閱匹配）。
交替
在具有匹配的圖表中，交替路徑是一條路徑，其邊緣在匹配和無與倫比的邊緣之間交替。同樣，交替的循環是一個週期，其邊緣在匹配和無與倫比的邊緣之間交替。增強路徑是從不飽和頂點開始和結束的交替路徑。可以找到較大的匹配，作為匹配和增強路徑的對稱差異。且僅當它沒有增強路徑時，匹配是最大的。
抗
在定向的無環圖中，成對無與倫比的頂點的子集s ，即在s中，從x到y或從y到x都沒有定向路徑。受部分排序集的抗小節概念的啟發。
反邊緣
非邊緣的同義詞，一對不可變化的頂點。
反三角形
三角形的三個獨立集，三角形的補充。
頂尖
1. Apex圖是一個圖形，其中可以刪除一個頂點，並留下平面子圖。刪除的頂點稱為頂點。 k -apex圖是可以通過刪除k頂點製成平面的圖。
2.通用頂點的同義詞，一個與所有其他頂點相鄰的頂點。
樹木
根和定向樹的同義詞；見樹。
弧
參見邊緣。
箭
有序的一對頂點，例如有向圖中的邊緣。箭頭（ x ， y ）有一個尾巴x ，一個頭y和一個從x到y的方向；據說Y是X和X的直接繼任者，是Y的直接前任。箭頭（ y ， x ）是箭頭（ x ， y ）的倒箭頭。
發音點
連接圖中的頂點，其去除將斷開圖形的連接。
-ary
K -Ary樹是一棵生根的樹，每個內部頂點都只有K子。一棵1-Ary的樹只是一條路。儘管該術語更恰當地指2-are樹，其中每個節點的孩子被區分為左或右子（每種類型中的最多），但該術語更恰當地指的是2-艾爾（每種節點）。如果每個內部頂點都有恰好的K子，則據說一棵K -Ary樹是完整的。
增強
一種特殊類型的交替路徑；請參閱交替。
自動形態
圖自動形態是圖形的對稱性，是圖形到自身的同構。

B

包
樹分解中的一組頂點之一。
均衡
如果其頂點分區的每個兩個子集彼此之間的尺寸，則兩分或多部分圖是平衡的。
帶寬
圖G的帶寬是最長的最小值的最小值，最小邊緣的長度（其兩個端點之間的訂單中的步驟數）。它也比最大間隔完成G的最大集團的大小少一個，以最大程度地降低集團的大小。
比克利克
完整的雙分圖或完整的雙方子圖的同義詞；請參閱完成。
雙連接
通常是2個連接的同義詞，但有時包括k 2 ，儘管不是2連接。見連接；對於雙連接組件，請參見組件。
綁定數
適當的頂點子集的鄰居數量與子集的大小的最小比率。
兩部分
雙方圖是一個圖形，其頂點可以分為兩個不相交的集合，以便一個集合中的頂點沒有相互連接，但可以連接到另一組中的頂點。換句話說，兩分的圖是沒有奇數循環的圖。同等地，這是一個可以與兩種顏色正確著色的圖。二分圖通常是寫入g =（ u ， v ， e ）的，其中u和v是每種顏色的頂點的子集。但是，除非該圖連接，否則它可能沒有唯一的2色。
雙重
雙重圖是一個兩分圖，其中只有兩個不同的頂點度，一個針對每組頂點兩部分。
堵塞
1.圖G的塊是最大子圖，它是孤立的頂點，橋邊緣或2個連接子圖。如果一個塊是2連接的，則其中的每對頂點屬於一個共同的循環。圖的每個邊緣恰好屬於一個塊。
2.圖G的塊圖是另一個圖形，其頂點是G的塊，當相應的塊共享一個鉸接點時，邊緣連接兩個頂點；也就是說，它是g的塊的相交圖。任何圖的塊圖都是森林。
3.圖G的塊切割（或塊切口）圖是一個兩部分圖，其中一個partite集由g的切割事件組成，另一個零件集由頂點組成對於每個塊 g 。連接G時，其塊切口圖是一棵樹。
4.塊圖（如果連接的話，也稱為集團樹，有時被錯誤地稱為Husimi樹）是所有塊都是完整的圖形的圖。 森林是一個塊圖；因此，尤其在任何圖的塊圖中都是塊圖，並且每個塊圖都可以構造為圖形的塊圖。
紐帶
最小切割集：一組邊緣的邊緣斷開圖形，沒有適當的子集具有相同的屬性。
書
1.書籍，書形或三角形書是完整的三方圖K 1,1， n ； N Triangles的集合加入了共享邊緣。
2.另一種類型的圖形，也稱為書籍或四邊形書籍，是在共享邊緣加入的4個環境的集合；具有邊緣的星星的笛卡爾產品。
3.書籍的嵌入是將圖形嵌入到拓撲書上，這是通過沿著共享線條加入半播放的空間。通常，嵌入的頂點必須在線上，這稱為嵌入式的脊柱，並且嵌入的邊緣必須躺在單個半平面中，這是本書的一個頁面之一。
邊界
1.在嵌入圖中，邊界步行是一個子圖，該子圖包含所有入射邊緣和頂點。
荊棘
Bramble是相互觸摸連接的子圖的集合，如果兩個子圖共享頂點，則兩個子圖觸摸，或每個子圖包括一個邊緣的一個端點。棕褐色的順序是一組頂點的最小尺寸，該頂點與所有子圖具有非空的交集。圖的樹寬是其任何荊棘的最大順序。
分支
一項度數兩個頂點的路徑，以與兩個程度不相等的頂點結束。
分支分解
G的分支分解是G的邊緣的分層聚類，由無根的二進制樹表示，其葉子由G的邊緣標記為葉子。分支分解的寬度是該二進制樹的邊緣E的最大值，是由g在兩個子樹中的g邊緣確定的子圖之間的共享頂點的數量。 G的分支是G的任何分支分解的最小寬度。
分支寬度
請參閱分支分解。
橋
1.橋，地峽或切割邊緣是一個邊緣，其去除將斷開圖形的連接。無橋圖是沒有橋樑的圖。等效地，一個2邊緣連接的圖。
2.尤其是在平面測試的背景下，一個循環的橋是最大的子圖，它與週期不相交，並且每個邊緣屬於一個內部與週期內內部分離的路徑。和弦是一座邊緣橋。外圍週期是一個循環，最多是一個橋。它必須是其圖的任何平面嵌入中的面孔。
3.一個循環的橋也可能意味著連接一個循環的兩個頂點但比連接相同兩個頂點的循環中的任何一個路徑的路徑。橋接圖是一個圖形，其中四個或多個頂點的每個週期都有一個橋。
無用的
無橋圖是沒有橋邊緣的圖。也就是說，一個2邊緣連接的圖。
蝴蝶
1.蝴蝶圖具有五個頂點和六個邊緣；它由兩個共享頂點的三角形形成。
2.蝴蝶網絡是一個與分佈式計算中的網絡體系結構的圖，與立方體連接的循環密切相關。

C

C
c n是n -vertex循環圖；參見週期。
仙人掌
仙人掌圖，仙人掌樹，仙人掌或Husimi樹是一個連接的圖，每個邊緣最多屬於一個週期。它的塊是循環或單個邊緣。此外，如果每個頂點最多屬於兩個塊，則稱為聖誕仙人掌。
籠
籠子是一個常規圖，其周長可能最小。
典範
批判性
圖形的規範形式是一個不變的，因此，只有當它們是同構時，兩個圖具有相等的不變性。規範形式也可以稱為規範不變式或完整的不變性，有時僅針對特定圖的圖表定義。圖形典寫是計算規範形式的過程。
卡片
通過刪除一個頂點，尤其是在重建猜想的上下文中，由給定圖形形成的圖。另請參見Deck ，這是圖的所有卡的多鍵。
雕刻寬度
雕刻寬度是類似於分支寬的圖形寬度的概念，而是使用頂點的層次聚類而不是邊緣的層次聚類。
毛蟲
毛毛蟲樹或毛毛蟲是一棵樹，內部節點會引起路徑。
中心
圖的中心是最小偏心率的頂點集。
鏈
1. 步行的同義詞。
2.在將代數拓撲的方法應用於圖形時，鏈複合物的元素，即一組頂點或一組邊緣。
臉頰常數
參見擴展。
櫻桃
櫻桃是三個頂點的路徑。
χ
χ （ g ） （使用希臘字母chi）是g的色數， χ '（ g ）是其色度指數。參見色彩和著色。
孩子
在根系的樹上，頂點V的孩子是沿向外邊緣的V的鄰居，該鄰居遠離根部。
弦
和弦
1.一個循環的和弦是不屬於循環的邊緣，兩個端點都屬於週期。
2.和弦圖是一個圖形，其中四個或多個頂點的每個循環都具有和弦，因此唯一的誘導循環是三角形。
3.強烈的和弦圖是一個和弦圖，其中每個長度六個或更多的循環都具有奇數和弦。
4.弦弦二分的圖不是弦（除非它是森林）；這是一個兩分圖，其中六個或多個頂點的每個循環都具有和弦，因此唯一的誘導週期是4個循環。
5.圓圈的和弦是線段連接圓上兩個點的線段；和弦集合的相交圖稱為圓形圖。
色
與著色有關；請參閱顏色。色圖理論是圖形的理論。色數χ （ G ）是G的適當著色所需的最小顏色數量。 χ '（ g ）是G的色素，是G的適當邊緣著色所需的最小顏色數量。
可選擇
可用性
如果每個頂點都有可用的顏色列表，則圖表可k- ous可以。該圖的可選性是其最小的k -Choosable 。
圓圈
圓形圖是圓圈和弦的相交圖。
電路
電路可能是指封閉的小徑或循環空間的元素（歐拉（Eulerian）跨越子圖）。圖的電路等級是其循環空間的維度。
圓周
圖的周長是其最長簡單循環的長度。當且僅當其周長等於其順序時，該圖是Hamiltonian。
班級
1.一類圖形或圖形家族是圖形的（通常是無限的）集合，通常定義為具有某些特定屬性的圖。使用“類”一詞而不是“集”，因為除非做出特殊限制（例如限制要從特定集合繪製的頂點，而定義為兩個頂點的邊緣）類別類別類別通常不設置使用集合理論正式化時。
2.彩色圖的顏色類是具有特定顏色的頂點或邊緣的集合。
3.在Viping的定理的背景下，在邊緣著色的簡單圖上，如果其色度指數等於其最大程度，則據說圖形是一類，如果其彩色索引等於一和級別，則圖形為第二。根據Viping的定理，所有簡單的圖形均為第一類或第二類。
爪
爪子是一棵樹，有一個內部頂點和三片葉子，或等效地將完整的兩部分圖k 1,3 。無爪圖是一個沒有誘導子圖的圖形。
集團
一個集團是一組相互相鄰的頂點（或該集合引起的完整子圖）。有時，一個集團被定義為最大的相互鄰接頂點（或最大完整子圖），它不屬於任何較大的此類集合（或子圖）。 k -clique是k級的集團。圖G的集團數ω （ g ）是其最大集團的順序。圖G的集團圖是G中最大列的交點圖。另請參見Biclique ，這是一個完整的雙方子圖。
集團樹
塊圖的同義詞。
集團寬度
圖G的集團寬度是通過創建標記為頂點的操作構造G所需的不同標籤數量的最小數量所有帶有給定標籤的頂點。最多2個集團寬度的圖形恰好是Caphichs 。
關閉
1.封閉的社區是其中的中央頂點；見鄰里。
2.封閉的步行是從同一頂點開始和結束的。參見步行。
3.如果圖等於其自身的及時閉合，則圖形將閉合；請參閱及物。
4.圖形屬性是在圖形上的某些操作下關閉的，如果每當對操作的參數或參數具有該屬性時，結果也是如此。例如，遺傳性質在誘導的子圖下關閉；單調特性在子圖下關閉；未成年人在未成年人的情況下關閉次要的特性。
關閉
1.有關有向圖的及時閉合，請參見及物。
2.有向圖的閉合是一組頂點，這些頂點沒有閉合外頂點的外向邊緣。例如，水槽是一個單vertex閉合。關閉問題是找到最小或最大重量的關閉問題。
共同
該前綴的各種含義通常涉及補體圖。例如， Cograph是由包括補充的操作產生的圖表。 cocoloring是一種著色，每個頂點都會誘導獨立集（如適當的著色）或集團（如補體的著色）。
顏色
染色
1.圖形著色是圖形的標記圖，該標記是通過給定顏色集中的元素，或等效地將頂點的分區分配到子集中，稱為“顏色類”，每種都與其中一種顏色相關聯。
2.一些作者使用“著色”，沒有資格，表示適當的著色，將不同的顏色分配給每個邊緣的端點。在圖形著色中，目標是找到一種適當的著色，該著色使用盡可能少的顏色。例如，兩分的圖是具有兩種顏色的圖形，四種顏色定理指出，每個平面圖都可以用最多四種顏色顏色。如果可以（如果可能的話）（可以正確地）顏色（ k-顏色），則據說它是k顏色的，如果可能的話，則可以使用k顏色。
3.已經研究了許多顏色的變化，包括邊緣著色（著色邊緣，因此沒有兩個具有相同端點的邊緣共享顏色），列表著色（每個頂點的適當著色僅限於可用顏色的子集）， acyclic Coloring （每個2色的子圖是無環的），共彩色（每個顏色類都誘導獨立集或集合），完整的著色（每兩個顏色類別具有一個邊緣）和總顏色（邊緣和頂點都有彩色）。
4.圖的著色數是一個加上墮落的。之所以這樣稱呼，是因為將貪婪的著色算法應用於圖形使用最多多種顏色的變性順序。
可比性
如果其頂點是部分有序集的元素，並且兩個頂點在部分順序上可比時相鄰，則無向圖是一個可比性圖。同等地，可比性圖是具有傳遞方向的圖。許多其他類的圖形可以定義為特殊類型的部分順序的可比性圖。
補充
補體圖簡單的圖G是與G相同的頂點集上的另一個圖形，每個在G中不相鄰的頂點的邊緣。
完全的
1.完整的圖是每個兩個頂點相鄰的一個：可能存在的所有邊緣。具有n個頂點的完整圖通常表示為k n 。完整的兩分圖是一個完整的圖形，其中一個頂點隔板相對兩側的每個兩個頂點相鄰。一個完整的兩分圖在分區的一側具有頂點，另一側的B頂點通常表示為k a ， b 。相同的術語和符號也已擴展到完整的多部分圖，將頂點分為兩個以上的子集，並且不同子集中的每對頂點都相鄰；如果子集中的頂點數為a ， b ， c ，... ，則該圖表示為k a ， b ， c ，...。
2.給定圖的完成是具有一些理想屬性的超圖。例如，和弦完成是一個和弦圖。
3.完整的匹配是完美匹配的同義詞；請參閱匹配。
4.完整的著色是一種適當的著色，其中每對顏色都用於至少一個邊緣的端點。每種具有最少顏色數量的著色都是完整的，但是可能存在更大顏色的完整顏色。圖形的可觀數量是完整著色中的最大顏色數。
5.圖的完整不變是規範形式的同義詞，該形式的不變式具有不同的非構形圖值。
成分
圖的連接組件是最大連接的子圖。該術語還用於具有更高連接性的圖形頂點的最大子圖或子集，包括雙連接組件，三連接組件和強烈連接的組件。
縮合
有向圖G的冷凝是一個有向的無環圖，該圖具有一個頂點，對於G的每個強烈連接的組件，以及一個包含G中至少一個邊緣的兩個端點的組件的邊緣連接對。
錐體
包含通用頂點的圖。
連接
導致連接。
連接的
連接的圖是每對頂點形成路徑端點的圖。較高形式的連接性包括有向圖中的強連通性（對於每個兩個方向都有一個從一個到另一個的路徑）， k -vertex連接的圖（刪除少於k頂點無法斷開圖），而k -gedge - 連接的圖（刪除少於K邊緣無法斷開圖形）。
連接的組件
組件的同義詞。
交談
匡威圖是轉置圖的同義詞。參見轉置。
核
1. A k核是通過去除所有小於K的頂點而形成的誘導子圖，並且在較早去除後，其度量的所有頂點都比K少於K。見墮落。
2.核心是圖G ，使得每個圖從G到自身的同態同態都是同構的。
3.圖G的核心是最小圖H ，因此從G到H的同構存在，反之亦然。 H是獨一無二的同構。它可以表示為G的誘導子圖，並且是其所有自同構的意義上都是同構。
4.在圖形匹配的理論中，圖的核心是其絨毛 - 孟德爾松分解的一個方面，形成了所有最大匹配的結合。
科特里
1.跨樹的補充。
2.用來描述Cograph的生根樹結構，其中每個cograph頂點是樹的葉子，樹的每個內部節點都標記為0或1樹上的祖先標記為1。
覆蓋
頂點封面是一組到圖表中每個邊緣的頂點。邊緣蓋是向圖中每個頂點的一組邊緣。圖形的一組子圖覆蓋了圖形，如果其聯合（將頂點和邊緣）等於圖形。
批判的
給定屬性的關鍵圖是具有該屬性的圖形，但由於刪除單個頂點而形成的每個子圖都沒有屬性。例如，一個關鍵因素圖是每個頂點刪除的完美匹配（1因子）的圖，但是（因為它具有奇數的頂點）沒有完美的匹配本身。比較hypo- ，用於沒有屬性的圖形，但每個單vertex刪除都可以。
立方體
立方體
1.立方體圖，八個vertex圖表的頂點和邊緣的邊緣。
2.超立方體圖，對立方體圖的高維概括。
3.折疊的立方體圖，是由HyperCube形成的，通過添加相反的頂點匹配的連接。
4.一半的立方體圖，超立方體圖的半平方。
5.局部立方體，超立方體的遠距離子圖。
6.圖G的立方是圖形g 3 。
7.三次圖形圖形圖，一個3個常規圖的另一個名稱，每個頂點具有三個入射邊緣。
8.與立方體連接的循環，這是一個立方圖，該圖是通過循環替換了Hypercube的每個頂點而形成的。
切
切割
剪切是圖形的頂點的一個分區分為兩個子集，或者（如果該集合是非空的，則跨越這樣的分區的邊緣）的集合（也稱為切割集）。據說，如果兩個子集都有端點，則可以跨越該分區。因此，從連接的圖中刪除切割機將其斷開連接。
切點
請參閱發音點。
切空間
圖的切割空間是GF（2） -矢量空間，其插圖的切割s作為其元素和集合的對稱差異作為其向量加法操作。
循環
1.一個週期可以是一種圖形或步行。作為步行，它可能是封閉的步行（也稱為遊覽），或者通常是封閉的步行，而無需重複的頂點和邊緣（也稱為簡單的周期）。在後一種情況下，通常將其視為圖，即，第一個頂點和方向的選擇通常不重要。也就是說，循環排列和步行的逆轉產生相同的周期。重要的特殊類型的循環包括哈密頓循環，誘導循環，周圍週期和最短循環，這些循環定義了圖的周長。 k循環是長度為k的周期；例如， 2循環是Digon ，而3循環是三角形。循環圖是一個本身就是一個簡單循環的圖。具有N頂點的循環圖通常表示C n 。
2.週期空間是圖形中簡單週期產生的矢量空間，通常在2個元素的字段上，也是其他字段。

D

dag
定向無環圖的縮寫，這是一個無向周期的有向圖。
甲板
通過以所有可能的方式刪除單個頂點，尤其是在重建猜想的背景下，由單個圖G形成的圖形。通過以所有可能的方式刪除單個邊緣，以相同的方式形成邊緣甲板。甲板上的圖形也稱為卡。另請參見關鍵（具有任何卡的屬性的圖形）和hypo- （沒有所有卡持有的屬性的圖形）。
分解
請參閱樹分解， 路徑分解或分支分解。
退化
退化
k分級圖是一個無方向的圖，其中每個誘導的子圖最多都具有最低度k 。圖的變性是其為k基化的最小的k 。退化排序是對頂點的排序，使每個頂點在誘導的亞圖和後來的頂點的誘導子圖中具有最低度。在k分級圖的退化順序中，每個頂點最多都有後來的鄰居。退化也稱為k核數，寬度和鏈接，一個加上墮落的也稱為著色號或szekeres -wilf數字。 k -devenate圖也稱為k感應圖。
程度
1.圖中頂點的程度是其入射邊緣的數量。圖G的程度（或最大程度）是其頂點的最大程度，通常表示δ（ g ） ； G的最小度是其頂點度的最小值，通常表示δ （ g ） 。學位有時稱為價值； g中的V度可以表示為d g （ v ） ， d （ g ）或deg（ v ） 。總學位是所有頂點的程度的總和；通過握手，這是一個偶數的數字。度序列是所有頂點的度的集合，以從最大到最小的排序順序排序。在有向圖中，可以區分級內（傳入邊緣的數量）和超級（外向數）。
2.圖的同態度是其Hadwiger編號的同義詞，即最大的集團小調的順序。
Δ, δ
δ（ g ） （使用希臘字母增量）是g中頂點的最大程度， δ （ g ）是最小程度。見學位。
密度
在n個節點的圖中，密度是圖表的邊數與n個節點上完整圖中的邊數的比率。請參閱密集圖。
深度
根部樹中節點的深度是從根到節點的路徑中的邊數。例如，根的深度為0，其相鄰節點中任何一個的深度均為1。這是節點減去的級別。但是，請注意，有些作者相反使用深度作為節點級別的同義詞。
直徑
連接圖的直徑是最短路徑的最大長度。也就是說，這是圖表中頂點對之間的最大距離。如果該圖的邊緣上有權重，則其加權直徑通過沿路徑的邊緣的總和來測量路徑長度，而未加權的直徑將路徑長度通過邊緣的數量測量。對於斷開的圖形，定義有所不同：直徑可以定義為無限的，也可以定義為連接組件的最大直徑，也可能是未定義的。
鑽石
鑽石圖是一個無向圖，具有四個頂點和五個邊緣。
息肉
緊密連接。 （不要與斷開連接混淆）
Digon
Digon是一個簡單的循環，在有向圖或多編碼中的長度二。 Digon不能以簡單的無向圖發生，因為它們需要兩次重複相同的邊緣，這違反了簡單的定義。
Digraph
有向圖的同義詞。
Dipath
看到定向路徑。
直接的前身
尾部的尾部，其頭部為給定頂點。
直接繼任者
導向邊的頭部的頭是給定頂點的。
指導
有向圖是邊緣具有從一個頂點到另一個頂點的區別方向的圖。在混合圖中，有向邊是具有區別方向的邊緣。定向邊緣也可以稱為弧或箭頭。
導向弧
請參閱箭頭。
導向邊緣
請參閱箭頭。
定向線
請參閱箭頭。
定向路徑
所有邊緣S都具有相同方向的路徑。如果導向路徑從頂點X到頂點Y ，則X是Y的前身， Y是X的繼任者， Y可以從X 到達。
方向
1. 圖中兩個相鄰頂點之間的不對稱關係，表示為箭頭。
2. 有向路徑中兩個頂點之間的不對稱關係。
斷開
導致斷開連接。
斷開連接
未連接。
脫節
1.如果兩個子圖沒有共享邊緣，則兩個子圖是邊緣脫節，如果沒有共享頂點，則頂點不相交。
2.兩個或多個圖的不相交聯合是一個圖形，其頂點和邊緣集是相應集合的不相交聯合。
距離
圖中任意兩個頂點之間的距離是最短路徑的長度，其兩個頂點是其端點。
DIMATIC
圖形的迪戈因分區是頂點分配到主體集合中的一個分區。圖形的迪博特數是這種分區中的最大統治集數。
主導
主導集是一組頂點，其中包括或與圖中的每個頂點相鄰；不要將其與頂點蓋混淆，頂點蓋是一個入射到圖中所有邊緣的頂點集。重要的特殊類型的主導集包括獨立的統治集（也是獨立集的主導集）和連接的主導集（誘發連接子圖的主導集）。單個vertex主導集也可以稱為通用頂點。圖的主導數是最小的主導集中的頂點數。
雙重的
平面圖G的雙圖是一個圖形，該圖為G的每個面都有一個頂點。

E

E
e （ g ）是G的邊緣集；請參閱邊緣設置。
耳朵
圖的耳朵是一條路徑，其端點可能重合，但否則沒有頂點或邊緣的重複。
耳朵分解
耳朵的分解是圖表的邊緣分配為一系列耳朵，每個耳朵的終點（第一個之後）都屬於先前的耳朵，並且每個耳朵的內部點不屬於任何先前的耳朵。敞開的耳朵是一條簡單的路徑（耳朵沒有重複的頂點），開放的耳朵分解是耳朵分解，其中第一個耳朵打開後的每個耳朵；當且僅當其雙連接時，圖具有開放的耳朵分解。如果耳朵有奇數的邊緣，則耳朵是奇怪的，而奇怪的耳朵分解是每隻耳朵奇數的耳朵分解。當且僅當其至關重要時，圖具有奇怪的耳朵分解。
偏心
頂點的偏心率是距任何其他頂點的最遠距離。
邊緣
邊緣（與頂點一起）是構造圖形的兩個基本單元之一。每個邊緣都有兩個（或在超圖中，更多）附加的頂點，稱為其端點。邊緣可能是指向或無方向性的；無方向的邊緣也稱為線條，有向邊緣也稱為弧形或箭頭。在一個無方向的簡單圖中，可以將邊緣表示為其頂點集，並且在有向簡單的圖中，它可以表示為有序的一對頂點。連接頂點x和y的邊緣有時會寫入xy 。
邊緣切割
一組邊的s，其去除s 可斷開圖形。單邊切割稱為橋， 地峽或切割邊緣。
邊緣設置
給定圖G的一組邊緣，有時用E （ g ）表示。
無染色圖
在給定的一組頂點上的無進出圖或完全斷開的圖形是沒有邊緣的圖形。有時稱為空圖，但該術語也可以指無頂點的圖形。
嵌入
圖形嵌入是圖形作為拓撲空間的子集的拓撲表示，每個頂點表示為一個點，每個邊緣表示為曲線，邊緣的端點為曲線的端點，並且在頂點或角度或角度之間沒有其他相互作用邊緣。平面圖是一個將這種嵌入在歐幾里得平面上的圖，並且環形圖是一個將這種嵌入在圓環上的圖。圖的屬是二維流形的最小可能屬，可以嵌入它。
空圖
1.在一組非空的頂點上的無進出圖。
2.零訂單零圖，一個沒有頂點且沒有邊緣的圖形。
結尾
無限圖的末端是射線的等效類別，如果有第三射線包含兩個射線，則兩個射線是等效的。
端點
兩個頂點中的一個由給定邊緣或步行，步道或路徑的第一個或最後一個頂點之一連接在一起。給定的定向邊緣的第一個終點稱為尾部，第二個端點稱為頭部。
枚舉
圖枚舉是在給定的圖中計數圖作為其順序的函數的問題。更一般而言，枚舉問題可以指計算特定類別的組合對象（例如集團，獨立集，顏色或跨越樹）的問題，或者是算法列出所有此類對象的算法。
歐拉
歐拉（Eulerian）路徑是一條步行，它可以精確地使用圖形的每個邊緣。 Eulerian Circuit（也稱為Eulerian循環或Euler Tour）是一條封閉的步行路程，它準確地使用了一次。歐拉圖是具有歐拉電路的圖。對於無方向的圖，這意味著該圖是連接的，並且每個頂點都具有甚至程度。對於有向圖，這意味著該圖已密切連接，並且每個頂點具有等級等級。在某些情況下，連通性要求鬆開，僅滿足度要求的圖稱為Eulerian。
甚至
可除以兩個；例如，一個均勻的周期是一個循環，其長度均勻。
擴展器
擴展器圖是一個圖形，其邊緣膨脹，頂點膨脹或光譜膨脹被遠離零界定。
擴張
1.圖G的邊緣膨脹，等級數或cheeger常數是最小比率，比g的最多s的子集s ，s的邊數的最多比率， s在s中的邊緣數量與s中的頂點數量。
2.頂點的膨脹，頂點等數數或圖G的放大倍數是最小比率。 s 。
3.圖G的唯一鄰域擴展是最小比率，而不是G的最大範圍，S的最小比率是S之外的頂點的數量，但與s中的唯一頂點與s中的頂點數量相鄰。
4. D規則圖G的光譜膨脹是其鄰接矩陣的最大特徵值D與第二大特徵值之間的光譜差距。
5.如果其所有R -Shollow的未成年人的邊緣與由R的函數界定的邊緣與頂點的比例，並且如果R的函數是多項式，則圖形的膨脹家族具有界限。

F

臉
在平面圖或圖形嵌入中，嵌入的平面或表面子集的連接成分與圖形不相交。對於嵌入飛機上的嵌入，除了一張臉以外的所有面孔都將受到界限。延伸到無窮大的一個特殊面孔稱為外表面。
因素
圖的一個因素是跨越子圖：包括圖的所有頂點的子圖。該術語主要用於常規子圖的背景： k因子是k期限的因素。特別是， 1個因子與完美匹配是同一件事。關鍵因素圖是一個圖形，刪除任何一個頂點都會產生具有1個因子的圖形。
分解
圖分解是圖形邊緣分為因素。 k因子是k因子的分區。例如， 1-效應是一個邊緣著色，每個頂點都在每種顏色的邊緣中入射。
家庭
課堂的同義詞。
有限
如果圖具有有限數量的頂點和有限數量的邊緣，則圖是有限的。許多消息來源都認為所有圖都是有限的，沒有明確的話。如果每個頂點都有有限數量的入射邊緣，則圖是局部有限的。無限圖是一個不是有限的圖：它具有無限的許多頂點，無限的邊緣或兩者兼而有之。
第一個訂單
圖的一階邏輯是一種邏輯形式，其中變量代表圖的頂點，並且存在二進制謂詞來測試兩個頂點是否相鄰。要區分二階邏輯，其中變量還可以表示一組頂點或邊緣。
-flap
對於一組頂點X ， X -Flap是通過刪除X形成的誘導子圖的連接組件。皮瓣術語通常用於避風港的背景下，該功能將較小的頂點映射到其襟翼。另請參見循環的橋，這是循環頂點的襟翼或循環的和弦。
禁止
禁忌的圖表是圖表的表徵是沒有其他圖形，例如子圖，誘導的子圖或未成年人的圖形。如果H是不作為子圖，誘導子圖或次要出現的圖形之一，則據說H被禁止。
強迫圖
強製圖是圖H ，因此在圖序列G（n）的圖中評估H的子圖密度足以測試該序列是否為Quasi-random 。
森林
森林是一個沒有循環的無向圖（不一根的樹木的不相交的結合），或者是形成的有針對性的圖形，作為根植樹的不連同結合。
frucht
1.羅伯特·弗魯赫特（Robert Frucht）
2. Frucht圖，這是兩個沒有非平凡對稱性的最小立方圖之一。
3. Frucht的定理，每個有限組都是有限圖的對稱組。
滿的
誘導的同義詞。
功能圖
功能圖是一個有向圖，每個頂點都具有超級圖。同等地，功能圖是最大的定向偽井。

G

G
通常用來表示圖形的變量。
屬
圖的屬是可以嵌入其表面的最小屬。見嵌入。
大地
作為一個名詞，大地測量是最短路徑的同義詞。當用作形容詞時，它意味著與最短路徑或最短路徑距離有關。
巨大的
在隨機圖理論中，巨型組件是一個連接的組件，包含圖形頂點的恆定分數。在隨機圖的標準模型中，通常最多有一個巨型組件。
周長
圖的周長是其最短循環的長度。
圖形
圖理論中研究的基本對象，這是一個通過邊緣成對連接的頂點系統。根據邊緣是否具有方向，通常將其細分為有向圖或無向圖。混合圖包括兩種類型的邊緣。
貪婪的
由貪婪算法產生。例如，圖形的貪婪著色是通過在某個序列中考慮頂點並將每個頂點分配的第一個可用顏色來產生的著色。
Grötzsch
1.HerbertGrötzsch
2.Grötzsch圖，最小的無三角形圖，需要在任何適當的著色中進行四種顏色。
3.Grötzsch的定理，即始終可以將無三角形的平面圖與最多三種顏色一起顏色。
Grundy號碼
1.圖形的Grundy數量是貪婪著色產生的最大顏色數，並具有不良選擇的頂點排序。

H

H
一個通常用來表示圖的變量，尤其是當G g已用G表示另一個圖表時。
h-彩色
圖G的h顏色（其中H也是圖）是從H到G的同態。
h-免費
如果沒有誘導的子圖同構為H ，則圖形為H ，即如果H是禁止誘導的子圖。無h -free圖是所有圖形（或通常是所有有限圖）的家族。例如，無三角形圖是沒有三角形圖作為子圖的圖。 h -free始終是世襲的。如果圖沒有較小的同構H ，則圖形不含h 。
哈德威格
1.雨果·哈德威格（Hugo Hadwiger）
2.圖的Hadwiger數量是該圖最大的完整次要的訂單。它也稱為收縮集團數量或同態性。
3. Hadwiger的猜想是Hadwiger編號永遠不小於色數的猜想。
哈密​​頓
哈密​​頓路徑或哈密頓循環是一個簡單的跨越路徑或簡單的跨越週期：它涵蓋了圖中的所有頂點。如果包含哈密頓量週期，則圖是哈密頓量，如果它包含哈密頓路徑，則可以追溯。
避風港
k -Haven是一個函數，將少於K頂點的每組X映射到其一個襟翼之一，通常滿足其他一致性條件。避風港的順序是數字k 。避風港可用於表徵有限圖的樹寬以及無限圖的末端和哈德威格數量。
高度
1.根部樹中節點的高度是最長路徑中的邊數，遠離根部（即它的節點的深度嚴格增加），從該節點開始，並在葉子上結束。
2.根樹的高度是其根的高度。也就是說，一棵樹的高度是最長路徑中的邊數，它遠離根部，從根開始，並在葉子上結束。
3.有向無環圖的高度是該圖中有向路徑的最大長度。
遺傳
圖形的遺傳性質是在誘導子圖下關閉的特性：如果G具有遺傳性特性，那麼G的每個引起的子圖都必須。比較單調（在所有子圖下關閉）或次要封閉（在未成年人下關閉）。
六邊形
一個簡單的循環，恰好由六個邊緣和六個頂點組成。
洞
孔是四個或更多的誘導循環。一個奇數是一個奇數長的孔。抗孔是四個序列的誘導子圖，其補體為循環。同等地，它是補體圖中的一個孔。該術語主要用於完美圖的上下文，其特徵在於沒有奇數孔或奇數抗孔的強圖定理是圖形。無孔的圖與弦圖相同。
同態等效性
如果存在兩個同態，則兩個圖是同等的，每個圖是從每個圖到另一個圖的。
同態
1.圖同構是從一個圖的頂點集到另一個圖的頂點集的映射，該頂點將相鄰頂點映射到相鄰的頂點。這種類型的映射是圖形理論方法中最常用的映射。正確的圖形著色可以等效地描述為與完整圖的同態。
2.圖的同態度是其Hadwiger編號的同義詞，即最大的集團小調的順序。
Hyperarc
有向HyperEdge具有源和目標集。
Hyperedde
與圖形邊緣完全具有兩個端點的要求相比，超圖中具有多數端點的邊緣。
超立方體
HyperCube圖是由幾何超立方體的頂點和邊緣形成的圖。
超圖
超圖是圖形的概括，其中每個邊緣（在此上下文中稱為HyperEdge）可能具有兩個以上的端點。
低
該前綴與圖形屬性結合使用，指示一個沒有屬性的圖形，但通過刪除單個頂點形成的每個子圖確實具有該屬性。例如， Hypohamiltonian圖是沒有哈密頓週期的圖形，但是每個單vertex刪除都會產生哈密頓頓子圖。比較關鍵，用於具有屬性的圖形，但每個vertex刪除卻沒有。

I

內度
有向圖中的傳入邊緣數；見學位。
發病率
圖中的發生率是頂點邊對，使頂點是邊緣的終點。
入射矩陣
圖形的入射矩陣是一個矩陣，其行被圖的頂點索引，其列被邊緣索引，當for i和gend j是i和gend j時， i和c列的單元格中的一個和一個。否則為零。
事件
邊緣與其終點之一之間的關係。
無與倫比
無與倫比的圖是可比性圖的補充。請參閱可比性。
獨立的
1.獨立的集合是一組引起無進出子圖的頂點。它也可以稱為穩定套件或Coclique。獨立數α （ g ）是最大獨立集的大小。
2.在圖形的圖形矩陣中，如果相應的子圖是樹或森林，則邊緣的子集是獨立的。在雙子矩陣中，如果相應的子圖是偽遠方的，邊緣的子集是獨立的。
漠不關心
冷漠圖是適當的間隔圖或單位間隔圖的另一個名稱；看到適當的。
誘導
圖形的誘導子圖或完整子圖是由頂點子集以及子集中兩個端點的所有邊緣形成的子圖。特殊情況包括誘導的路徑和誘導的循環，誘導的亞圖是路徑或週期。
感應
退化的同義詞。
無窮
無限圖是不是有限的。見有限。
內部的
路徑或樹的頂點是內部的，如果它不是葉子；也就是說，如果其學位大於一個。如果沒有第一個也沒有第一個和最後一個的頂點，則兩條路徑在內部是不相交的（有人稱其為獨立）。
路口
1.兩個圖的交點是它們最大的常見子圖，該圖由屬於兩個圖的頂點和邊緣形成。
2.相交圖是一個圖形，其頂點對應於集合或幾何對象，當相應的兩個集合或對象具有非空交點時，正好在兩個頂點之間具有邊緣。幾類圖形可以定義為某些類型的對象的交點圖，例如弦圖（樹的子樹的相交圖），圓形圖（圓圈的和弦的相交圖），間隔圖（間隔圖的相交圖）線圖（圖形邊緣的相交圖）和集團圖（圖形最大集中的相交圖）的線圖）。每個圖是針對某些集合家族的相交圖，該家族稱為圖的交點表示。圖G的相交數是G的任何相交表示中的最小元素總數。
間隔
1.間隔圖是線間隔的相交圖。
2.圖中的間隔[ u ， v ]是從u到v的所有最短路徑的結合。
3.間隔厚度是路徑寬的同義詞。
不變
屬性的同義詞。
倒箭
與另一個箭頭相比的箭頭相反。箭頭（ y ， x ）是箭頭（ x ， y ）的倒箭頭。
孤立
圖形的孤立頂點是一個頂點，其度為零，即沒有入射邊緣的頂點。
同構
如果它們之間存在同構，則兩個圖是同構。見同構。
同構
圖同構是一個一對一的發病率，它保存了一個圖的頂點和邊緣與另一個圖的頂點和邊緣的對應關係。以這種方式相關的兩個圖是同構。
等級
參見擴展。
地峽
橋樑的同義詞，從而使刪除斷開圖形連接的邊緣。

K

K
有關完整圖的符號，請完成兩分圖和完整的多部分圖，請參見完成。
κ
κ （ g ） （使用希臘字母kappa）是g中最大集團的順序；見集團。
核心
有向圖的內核是一組穩定且吸收的頂點。
結
有向圖的不可避免的部分。參見結（數學）和結理論。

L

L
l （ g ）是g的線圖；見行。
標籤
1.與圖形的頂點或邊緣相關的信息。標記的圖是一個圖形，其頂點或邊緣具有標籤。術語標記或邊緣標記的術語可用於指定圖形的哪些對象具有標籤。圖標記是指將標籤分配給受某些約束的圖形的幾個不同問題。另請參見圖形，其中標籤被解釋為顏色。
2.在圖表的上下文中，如果圖形都可以彼此區分，則據說圖形的頂點被標記為標籤。例如，這可以通過固定從1到圖的順序之間的一對一對應關係來實現這一目標。當標記頂點時，將彼此同構的圖（但帶有不同頂點訂購）算作單獨的對象。相比之下，當頂點未標記時，彼此同構的圖不會單獨計數。
葉子
1.葉頂點或吊墜頂點（尤其是在樹中）是一個頂點，其度為1 。葉邊緣或吊墜邊緣是將葉頂點連接到其單個鄰居的邊緣。
2.樹的葉子功率是一個圖形，其頂點是樹的葉子，其邊緣連接葉子的葉子的距離最多是給定的閾值。
長度
在未加權的圖中，週期，路徑或步行的長度是其使用的邊數。在加權圖中，它可能是其使用的邊緣的權重之和。長度用於定義最短路徑，周長（最短循環長度）和圖中兩個頂點之間的最長路徑。
等級
1.這是節點加1的深度，儘管有些人將其定義為深度的同義詞。根部樹中的節點級別是從根到節點的路徑中的節點數。例如，根具有1級，其相鄰節點中的任何一個都有2級。
2.所有節點的一組具有相同級別或深度。
線
無向邊緣的同義詞。圖G的線圖L （ g ）是一個圖形的圖形，每個邊緣的每個邊緣都有頂點，並且每對邊緣在G中共享端點的邊緣。
連鎖
退化的同義詞。
列表
1.鄰接列表是用於圖形算法的圖形的計算機表示。
2.列表著色是圖形著色的一種變體，其中每個頂點都有可用顏色的列表。
當地的
圖的本地屬性是僅由圖中頂點的鄰域確定的屬性。例如，如果其所有社區都是有限的，則圖是本地有限的。
環形
循環或自循環是邊緣，其端點是相同的頂點。它形成長度1的周期。這些不允許在簡單的圖中。

M

放大
頂點擴展的同義詞。
匹配
匹配是一組邊緣，其中沒有兩個共享任何頂點。如果頂點是匹配中邊緣的端點之一，則將其匹配或飽和。完美的匹配或完整匹配是與每個頂點匹配的匹配。它也可以稱為1因子，只有在訂單為偶數時才能存在。在具有奇數順序的圖中，幾乎完美的匹配是使除一個頂點以外的所有匹配。最大匹配是一種使用盡可能多的邊緣的匹配。圖G的匹配數α '（ g ）是最大匹配中的邊數。最大匹配是與不添加其他邊緣的匹配。
最大
1.如果具有該屬性，則給定圖G的子圖對特定屬性是最大的，但沒有其他超圖也是G的子圖也具有相同的屬性。也就是說，它是該屬性的子圖的最大元素。例如，最大集團是一個完整的子圖，無法將其擴展到較大的完整子圖。 “最大”一詞應與“最大值”區分開：最大值始終是最大的，但不一定是副主義。
2.如果無法向其添加更多邊緣（保持頂點設置不變），則具有給定屬性的簡單圖是該屬性的最大值，同時保留了圖形和屬性的簡單性。因此，例如，最大平面圖是一個平面圖，因此將更多的邊緣添加到其上將創建一個非平面圖。
最大限度
如果特定屬性是該屬性的所有子圖中最大的子圖（按順序或大小），則給定圖G的子圖是最大的。例如，最大集團是給定圖中的任何最大集團。
中位數
1.一個三重頂點的中值，一個頂點屬於所有對頂點之間的最短路徑，尤其是中間圖和模塊化圖。
2.中間圖是一個圖形，其中每三個頂點具有獨特的中位數。
梅尼爾
1.亨利·梅尼爾（Henri Meyniel），法國圖理論家。
2. Meyniel圖是一個圖形，其中每個長度五個或更多的奇數循環至少具有兩個和弦。
最小
如果特定屬性具有該屬性，但沒有適當的子圖也具有相同的屬性，則給定圖的子圖最少。也就是說，它是該屬性子圖的最小元素。
最小切割
切割的切割，其切割的總重量最小，可能僅限於將指定的頂點分開的切割；它們的特徵是最大流量定理。
次要的
如果可以通過從g中刪除邊緣或頂點並在g中收縮邊緣，則圖H是另一個圖G的少數。如果可以將其作為未成年人形成淺的未成年人，以使G的子圖的形成H的頂點均具有較小的直徑。 H是G的拓撲小調，如果G具有h的細分子圖。如果沒有h作為輔助，則圖形不含h 。如果圖形在未成年人的下關閉，則圖表卻略有關閉；羅伯遜 - 西摩定理將次要的家庭描述為有限的禁忌少年。
混合
混合圖是一個可能包括有向和無向邊緣的圖。
模塊化的
1.模塊化圖，其中每個三重頂點具有至少一個中間頂點，該頂點屬於三個對的所有對之間的最短路徑。
2.模塊化分解，圖形分解為子圖，所有頂點以相同的方式連接到圖形的其餘部分。
3.圖集群的模塊化，跨簇邊緣數量與其預期值的差異。
單調
圖形的單調屬性是在子圖下關閉的屬性：如果G具有遺傳性屬性，則G的每個子圖都必須。比較遺傳（在誘導的子圖下封閉）或次要關閉（在未成年人的下關閉）。
摩爾圖
摩爾圖是一個常規圖形，準確地滿足了摩爾的界限。摩爾結合是圖形的程度，直徑和順序的不等式，由愛德華·摩爾（Edward F. Moore）證明。每個摩爾圖都是一個籠子。
多媒體
多編碼是一個允許多個鄰接（以及通常是自寬）的圖；不需要簡單的圖。
多個鄰接
多個鄰接或多個邊緣是一組具有相同端點的一個以上的邊緣（在有向圖的情況下，在相同的方向上）。具有多個邊緣的圖通常稱為多編碼。
多重性
邊緣的多重性是多個鄰接中的邊數。圖的多樣性是其任何邊緣的最大多重性。

N

N
1.有關開放和關閉社區的符號，請參見社區。
2.經常使用較低的n （尤其是在計算機科學中）來表示給定圖中的頂點數量。
鄰居
鄰居
與給定頂點相鄰的頂點。
鄰里
鄰里
頂點V的開放鄰域（或鄰域）是與V相鄰的所有頂點引起的子圖。封閉的社區以相同的方式定義，但也包括V本身。 G中V的開放鄰居可以表示N G （ V ）或N （ V ） ，並且可以表示封閉的鄰域N G [ V ]或N [ V ] 。如果未指定社區的開放性或封閉性，則假定它是開放的。
網絡
屬性（例如名稱）與節點和/或邊緣關聯的圖。
節點
頂點的同義詞。
非邊緣
非邊緣或反向是一對不相鄰的頂點。補體圖的邊緣。
空圖
請參閱空圖。

O

奇怪的
1.奇數循環是一個奇數的循環。非雙分歧圖的奇數是其最短奇數循環的長度。一個奇數孔是一個奇數週期的特殊情況：一個被誘導並具有四個或多個頂點。
2.奇數頂點是一個頂點，其度為奇數。通過握手引理每個有限的無向圖具有均勻數量的奇數頂點。
3.奇怪的耳朵是一個簡單的路徑或簡單的循環，具有奇數的邊緣，用於奇特的臨界圖的奇怪耳朵分解；看到耳朵。
4.奇數和弦是連接兩個頂點的邊緣，它們在均勻的周期中相距奇數。奇數和弦用於定義強烈的和弦圖。
5.一個奇數圖是一個旋轉圖的特殊情況，每個頂點（ n -1） - 元素子集的一個頂點（2 n -1） - 元素集，以及一個在相應的集合為兩個子集時連接兩個子集的邊緣脫節。
打開
1.參見鄰里。
2.參見步行。
命令
1.圖G的順序是其頂點的數量， | V （ g ）| 。變量n通常用於此數量。另請參見大小，邊緣數。
2.圖形的邏輯類型；請參閱第一階和二階。
3.圖的順序或順序是其頂點的排列為一個序列，尤其是在拓撲排序的背景下（有向無環圖的順序，每個邊緣從早期的頂點轉到以後的頂點）和退化順序（每個頂點在誘導的子圖和所有後來的頂點中具有最小程度的順序）。
4.有關避風港或布拉布爾的命令，請參見Haven and Bramble 。
方向
定向
1.無向圖的方向是向其邊緣的方向分配，將其變成有向圖。一個方向的圖是已分配方向的圖形。因此，例如，多葉是一個定向的樹。它與有向樹（樹木）的不同之處在於，其邊緣方向不需要一致性。其他特殊類型的方向包括錦標賽，完整圖的方向；強大的方向，緊密聯繫的方向；無環，無環的方向； Eulerian取向，是Eulerian的方向；和及時的方向，定向封閉的方向。
2.定向圖，一些作者用作有向圖的同義詞。
超級
見學位。
外
見臉。
外平
外平面圖是一個可以嵌入平面（無交叉）的圖形，因此所有頂點都在圖的外表面上。

P

父母
在根的樹上，頂點V的父沿傳入邊緣的鄰居，它是針對根部的。
小路
路徑可以是步行或步行，而無需重複的頂點，因此可以根據源頭（也稱為簡單的路徑）（也稱為簡單路徑）。重要的特殊情況包括誘發路徑和最短路徑。
路徑分解
圖G的路徑分解是樹的分解，其底層樹是一條路徑。它的寬度的定義與樹分解相同的方式與最大袋子的大小相同。 G的任何路徑分解的最小寬度是G的路徑。
路徑寬
圖G的路徑是G的路徑分解的最小寬度。它也可以根據g的間隔完成數量來定義。它始終介於帶寬和g的樹寬之間。它也稱為間隔厚度，頂點分離號或節點搜索編號。
吊墜
見葉。
完美的
1.完美的圖是一個圖形，在每個誘導子圖中，色數等於集團數字。完美的圖定理和強大的完美圖定理是關於完美圖的兩個定理，前者證明了它們的補充也很完美，後者證明它們正是沒有奇數或反孔的圖形。
2.一個完美的訂購圖是一個圖形，其頂點可以以這種方式排序，以使貪婪的著色算法使用此訂購最佳的每個誘導子圖最佳著色。完美的訂購圖是完美圖的子類。
3.完美的匹配是使每個頂點飽和的匹配。請參閱匹配。
4.完美的1件分子化是圖表的邊緣分配為完美的匹配，因此每兩個匹配都形成了漢密爾頓週期。
外圍
1.外圍週期或非分離週期是一個循環，最多是一個橋。
2.外圍頂點是一個頂點，其偏心率最大。在樹上，這一定是葉子。
彼得森
1.朱利葉斯·彼得森（Julius Petersen ）（1839-1910），丹麥理論家。
2. Petersen圖，這是一個經常用作反例的10 vertex 15邊緣圖。
3.彼得森定理，每個無用的立方圖都具有完美的匹配。
平面
平面圖是一個嵌入歐幾里得平面上的圖。平面圖是一個平面圖，已經固定了特定嵌入的平面圖。 k平面圖是可以在平面中繪製的，每個邊緣最多可在k交叉處。
Polytree
聚樹是一棵定向的樹；同等地，基礎無向圖的有向無環圖是一棵樹。
力量
1.圖G的圖形電源G K是同一頂點集上的另一個圖。當G k處最多在g中的距離時，兩個頂點在g k中相鄰。葉子功率是一個密切相關的概念，它通過取下樹葉引起的子圖來源自樹的力量。
2.功率圖分析是一種通過在網絡中識別集團，雙晶和恆星來分析複雜網絡的方法。
3.無標度網絡的程度分佈中的功率定律是一種現象，其中給定程度的頂點的數量與程度的冪成正比。
前任
在定向路徑上給定頂點之前的頂點。
恰當的
1.適當的子圖是一個子圖，該子圖與整個圖形相對於整個圖表至少一個頂點或邊緣。對於有限的圖，正確的子圖絕不是整個圖的同構，而是對於無限圖。
2.正確的著色是將顏色分配給圖形的頂點（著色），該顏色將不同的顏色分配給每個邊緣的端點；請參閱顏色。
3.適當的間隔圖或正確的圓形弧形圖是分別（分別）或圓形弧的集合的相交圖，因此不包含其他間隔或弧。正確的間隔圖也稱為單位間隔圖（因為它們可以始終用單位間隔表示）或無差異圖。
財產
圖形屬性是某些圖形可以正確的，而其他圖形可以是錯誤的，這僅取決於圖形結構，而不取決於偶然的信息，例如標籤。圖形屬性可以等效地用圖形（具有給定屬性的圖）來描述。更一般而言，圖形屬性也可能是圖形的函數，該函數再次獨立於偶然信息，例如圖的大小，順序或程度序列；對屬性的更一般的定義也稱為圖形的不變。
偽索
偽索是一個無方向的圖，每個連接的組件最多都有一個週期，或一個有向圖，每個頂點最多具有一個外向的邊緣。
偽掃描
偽掃描是允許自動浮動的圖形或多編碼。

Q

準線圖
準行圖或本地共同兩部分圖是一個圖，其中每個頂點的開放鄰域都可以分為兩個集團。這些圖始終不含爪子，並且包括特殊情況。它們用於無爪圖的結構理論。
準隨機圖序列
準隨機圖序列是一系列圖，該序列與根據ERDőS-Rényi隨機圖模型產生的一系列隨機圖共享多個屬性。
顫動
如類別理論中所用的，顫抖是一種定向的多編碼。顫抖的邊緣稱為箭頭。

R

半徑
圖的半徑是任何頂點的最小偏心率。
拉馬努揚
Ramanujan圖是一個圖形，其光譜膨脹盡可能大。也就是說，它是D-規範的圖，因此其鄰接矩陣的第二大特徵值最多是 。
射線
無限圖中的射線是一個無限的簡單路徑，恰好一個端點。圖的末端是射線的等效類。
可達性
從一個頂點到達圖中另一個頂點的能力。
可到達
具有肯定的可及性。如果有從x到y的路徑，則可以從頂點x到達頂點y。
可識別
在重建猜想的上下文中，如果可以從圖形的甲板確定其真相，則圖形屬性是可識別的。已知許多圖形屬性是可識別的。如果重建猜想是正確的，則所有圖形屬性都是可識別的。
重建
重建猜想指出，每個無方向的圖G均由其甲板唯一確定，這是通過以所有可能的方式從G中刪除一個頂點形成的多組圖。在這種情況下，重建是從其甲板形成圖的形成。
長方形
一個簡單的循環，恰好由四個邊緣和四個頂點組成。
常規的
當它的所有頂點具有d時，圖為d 。常規圖是某些d的d -groumar的圖。
常規比賽
常規錦標賽是一場錦標賽，在該錦標賽中，所有頂點等於級別。
反向
參見轉置。
根
1.圖中指定的頂點，尤其是在有向樹和紮根的圖中。
2.圖形g的逆操作：圖G的k鍵是同一頂點集上的另一個圖形，使得兩個頂點在G中相鄰，並且僅當它們在根中最多具有距離時。

S

飽和
請參閱匹配。
搜索號碼
節點搜索號是路徑寬的同義詞。
二階
圖形的二階邏輯是一種邏輯形式，其中變量可能代表頂點，邊緣，頂點集和（有時）邊緣集。該邏輯包括測試頂點和邊緣是否入射的謂詞，以及頂點或邊緣是否屬於集合。要區分一階邏輯，其中變量只能表示頂點。
自循環
循環的同義詞。
分開頂點
請參閱發音點。
分離號
頂點分離號是路徑寬的同義詞。
兄弟
在根系中，頂點V的兄弟姐妹是一個頂點，其母體頂點與V。
簡單的
1.簡單的圖是沒有循環且沒有多個鄰接的圖形。也就是說，每個邊緣連接兩個不同的端點，沒有兩個邊緣具有相同的端點。簡單的邊緣是不屬於多重鄰接的邊緣。在許多情況下，除非另有說明，否則假定圖形被認為很簡單。
2.簡單的路徑或簡單的循環是沒有重複頂點，因此沒有重複邊緣的路徑或循環。
下沉
在有向圖中的水槽是一個沒有傳出邊緣的頂點（超級等於0）。
尺寸
圖G的大小是其邊緣的數量， | e （ g ）| 。變量M通常用於此數量。另請參見順序，頂點的數量。
小世界網絡
小世界網絡是一個圖形，其中大多數節點不是彼此的鄰居，但是可以通過少數啤酒花或步驟從其他每個節點從其他每個節點接觸大多數節點。具體而言，一個小世界網絡被定義為一個圖，其中兩個隨機選擇節點之間的典型距離l （所需步驟數）在網絡中NODES N的對數成正比增長
Snark
Snark是一個簡單，連接的，無橋的立方圖，具有等於4的色度指數。
來源
在有向圖中的源是一個沒有傳入邊緣的頂點（內度等於0）。
空間
在代數圖理論中，二進制場上的幾個向量空間可能與圖形相關聯。每個都有其向量的一組邊緣或頂點，而集合作為其矢量總和操作的對稱差異。邊緣空間是所有邊緣的空間，頂點空間是所有頂點的空間。切割空間是邊緣空間的子空間，其圖形的切割集作為其元素。循環空間將歐拉（Eulerian）跨越子圖作為其元素。
扳手
扳手是（通常是稀疏）的圖形，其最短路徑距離近似於密集圖或其他度量空間中的路徑距離。變化包括幾何跨度，其頂點是幾何空間中的點的圖；樹的跨度，跨越圖的樹的樹，其距離近似圖形距離，圖形跨度，稀疏圖的稀疏子圖，其距離近似於原始圖的距離。貪婪的扳手是由貪婪算法構建的圖形扳手，通常將所有邊緣從最短到最長，並保留保留距離近似所需的邊緣。
跨度
當子圖包括給定圖的所有頂點時，它正在跨越。重要情況包括跨越樹木，跨越樹的子圖以及完美的匹配，跨越匹配的子圖。跨越子圖也可以稱為一個因素，尤其是（但不僅是常規）。
疏
稀疏圖是相對於其頂點數量很少的邊緣。在某些定義中，對於給定圖的所有子圖也應為相同的屬性。
光譜
光譜
圖的頻譜是其鄰接矩陣的特徵值的集合。光譜圖理論是圖形論的分支，它使用光譜來分析圖。另請參見光譜膨脹。
分裂
1.拆分圖是一個圖形，其頂點可以分為一個集團和獨立集。相關的圖形類別（雙拆分圖）用於強大的完美圖定理的證明。
2.任意圖的拆分是將其頂點的一個分區分為兩個非空的子集，因此跨越此切割的邊緣形成了一個完整的兩部分子圖。圖的拆分可以由稱為其拆分分解的樹結構表示。當沒有其他任何拆分交叉時，拆分稱為強拆分。當它的兩個側面都有多個頂點時，拆分稱為非平地。當沒有非平凡的分裂時，圖稱為prime。
正方形
1.圖G的平方是圖形g 2 ；在另一個方向上， g是g 2的平方根。二分圖的半平方是其正方形的子圖，該平方是由兩部分的一側引起的。
2.方形圖是可以繪製的平面圖，因此所有有界的面都是4個週期，所有度≤3的頂點屬於外部面。
3.方格圖是一個晶格圖，該晶格圖是由平面中的點定義的，其整數坐標由單位長度連接。
穩定的
穩定集是獨立集的同義詞。
星星
一顆星是一棵具有內部頂點的樹。同等地，對於某些n≥2 ，它是一個完整的二分圖k 1， n 。帶有三葉的星星的特殊情況稱為爪子。
力量
圖的強度是在所有可能的刪除上從圖形上刪除的邊緣數量與創建的組件的最小比率。它類似於基於頂點的去除。
強的
1.有關有向圖的牢固連通性和緊密連接的組件，請參見連接和組件。強大的方向是緊密聯繫的方向。參見方向。
2.有關強大的完美圖定理，請參閱完美。
3.強烈的規則圖是一個常規的圖形，其中每個兩個相鄰的頂點具有相同數量的共享鄰居，而每兩個非貼身頂點具有相同數量的共享鄰居。
4.強烈的和弦圖是一個和弦圖，其中每個長度六個或更多的偶數週期都具有奇數和弦。
5.強烈完美的圖是一個圖形，其中每個感應子圖都有一個獨立的設置，以滿足所有最大集團。 Meyniel圖也稱為“非常完美的圖”，因為在其中，每個頂點都屬於如此獨立的集合。
亞福特
森林的子圖。
子圖
圖G的子圖是由G的頂點和邊緣的子集形成的另一個圖。頂點子集必須包括邊緣子集的所有端點，但也可能包括其他頂點。跨越子圖是包含圖形的所有頂點的一個。誘導的子圖是包括所有端點屬於頂點子集的邊緣。
子樹
子樹是樹的連接子圖。有時，對於根樹，子樹被定義為一種特殊類型的連接子圖，由所有頂點和邊緣形成，可從所選頂點到達。
接班人
在定向路徑中以給定頂點沿著給定頂點出現的頂點。
超探調器
超探調器是一個圖形，具有兩個指定和等式的頂點i和o子集，因此，對於每兩個相等大小的子集i和t o ，存在一個連接s中每個頂點到一個頂點到一個頂點的不相交路徑的家族， t 。一些來源還要求超級探調器是有向無環圖，而i作為其來源，並且O作為水槽。
超圖
通過將頂點，邊緣或兩者添加到給定圖形形成的圖形。如果H是G的子圖，則G是H的超圖。

T

塞塔
1. theta圖是三個具有相同兩個不同末端頂點的內部不相交（簡單）路徑的聯合。
2.通過構造每個點周圍的錐體系統並將每個圓錐形的一個邊添加到圓錐體的中央射線的點，歐幾里得平面中的theta圖是通過構造一個圓錐體的系統來構建的。
3.圖形的lovászNumber或lovászTheta函數是與集團數和色數相關的圖形不變式，可以通過半決賽時間在多項式時間內計算。
湯姆森圖
Thomsen圖是完整的兩部分圖的名稱 。
拓撲
1.拓撲圖是按平面中的點和曲線的圖表和邊緣的表示（不一定避免穿越）。
2.拓撲圖理論是圖嵌入的研究。
3.拓撲排序是將定向的無環形圖安排到拓撲順序的算法問題，即頂點序列，使每個邊緣從較早的頂點到序列中的較晚頂點。
完全斷開連接
Edggeless的同義詞。
旅遊
一條封閉的步道， 步行，以同一頂點開始和結束，沒有反复的邊緣。 Euler Tours是使用所有圖形邊緣的旅行；見歐拉。
比賽
比賽是完整圖的方向。也就是說，這是一個有向圖，使每個兩個頂點完全通過一個有向邊（僅在兩個頂點之間的兩個方向之一）連接起來。
可追溯
可追溯圖是包含哈密頓路徑的圖。
踪跡
步行而沒有反复的邊緣。
傳遞
與瞬態屬性有關。給定有向圖的傳遞閉合是同一頂點集上的圖形，每當原始圖具有連接相同兩個頂點的路徑時，它具有從一個頂點到另一個頂點的邊緣。圖形的及時還原是具有相同瞬態閉合的最小圖。定向的無環圖具有獨特的橫向降低。及時取向是其自身及其及其及其及其及其及其及其及其及其及其及其及物的閉合的方向。它僅用於可比性圖。
轉置
給定有向圖的轉置圖是同一頂點上的圖形，每個邊緣都在方向上逆轉。它也可以稱為圖形的相反或反向。
樹
1.樹是一個無向圖，既連接和無環，又是一個有向圖的圖形，其中存在從一個頂點（樹的根）到所有其餘頂點的唯一步行。
2. k -樹是通過在共享k個cliques上粘合（ k + 1）將膠合（k + 1）形成的圖。根據此定義，從普通意義上講的樹是1樹。
樹分解
圖G的樹分解是一棵樹，其節點的標記為g的頂點。這些套件稱為袋子。對於每個頂點V ，包含V的袋子必須誘發樹的子樹，對於每個邊緣，紫外線必須存在一個包含U和V的袋子。樹分解的寬度比其任何袋中的最大頂點少一個。 G的樹寬是G的任何樹分解的最小寬度。
樹寬
圖G的樹寬是G的樹分解的最小寬度。也可以根據G的串聯完成數量， G的避風港的順序或G的Bramble訂單來定義。
三角形
圖中三個循環。無三角形圖是一個沒有任何三角子圖的無向圖。
瑣碎的
瑣碎的圖是具有0或1個頂點的圖形。具有0個頂點的圖也稱為NULL圖。
圖恩
1.PálTurán
2.Turán圖是一個平衡的完整多部分圖。
3.Turán的定理指出，Turán圖在給定秩序的所有無集中圖中具有最大邊緣數量。
4.Turán的磚砌工廠問題要求在完整的兩部分圖的圖紙中提出最少的穿越數量。
雙胞胎
如果有相同的封閉社區，則兩個頂點u，v是真雙胞胎： n g [ u ] = n g [ v ] （這意味著u和v是鄰居），如果它們具有相同的開放式鄰居，則它們是假的雙胞胎： n g （ u ）= n g （ v ）） （這意味著u和v不是鄰居）。

U

一元頂點
在根的樹上，一元頂點是一個恰好具有一個子頂點的頂點。
無方向
一個無方向的圖是一個圖，其中每個邊緣的兩個端點沒有彼此區分。另請參見定向和混合。在混合圖中，無向的邊緣再次是端點沒有區分的邊緣。
制服
當其所有邊緣具有k端點時，高顆粒是均勻的，而對於某些k的k-均勻時，則均勻。例如，普通圖與2-均勻的超圖相同。
普遍的
1.通用圖是一個圖形，它包含子圖中的所有圖表中的所有圖形，或給定圖形家族中給定大小或順序的所有圖。
2.通用頂點（也稱為頂點或主導頂點）是一個頂點，與圖中的其他每個頂點相鄰。例如，車輪圖和連接的閾值圖始終具有通用頂點。
3.在圖的邏輯中，在公式中普遍量化的頂點可以稱為該公式的通用頂點。
未加權圖
尚未分配重量的頂點和邊緣S的圖； 加權圖的相反。
實用圖
實用圖是完整的兩部分圖的名稱 。

V

V
請參閱頂點集。
價
學位的同義詞。
頂點
頂點（複數頂點）（帶有邊緣）是構造圖形的兩個基本單元之一。圖的頂點通常被認為是原子對象，沒有內部結構。
頂點切割
分開集
一組將其去除的頂點斷開圖形。單vertex剪裁稱為鉸接點或切割頂點。
頂點集
給定圖G的頂點集，有時用V （ g ）表示。
頂點
請參閱頂點。
尖銳
1. Vadim G.
2. Viping的定理認為色度指數最多比最大程度高。
3. Viping在笛卡爾產品的統治數量上的猜想。
體積
一組頂點的程度之和。

W

W
字母W用於符號中，用於車輪圖和風車圖。該符號不是標準化的。
華格納
1.克勞斯·瓦格納（Klaus Wagner）
2. Wagner圖，一個八個VertexMöbius梯子。
3.瓦格納（Wagner）的定理表徵了其禁止的未成年人的平面圖。
4.瓦格納（Wagner）的定理表徵了k 5-少數圖。
走
步行是一個有限或無限的邊序，它連接了一系列頂點。散步有時也稱為鏈條。如果第一個也是最後一個頂點與眾不同，則散步是打開的，如果重複進行，則散步。
弱連接
如果用無方向的邊替換其所有有向邊緣會產生連接的（無向）圖，則將有向圖稱為弱連接。
重量
數值，將標籤分配給圖形的頂點或邊緣。子圖的重量是該子圖內頂點或邊緣的重量之和。
加權圖
其頂點或邊緣s的圖形分配了重量s。頂點加權圖在其頂點上具有權重，而邊緣加權圖的邊緣上有權重。
彩色
顏色良好的圖是所有貪婪的顏色都使用相同數量的顏色的圖。
覆蓋良好
覆蓋良好的圖是所有最大獨立集相同大小的圖。
車輪
車輪圖是通過將通用頂點添加到簡單循環中形成的圖。
寬度
1. 退化的同義詞。
2.有關稱為寬度的其他圖形不變性，請參見帶寬， 分支環， 集團寬度， 路徑寬度和樹寬。
3.樹分解或路徑分解的寬度比其一個袋子之一的最大尺寸小，可用於定義樹寬和路徑寬度。
4.有向無環圖的寬度是抗抗小鍵的最大基數。
風車
風車圖是一個集團集合的結合，彼此相同，一個共享頂點屬於所有集團以及所有其他頂點和邊緣。

也可以看看