青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

二分圖最小覆蓋的Konig定理及其證明,最小路徑覆蓋證明

二分圖最小覆蓋的Konig定理及其證明

二分圖:

頂點可以分類兩個集合X和Y,所有的邊關聯在兩個頂點中,恰好一個屬于集合X,另一個屬于集合Y。

最小覆蓋:

最小覆蓋要求用最少的點(X集合或Y集合的都行)讓每條邊都至少和其中一個點關聯。可以證明:最少的點(即覆蓋數)=最大匹配數

Konig定理:

二分圖的最小頂點覆蓋數等于最大匹配數。

 證明:

 為主便敘述,假設G分為左邊X和右邊Y兩個互不相交的點集。。。。。。

假設G經過匈牙利算法后找到一個最大匹配M,則可知G中再也找不到一條增廣路徑。

標記右邊未匹配邊的頂點,并從右邊未匹配邊的頂點出發,按照邊:未匹配->匹配->未匹配...,的原則標記途中經過的頂點,則最后一條經過的邊必定為匹配邊。重復上述過程,直到右邊不再含有未匹配邊的點。

記得到的左邊已標記的點和右邊未標記的點為S, 以下證明S即為所求的最小頂點集。

1| S | == M 
    顯然,左邊標記的點全都為匹配邊的頂點,右邊未標記的點也為匹配邊的頂點。因此,我們得到的點與匹配邊一一對應。

2S能覆蓋G中所有的邊。

       上途S中點所得到的邊有以下幾種情況:

       1)左右均標記;

       2)左右均無標記;

       3)左邊標記,右邊未標記;

       若存在一條邊e不屬于S所覆蓋的邊集,則e 左邊未標記右邊標記。

如果e不屬于匹配邊,那么左端點就可以通過這條邊到達(從而得到標記);如果e屬于匹配邊,那么右端點不可能是一條路徑的起點,于是它的標記只能是從這條邊的左端點過來的左端點就應該有標記。

 

3S是最小的覆蓋。

       因為要覆蓋這M條匹配邊至少就需要M個點。

轉自:http://yejingx.ycool.com/post.2801156.html#



在一個PXP的有向圖中,路徑覆蓋就是在圖中找一些路經,使之覆蓋了圖中的所有頂點,且任何一個頂點有且只有一條路徑與之關聯;(如果把這些路徑中的每條路徑從它的起始點走到它的終點,那么恰好可以經過圖中的每個頂點一次且僅一次);如果不考慮圖中存在回路,那么每每條路徑就是一個弱連通子集.

由上面可以得出:

1.一個單獨的頂點是一條路徑;

2.如果存在一路徑p1,p2,......pk,其中p1 為起點,pk為終點,那么在覆蓋圖中,頂點p1,p2,......pk不再與其它的頂點之間存在有向邊.

最小路徑覆蓋就是找出最小的路徑條數,使之成為P的一個路徑覆蓋.

路徑覆蓋與二分圖匹配的關系:

最小路徑覆蓋=|P|-最大匹配數;

其中最大匹配數的求法是把P中的每個頂點pi分成兩個頂點pi'與pi'',如果在p中存在一條pi到pj的邊,那么在二分圖P'中就有一條連接pi'與pj''的無向邊;這里pi' 就是p中pi的出邊,pj''就是p中pj 的一條入邊;

對于公式:最小路徑覆蓋=|P|-最大匹配數;可以這么來理解;

如果匹配數為零,那么P中不存在有向邊,于是顯然有:

最小路徑覆蓋=|P|-最大匹配數=|P|-0=|P|;即P的最小路徑覆蓋數為|P|;

P'中不在于匹配邊時,路徑覆蓋數為|P|;

如果在P'中增加一條匹配邊pi'-->pj'',那么在圖P的路徑覆蓋中就存在一條由pi連接pj的邊,也就是說pi與pj 在一條路徑上,于是路徑覆蓋數就可以減少一個;

