任何圖都可以轉化成二分圖嗎？

我有一個無向聯通圖，每個節點代表一個用戶，邊代表用戶之間互相follow，我可以把這個圖轉化成二分圖嗎？比如有n個節點，二分圖的左邊是X1...X2，二分圖右邊是y1....yn

---

以免題主沒看懂 @王希的嚴謹推導，本弱來給你不嚴謹地證明一下為什麼不含奇環對於二分圖來說是充分必要的。

必要性：

考慮對圖進行二分圖染色。如果兩個節點之間有一條長度為奇數的路徑，那麼顯然兩個點顏色不同，反之如果兩個節點之間有一條長度為偶數的路徑，那麼兩個點顏色必定相同（這是顯然的）。

如果圖中存在奇環，那麼我們任取環上兩點，可以發現如果從環的兩邊走，那麼兩條路徑必定是一奇一偶的，所以我們無法就行二分圖染色，即原圖不是二分圖。

充分性：

還是考慮二分圖染色的過程。假設某個點的顏色既是黑色又是白色，那麼說明從起點到這個點存在一條奇路徑，也存在一條偶路徑，那麼我們就可以構造出一個奇環（因為兩條路徑之和是奇數）（注意這裡的環不一定是簡單環，有可能有某些邊被走兩次）。而原圖不存在奇環，所以這種情況不可能發生，即原圖一定可以被二分圖染色，即原圖就是個二分圖。

Q.E.D.

---

必須沒有奇環

---

啥叫「轉化」……只有是或者不是吧？因為同構的圖我們認為是一樣的。

結論：一張圖是二分圖當且僅當其不含奇圈。

證明：

1.必要性。二分圖的邊是在兩個集合里交替的，顯然不會出現奇圈。

2.充分性。設不含奇圈，任取,令

（即 X 是距離為奇數的， Y 是距離為偶數的）任取其一條邊，只需證分別屬於和。

設分別為到的最短路。

（1）如果與的最後一個公共頂點是，不妨設是.因為的段都是最短路，故這兩段等長。因此長度差,其奇偶性相反，屬於不同集合。

（2）如果最後一個頂點不是，不妨設為.則段是一樣的。假如其奇偶性相同，則的和的奇偶性相同，它們和構成了一個奇圈，矛盾。

證畢。

謝謝 @玄星指出了兩處不嚴謹的地方：

（1）當時。

補充：此時是平凡情況，顯然成立。

（2）當不存在時。

補充：對於連通圖，這樣的路徑存在；對於非連通圖，考慮其每一個連通分支。

---

你只能說一個圖「是不是」二分圖。「轉化」這個詞令人不知所云。

是指同構變換嗎？那你相當於在問「是不是任何圖都是二分圖」，顯然否，反例如；

是允許非同構變換嗎？那隻要去掉所有邊就可以得到二分圖啦（

---

拆點。

一個用戶拆成左右兩點，ab互相follow的話就左a右b連邊再左b右a連邊。這就是一個二分圖，且包含和原來一樣的信息。

就是不知道這算不算「轉化」。

---

可以，得到一個二分圖X={x0},Y={y0},E={(x0,y0)}。

什麼？你說和原圖沒有關係？那不怪我，你也沒說清楚轉化要保留什麼性質啊。

---

推薦閱讀：