• 禁止圖的表征

    編輯
    本詞條由“匿名用戶” 建檔。

    禁止圖的表征

    編輯

    在圖論這個數學分支中,許多重要的圖族可以由不屬于該圖族的單個圖的有限集合來描述,并進一步排除該圖族中包含任何這些禁止圖的(誘導)子圖或小圖的所有圖。這種現象的一個典型例子是庫拉托夫斯基定理,該定理指出,當且僅當一個圖不包含兩個禁圖,即完整圖K5和完整的二方圖K3,3中的任何一個時,該圖是平面的(可以在平面上沒有交叉)。對于庫拉托夫斯基定理,包含的概念是圖的同構性,其中一個圖的細分作為另一個圖的子圖出現。因此,每個圖要么有一個平面圖(在這種情況下,它屬于平面圖族),要么它至少有一個這兩個圖的細分作為子圖。

    禁止圖的表征的定義

    編輯

    更廣泛地說,禁止圖的特征是一種指定圖族或超圖結構的方法,通過指定禁止在該圖族的任何圖中存在的子結構。不同的家族在禁止的性質上有所不同。一般來說,一個結構G是一個家族的成員F的成員。當且僅當一個被禁止的子結構不包含在G中時,該被禁止的子結構可能是其中之一。子圖,從大圖的頂點和邊的子集中得到的較小的圖;誘導子圖,通過選擇頂點的一個子集并使用該子集中具有兩個端點的所有邊得到的較小的圖;同構子圖(也稱為拓撲小圖),通過將二級頂點的路徑折疊成單邊而從子圖中得到的較小的圖;或者圖小圖,通過任意的邊收縮從子圖中得到的較小的圖。禁止屬于某一圖族的結構集也可以稱為該圖族的障礙集。禁止圖的特征可用于測試一個圖是否屬于某一族的算法中。在許多情況下,有可能在多項式時間內測試一個給定的圖是否包含障礙集的任何成員,因此它是否屬于該障礙集所定義的族。為了使一個族具有禁止圖的特征,并具有特定類型的子結構,該族必須在子結構下是封閉的。

    庫拉托夫斯基定理

    也就是說,該族中一個圖的每個子結構(特定類型)必須是該族中的另一個圖。等價地,如果一個圖不是家族的一部分,所有包含它作為子結構的更大的圖也必須從家族中排除。當這一點為真時,總是存在一個阻礙集。然而,對于子結構的某些概念,這個障礙集可能是無限的。

    內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/164473/

    (3)
    詞條目錄
    1. 禁止圖的表征
    2. 禁止圖的表征的定義

    輕觸這里

    關閉目錄

    目錄
    91麻精品国产91久久久久