如此繼續增加匹配邊,每增加一條,路徑覆蓋數就減少一條;直到匹配邊不能繼續增加時,路徑覆蓋數也不能再減少了,此時就有了前面的公式;但是這里只 是說話了每條匹配邊對應于路徑覆蓋中的一條路徑上的一條連接兩個點之間的有向邊;下面來說明一個路徑覆蓋中的每條連接兩個頂點之間的有向邊對應于一條匹配 邊;

與前面類似,對于路徑覆蓋中的每條連接兩個頂點之間的每條有向邊pi--->pj,我們可以在匹配圖中對應做一條連接pi'與pj''的邊, 顯然這樣做出來圖的是一個匹配圖(這一點用反證法很容易證明,如果得到的圖不是一個匹配圖,那么這個圖中必定存在這樣兩條邊  pi'---pj'' 及 pi' ----pk'',(j!=k),那么在路徑覆蓋圖中就存在了兩條邊pi-->pj, pi--->pk ,那邊從pi出發的路徑就不止一條了,這與路徑覆蓋圖是矛盾的;還有另外一種情況就是存在pi'---pj'',pk'---pj'',這種情況也類似可證);

至此,就說明了匹配邊與路徑覆蓋圖中連接兩頂點之間邊的一一對應關系,那么也就說明了前面的公式成立!

轉自:http://hi.baidu.com/cjhh314/blog/item/ded8d31f15d7510c304e1591.html



