混合圖歐拉回路
原來混合圖歐拉回路用的是網(wǎng)絡(luò)流。
把該圖的無向邊隨便定向，計(jì)算每個(gè)點(diǎn)的入度和出度。如果有某個(gè)點(diǎn)出入度之差為奇數(shù)，那么肯定不存在歐拉回路。因?yàn)闅W拉回路要求每點(diǎn)入度 = 出度，也就是總度數(shù)為偶數(shù)，存在奇數(shù)度點(diǎn)必不能有歐拉回路。
好了，現(xiàn)在每個(gè)點(diǎn)入度和出度之差均為偶數(shù)。那么將這個(gè)偶數(shù)除以2，得x。也就是說，對(duì)于每一個(gè)點(diǎn)，只要將x條邊改變方向（入>出就是變?nèi)耄?/span>>入就是變出），就能保證出 = 入。如果每個(gè)點(diǎn)都是出 = 入，那么很明顯，該圖就存在歐拉回路。
現(xiàn)在的問題就變成了：我該改變哪些邊，可以讓每個(gè)點(diǎn)出 = 入？構(gòu)造網(wǎng)絡(luò)流模型。首先，有向邊是不能改變方向的，要之無用，刪。一開始不是把無向邊定向了嗎？定的是什么向，就把網(wǎng)絡(luò)構(gòu)建成什么樣，邊長(zhǎng)容量上限1。另新建s和t。對(duì)于入 > 出的點(diǎn)u，連接邊(u, t)、容量為x，對(duì)于出 > 入的點(diǎn)v，連接邊(s, v)，容量為x（注意對(duì)不同的點(diǎn)x不同）。之后，察看是否有滿流的分配。有就是能有歐拉回路，沒有就是沒有。歐拉回路是哪個(gè)？察看流值分配，將所有流量非0（上限是1，流值不是0就是1）的邊反向，就能得到每點(diǎn)入度 = 出度的歐拉圖。
由于是滿流，所以每個(gè)入 > 出的點(diǎn)，都有x條邊進(jìn)來，將這些進(jìn)來的邊反向，OK，入 = 出了。對(duì)于出 > 入的點(diǎn)亦然。那么，沒和s、t連接的點(diǎn)怎么辦？和s連接的條件是出 > 入，和t連接的條件是入 > 出，那么這個(gè)既沒和s也沒和t連接的點(diǎn)，自然早在開始就已經(jīng)滿足入 = 出了。那么在網(wǎng)絡(luò)流過程中，這些點(diǎn)屬于“中間點(diǎn)”。我們知道中間點(diǎn)流量不允許有累積的，這樣，進(jìn)去多少就出來多少，反向之后，自然仍保持平衡。
所以，就這樣，混合圖歐拉回路問題，解了。
今天碰到一題是求這的...寫下筆記......
http://acm.pku.edu.cn/JudgeOnline/problem?id=1637
posted on 2008-08-02 22:09
小果子 閱讀(967)
評(píng)論(1) 編輯 收藏 引用