• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 18,  comments - 5,  trackbacks - 0
            一、定義
                  割點(diǎn):如果在圖G中刪去一個結(jié)點(diǎn)u后,圖G的連通分枝數(shù)增加,即W(G-u)>W(G),則稱結(jié)點(diǎn)u為G的割點(diǎn),又稱關(guān)節(jié)點(diǎn)。
                  橋:如果在圖G中刪去一條邊e后,圖G的連通分支數(shù)增加,即W(G-e)>W(G),則稱邊u為G的橋,又稱割邊或關(guān)節(jié)邊。
                  雙連通分支:G中不含割點(diǎn)的極大連通子圖稱為G的雙連通分支,又稱為G的塊。
            二、DFS
                  描述:在對于任選一個圖中結(jié)點(diǎn)為根的DFS搜索樹中建立一個LAB數(shù)組與LOW數(shù)組,LAB數(shù)組存儲個結(jié)點(diǎn)的編號,LOW數(shù)組存儲各點(diǎn)及其子樹的各結(jié)點(diǎn)能到達(dá)的最小編號結(jié)點(diǎn)的編號。
            1 //lab為一個全局變量,初始為1, LAB各項(xiàng)初始為0
            2 DFS(u)
            3     LAB[u] = LOW[u] = lab++
            4     for each (u, v) in E(G)
            5         if LAB[v] is 0
            6             DFS(v)
            7             LOW[u] = min{LOW[u], LOW[v]}
            8         else if  v isnot parent of u
            9             LOW[u] = min{LOW[u], LAB[v]}

                  第5行中,如果(u, v)是樹邊,則對v做深度優(yōu)先搜索,并且LOW[u] = min{LOW[u], LOW[v]},如果(u, v)是反向邊,則LOW[u] = min{LOW[u], LAB[v]}。

            三、割點(diǎn)
                  描述:當(dāng)一個結(jié)點(diǎn)u是割點(diǎn)時必滿足以下兩個條件之一:
                        1)u為根且至少有兩棵子樹;
                        2)u不為根且存在一個u在深搜樹中的子女v使得LOW[v] ≥ LAB[u]。
                  示例:POJ 1523 解題報(bào)告
            四、橋
                   描述:一條邊e=(u, v)是橋,當(dāng)且僅當(dāng)e為樹枝邊且LOW[v] > LAB[u]。
                  示例:POJ 3352 解題報(bào)告

                  
            posted on 2009-07-05 16:18 Icyflame 閱讀(2646) 評論(1)  編輯 收藏 引用 所屬分類: 圖論
            色欲综合久久躁天天躁| 久久人爽人人爽人人片AV| 久久综合久久美利坚合众国| 国产成人精品综合久久久久| 狠狠色丁香久久婷婷综合五月| 久久se精品一区精品二区国产| 亚洲中文字幕无码久久2020 | 久久久久久久波多野结衣高潮| 嫩草伊人久久精品少妇AV| 国产精品欧美亚洲韩国日本久久 | 好久久免费视频高清| 久久婷婷人人澡人人爽人人爱| 久久精品国产亚洲欧美| 久久精品国产亚洲AV蜜臀色欲| 精品免费久久久久国产一区| 久久九九全国免费| 亚洲AV无码久久| 伊人久久综合精品无码AV专区| 久久久久久噜噜精品免费直播| 国产精久久一区二区三区| 久久国产一区二区| 亚洲精品国产字幕久久不卡| 伊色综合久久之综合久久| 久久国产精品无码网站| 青青草原综合久久| 国产女人aaa级久久久级| 久久99中文字幕久久| 99久久99久久精品免费看蜜桃| 久久久久亚洲AV成人片| 成人久久免费网站| 少妇人妻88久久中文字幕| 亚洲AV无码1区2区久久| 久久婷婷国产综合精品| 久久久久久久女国产乱让韩| 97精品依人久久久大香线蕉97 | 国产精品久久午夜夜伦鲁鲁| 麻豆成人久久精品二区三区免费| 亚洲国产精品高清久久久| 无码国内精品久久人妻| 亚洲AV无码1区2区久久| 精品久久久久久国产|