posted on 2009-09-02 23:06 abilitytao 閱讀(2969) 評論(0)  編輯 收藏 引用

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲激情网站免费观看| 在线不卡免费欧美| 亚洲视频精选在线| 亚洲毛片在线观看| 欧美日韩一区三区| 午夜在线成人av| 亚洲欧美日韩一区二区在线| 国产香蕉97碰碰久久人人| 久久都是精品| 久久综合一区| 一本色道综合亚洲| 亚洲午夜久久久久久尤物 | 老司机午夜免费精品视频| 亚洲一区二三| 国际精品欧美精品| 免费视频一区二区三区在线观看| 欧美福利影院| 午夜精品久久久久久久99水蜜桃 | 欧美不卡在线视频| 欧美激情在线播放| 午夜精品一区二区三区在线视| 欧美一区二区性| 亚洲欧洲另类国产综合| 夜夜狂射影院欧美极品| 韩日在线一区| 一区二区三区av| 精品91在线| 一本大道久久a久久精二百| 精品动漫3d一区二区三区| 亚洲人成网站在线观看播放| 欧美性片在线观看| 欧美成年人视频网站欧美| 国产精品国产三级国产aⅴ入口| 美女免费视频一区| 国产精品欧美日韩一区| 亚洲激情黄色| 国产最新精品精品你懂的| 日韩一级黄色片| 在线看欧美视频| 午夜精品久久久久久久99樱桃 | 国产精品免费视频观看| 狂野欧美一区| 国产欧美精品在线观看| 亚洲欧洲精品一区二区三区不卡| 国产午夜精品全部视频播放 | 亚洲国产欧美精品| 合欧美一区二区三区| 亚洲一区二区三区在线| 亚洲美女视频网| 久久久免费精品| 久久久久久久久蜜桃| 国产精品一区二区a| 亚洲精品一区中文| 亚洲精品小视频| 开心色5月久久精品| 美日韩精品免费观看视频| 国产精品久久久久一区二区三区 | 亚洲午夜日本在线观看| 一本一本久久a久久精品综合妖精 一本一本久久a久久精品综合麻豆 | 亚洲丶国产丶欧美一区二区三区| 亚洲综合精品自拍| 亚洲尤物视频网| 欧美日韩和欧美的一区二区| 亚洲高清av在线| 久久久噜噜噜久久久| 国产精品久99| 亚洲综合成人婷婷小说| 亚洲欧美日韩精品久久久久| 国产精品电影在线观看| 妖精视频成人观看www| 亚洲一区二区三区四区五区黄 | 午夜在线精品偷拍| 亚洲欧美在线x视频| 国产精品扒开腿爽爽爽视频| 亚洲最新中文字幕| 亚洲一区二区影院| 国产精品久久久久一区二区| 亚洲欧美中文在线视频| 欧美一区激情视频在线观看| 国产亚洲欧美日韩在线一区 | 亚洲免费精品| 亚洲一区二区三区色| 国产麻豆综合| 久久精品视频99| 亚洲成人直播| 一区二区三区精密机械公司| 国产精品黄色| 久久岛国电影| 亚洲黄色精品| 午夜精品福利视频| 激情综合激情| 欧美日韩四区| 欧美在线精品一区| 免费亚洲电影在线| 亚洲已满18点击进入久久| 国产精品夜夜嗨| 玖玖国产精品视频| 在线一区二区三区做爰视频网站 | 日韩亚洲欧美中文三级| 欧美午夜a级限制福利片| 午夜精品www| 欧美国产精品久久| 午夜精品福利电影| 亚洲激情在线激情| 国产精品私房写真福利视频| 久久久精品日韩欧美| 亚洲精品欧美极品| 久久亚洲春色中文字幕| 一区二区三区波多野结衣在线观看| 国产精品亚洲综合久久| 欧美激情2020午夜免费观看| 西瓜成人精品人成网站| 亚洲精品国产精品国产自| 久久人91精品久久久久久不卡| 一区二区激情| 在线播放国产一区中文字幕剧情欧美 | 91久久在线| 久久综合综合久久综合| 亚洲字幕在线观看| 亚洲精品网站在线播放gif| 国产视频一区三区| 欧美日韩在线视频一区| 久久中文久久字幕| 欧美在线观看你懂的| 夜夜嗨av一区二区三区网页| 亚洲国产成人精品女人久久久 | 国产精品视频久久久| 中文在线资源观看视频网站免费不卡| 久久久夜精品| 午夜欧美精品| 亚洲午夜在线观看| 亚洲巨乳在线| 亚洲二区视频在线| 国内精品嫩模av私拍在线观看| 国产精品国产精品| 欧美亚洲不卡| 欧美日韩国产在线播放| 欧美激情91| 欧美黄色小视频| 欧美国内亚洲| 欧美激情bt| 欧美国产91| 欧美激情视频一区二区三区免费| 久久在线免费观看| 久久综合九九| 蜜桃av久久久亚洲精品| 美女精品国产| 免费亚洲电影在线| 欧美多人爱爱视频网站| 米奇777在线欧美播放| 欧美二区在线看| 欧美高清在线播放| 欧美欧美在线| 欧美色图麻豆| 国产精品久久久久影院亚瑟| 国产精品国产三级国产aⅴ无密码 国产精品国产三级国产aⅴ入口 | 老巨人导航500精品| 欧美大片国产精品| 亚洲日本在线观看| 亚洲天堂黄色| 欧美永久精品| 免费观看成人鲁鲁鲁鲁鲁视频| 欧美粗暴jizz性欧美20| 欧美日韩一区在线观看视频| 国产精品亚洲а∨天堂免在线| 国产视频精品xxxx| 在线观看欧美| 亚洲视频999| 久久精品国产第一区二区三区| 欧美成人一二三| 亚洲精品日本| 欧美伊人久久| 欧美高清视频在线观看| 欧美日韩亚洲综合在线| 国产欧美日韩精品丝袜高跟鞋| 一区二区三区在线视频观看 | 国产亚洲高清视频| 激情亚洲一区二区三区四区| 99re8这里有精品热视频免费| 亚洲综合色网站| 久久中文精品| 日韩视频一区二区在线观看| 欧美一区二区精品久久911| 欧美成人性网| 国产欧美精品在线观看| 亚洲日本乱码在线观看| 亚洲欧洲99久久| 亚洲第一伊人| 亚洲在线视频观看| 欧美成人蜜桃| 国产午夜精品美女毛片视频| 一本大道久久a久久综合婷婷| 久久精品水蜜桃av综合天堂| 亚洲精选在线| 久久综合狠狠| 国产毛片一区| 亚洲图中文字幕| 欧美激情成人在线| 久久精品国产96久久久香蕉| 欧美日韩一区二区三区免费|