# Graph challanges ## Is a graph [bipartite](http://web.ntnu.edu.tw/~algo/BipartiteGraph.html)? ### 定義 可以把一個 graph 的 vertices 分成兩個 subsets 嗎？ 即兩個 subset 裡面的 vertices 互相不互相接. ### 難度 有學過演算法的學生都可以解答的出來 ### 解決方法 DFS 演算法可以確認一個 graph 是否為 bipartite [textbook code](https://algs4.cs.princeton.edu/41graph/Bipartite.java.html) [GeeksForGeeks](https://www.geeksforgeeks.org/check-if-a-given-graph-is-bipartite-using-dfs/) BFS 演算法可以確認一個 graph 是否為 bipartite [GeeksForGeeks](https://www.geeksforgeeks.org/bipartite-graph/) ### 實際案例 約會關係的 graph 中, 是否可以判斷為 bipartite: 一定是一男一女才會有約會關係 (人為 vertices, 顏色為性別, 約會關係為 edge) 結論: 這張圖可能是 bipartite, 但現在的社會已經不一定了. ### leetcode [Is Graph Bipartite](https://leetcode.com/problems/is-graph-bipartite/) ## Find a cycle 在一個 graph 找出 cycle ### 定義 從一個點出發, 是否可以走回原點. 後面的有向圖 DAG 也會用到相同概念 ### 難度 沒學過演算法的程序員也可以解答的出來 ### 解決方法 DFS 解決最簡單 [textbook code](https://algs4.cs.princeton.edu/41graph/Cycle.java.html) [GeeksForGeek](https://www.geeksforgeeks.org/detect-cycle-undirected-graph/) ### leetcode [Course Schedule](https://leetcode.com/problems/course-schedule/) ### Open question ``` javascript // If an adjacent is not // visited, then recur for that // adjacent if (!visited[i]) { if (isCyclicUtil(i, visited, v)) return true; } // If an adjacent is visited // and not parent of current // vertex, then there is a cycle. else if (i != parent) return true; ``` ![](https://i.imgur.com/lBx20rs.png) node 4 鄰近的 node 有 2，3，5 DFS 下一個走 5 的話沒有 visited 所以會繼續 DFS 下去 DFS 下一個走 3 的話是 parent (visited), 所以沒辦法說他是 cycle DFS 下一個走 2 的話是 visited 而且也不是 parent, 判斷為 cycle Cycle 為 2->3->4->2 ## [七橋問題 (又稱作: Eulerian tour, Eulerian cycle)](https://medium.com/marketingdatascience/%E4%B8%80%E7%AD%86%E7%95%AB%E8%88%87%E6%9F%AF%E5%B0%BC%E6%96%AF%E5%A0%A1%E4%B8%83%E6%A9%8B%E5%95%8F%E9%A1%8C-seven-bridges-of-k%C3%B6nigsberg-653f67c576d3) ### 定義 算是 Find a cycle 的延伸案例, 是否在經過每個 edge 一次的前提下最後回到原點 Euler path: 存在一個路徑可以走過全部邊, 但是這個路徑不一定能夠回到原點 Euler cycle: 存在一個路徑可以走過全部邊, 且能夠回到原點 [補充](https://courses.lumenlearning.com/wmopen-mathforliberalarts/chapter/introduction-euler-paths/) Semi-Eulerian: 有 Euler path 但是沒有 Euler cycle ![](https://i.imgur.com/kk3XFgp.png) ### 難度 有學過演算法的學生都可以解答的出來 ### 解決方法 * 通用證明: 如果這個 graph 中每個 vertices 都有偶數個 degrees, 就可以, 所以七橋問題無解, 因為圖中有 vertices 有基數個 degrees * 程式證明： [textbook code](https://algs4.cs.princeton.edu/41graph/EulerianCycle.java.html) [GeeksForGeeks](https://www.geeksforgeeks.org/eulerian-path-and-circuit/) ### leetcode [Reconstruct Itinerary](https://leetcode.com/problems/reconstruct-itinerary/) ### Open question Note that odd degree vertex count can never be 1 for undirected graph Whyyyyyyyyyyyyyy? ## [Travelling salesperson problem (Hamiltonian cycle)](http://episte.math.ntu.edu.tw/articles/mm/mm_11_3_02/) ### 定義 Find a cycle that uses every edge exactly once. 原本的問題要包含成本的概念, 現在只需要找到是否有 cycle. [Hamiltonian cycle](http://web.ntnu.edu.tw/~algo/Circuit.html) ### 難度 很難 [NP-complete](https://www.ycc.idv.tw/algorithm-complexity-theory.html) 問題 (課程後面會解釋). 沒有一個很有效率的方法, 當 graph 很大的時候(?) ## Are two graphs identical except for vertex names? ### 定義 (我自己定義) 如何確定兩個 graphs 是完全相同的, 當所有 vertices 的名字都不一樣的時候 ### 難度 超難, 無解 graph isomorphism is longstanding open problem (目前還是個開放問題) isomorphism(同構) ### 解決方法 目前的方向是, 一直改變 vertices 的名字來確定到底是不是相同(?) 但這個解法是指數型的, 所以當 graph 超大的時候一定解不出來. ## [Planarity algorithm](https://www.easyatm.com.tw/wiki/%E5%B9%B3%E9%9D%A2%E6%80%A7%E7%AE%97%E6%B3%95) ### 定義 Lay out a graph in the plane without crossing edges? 指判定一個 graph 是否為可平面圖 (任意兩邊不能有交叉) ### 難度 有難度 ### 解決方法 使用 Planarity algorithm(based on DFS) 可以在線型的時間內找出答案, 但是對本課程的學生太難了.