• 排放法(離散數學)

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

    排放法(離散數學)

    編輯

    排放法是一種用于證明結構圖理論中的公設的技術。排放法因其在四色定理證明中的核心作用而最為著名。排放法被用來證明某一類中的每一個圖都包含指定列表中的一些子圖。然后,所需子圖的存在常常被用來證明一個著色結果。最常見的是,放電法適用于平面圖。最初,為圖的每個面和每個頂點分配一個電荷。分配的電荷使其總和為一個小的正數。在放電階段,根據一組放電規則的要求,每個面或頂點的電荷可能被重新分配到附近的面和頂點。然而,每個放電規則都保持著電荷的總和。這些規則被設計成在放電階段后,每個帶有正電荷的面或頂點都位于所需的子圖中。由于電荷的總和是正的,一些面或頂點必須有正電荷。許多放電參數使用幾個標準初始電荷函數中的一個(這些函數列在下面)。放電法的成功應用需要創造性地設計放電規則。

    一個例子

    編輯

    如果一條邊的端點都是5度,或者都是5度和6度,我們稱其為輕度。將圖形嵌入平面。為了證明該定理,只需考慮平面三角圖即可。我們任意向圖形添加邊,直到它成為一個三角形。由于原圖的最小度數為5,新邊的每個端點至少有6度。因此,沒有一條新邊是輕的。因此,如果三角形包含一條輕邊,那么該邊一定在原圖中。表示一個頂點的度數和一個面的長度。

    使用歐拉公式,很容易看出所有電荷之和為12。我們只使用一個放電規則。每個5度的頂點給每個鄰居1/5的電荷。我們考慮哪些頂點可能有正的最終電荷。xxx有正的初始電荷的頂點是5度的頂點。每個5度的頂點給每個鄰居1/5的電荷。排放法(離散數學)

    如果一個頂點v的度數為7,且最終電荷為正。有7度,并且有正的最終電荷,那么v從至少6個相鄰的5度頂點從至少6個相鄰的5度頂點得到電荷。由于該圖是一個三角結構,與v相鄰的頂點v相鄰的頂點必須形成一個循環。必須形成一個循環,由于它只有7度,5度的鄰居不可能都被更高程度的頂點分開;v的5度鄰居中至少有兩個v的5度鄰居中至少有兩個的5度鄰居中至少有兩個在這個循環上是相鄰的。這就產生了光邊。

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

    贊 (3)
    詞條目錄
    1. 排放法(離散數學)
    2. 一個例子

    輕觸這里

    關閉目錄

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