其實還是晚上的思考
為什么晚上這么多思考啊(╯‵□′)╯︵┻━┻
還有我還花了一個上午，就證了這么一個SB東西(╯‵□′)╯︵┻━┻
點雙存在條件
點雙聯通分量的定義：一個無向連通圖中不存在割點即可，
一個無向聯通圖是點雙，當且僅當滿足以下條件之一：
- 圖的頂點數不超過2
- 圖中任意兩點都存在于至少一個簡單環中（但是不是說所有點在一個簡單環），其中簡單環指的是不自交的環，也就是我們通常畫出來的環，
1條件很明顯，不說了，2條件的話，充分性很好證明， x , y x,y x,y都同時包含在至少一個簡單環中，則圖中一定沒有割點，是點雙，
但是必要性嗎，，，，
引理1：對于兩個相鄰的點雙（共用一個割點），這兩個邊已經滿足圖中任意兩點都包含在一個簡單環中，從這兩個點雙各選一個點（除了割點），連一條邊，可以證明，這個新形成點雙也滿足這個圖中任意兩點都包含在一個簡單環中，
證明：
這樣兩個綠點加割點形成簡單環，現在我們只需要證明，存在一條簡單路徑能從綠點走到藍點再走到黑點就可以了，
隨便選擇一個藍點到黑點的簡單環，設藍點為
a
a
a，黑點為
b
b
b，這樣就存在一條路徑：
a
?
>
x
1
?
>
x
2
?
>
x
3
?
>
.
.
.
?
>
b
、
a
?
>
y
1
?
>
y
2
?
>
y
3
?
>
.
.
.
?
>
b
a->x_1->x_2->x_3->...->b、a->y_1->y_2->y_3->...->b
a?>x1??>x2??>x3??>...?>b、a?>y1??>y2??>y3??>...?>b，首先如果藍點就在路徑上，直接存在，如果不在路徑上，
首先考慮綠點到藍點的一條路徑，其不可能與兩條路徑有交點，如果其只和一個路徑有交點，那么直接選擇即可，
如果與兩條路徑都有交點，那么按圖中選法即可（找到最早有交點的路徑直接走路徑即可），
這樣就證明啦QMQ
引理2（用來補充說明上面那個引理）：兩個點雙最多共用一個割點，
證明：如果共用兩個，這兩個點必然不是割點，證畢，
然后就可以證明了，對于一個點雙，建立一個生成樹，不斷加邊，最后一定會成為一個點雙的（如果不能成為點雙，那么說明原本就不存在點雙，）
邊雙存在條件
邊雙聯通分量的定義：一個無向連通圖中不存在橋即可，
一個無向聯通圖是點雙，當且僅當滿足這個條件：
圖中任意一條邊都存在于至少一個簡單環中（但是不是說所有點在一個簡單環），其中簡單環指的是不自交的環，也就是我們通常畫出來的環，
哇，這個簡直SB，充分性和上面差不多，必要性的話，
你把這個邊刪掉，然后不影響邊左右兩點的連通性，說明存在一條其他路徑，加上這條邊即可構成簡單環啊，簡直SB，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/95891.html
標籤：其他
上一篇：go env 命令介紹
下一篇：鴻蒙內核開發概述