DAG相關(guān)

最小路徑覆蓋

定義：最少不重路徑覆蓋DAG

初始時(shí)每個(gè)點(diǎn)是獨(dú)立的

之后每次加一條邊把兩個(gè)點(diǎn)連到一起 因?yàn)橹荒苡靡淮?#xff0c;所以是個(gè)最大匹配

$$\text{最小路徑覆蓋=N-拆點(diǎn)后最大匹配}$$

最小鏈覆蓋

定義：最少可重路徑覆蓋DAG

感性理解，某個(gè)流到了下面發(fā)現(xiàn)堵住了，也就是匹配過(guò)了

大概就是這樣

由于頂點(diǎn)可以重復(fù)，這個(gè)時(shí)候小紅紅可以往外面跑

所以每個(gè)點(diǎn)反著往自己連邊，從頭開(kāi)始匹配

最長(zhǎng)反鏈

定義：DAG選最多的點(diǎn)不能互相到達(dá)

$$\text{Dilworth定理：最長(zhǎng)反鏈=最小鏈覆蓋}$$

二分圖相關(guān)

$$\text{最小頂點(diǎn)覆蓋=最大匹配=N-最大獨(dú)立集}$$

懶得證了

總結(jié)

以上是生活随笔為你收集整理的【水】几个网络流图论模型的记录的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。