1. 題目說明:
請依下列題意進行作答,使輸出值符合題意要求。
2. 設計說明:
(1) 尤拉路徑是圖論(Graph Theory)中被廣為人知的一個經典問題,又被稱為「一筆畫問題」,起源於哥尼斯堡七橋問題;數學家尤拉(Euler)在 1736 年解開了七橋問題並提出相關結論與定理:如果能夠從圖上某一點當作起點出發,找出一條路徑可以通過圖上所有邊恰好一次,就好像用畫筆可以連續地畫過該圖形的所有邊,該路徑就稱為「尤拉路徑(Euler path)」。
(2) 以下是尤拉對於一筆畫問題的重點結論:
「一個連通圖中,所有節點的分支度都是偶數,或只有 2 個節點的分支度是奇數,則該圖就可以用一筆畫完成;否則無法一筆畫。」
(3) 一個無向圖(Undirected Graph)通常表示為 G=(V,E),其中 V 為節點(Vertex)的集合,E 為邊(Edge)的集合,且任一個邊是由兩個相連接的節點所構成,當標示為 (a,b) 即表示節點 a 與 b 之間有邊連接。
(4) 請設計一支程式,可以讀取一個無向圖的資料(邊的列表),然後判斷該圖形是否能夠一筆畫完成,並輸出圖形的相鄰矩陣結果(注意:題目給的圖形一定是「連通圖」)。
提示:任一節點的「分支度(Degree)」為該節點連接的邊數、亦即是對外所連接的節點數。
提示:「連通圖(Connected Graph)」中的任兩個節點必存在一條路徑相通;反之則為「非連通圖」。
提示:可使用「二維陣列(Two-Dimensional Array)」資料結構來實作「相鄰矩陣(Adjacency Matrix)」以紀錄圖形中節點與節點的關係(邊)。
第 1 列:包含兩個正整數 M、N,並以半形空白間隔,其中 M 為節點數、N 為邊數。
第 2~N+1 列:每一列包含兩個正整數 a、b,並以半形空白間隔,代表圖形的某一個邊連接節點 a 與 b,且 1 ≤ a, b ≤ M。
第 1 列:若圖形可以「一筆畫完成」,則輸出「YES」;否則輸出「NO」。
第 2~M+1 列:輸出圖形的相鄰矩陣,共有 M 列由 0 與 1 所構成的資料列,每一列有 M 個數字,請使用「1」表示列、行相對應的節點之間有邊;使用「0」表示沒有對應邊的存在,每個數字之間須以半形空白間隔。
3 3 1 2 1 3 3 2
YES 0 1 1 1 0 1 1 1 0
5 8 1 2 1 3 1 4 1 5 2 5 3 2 3 4 5 4
NO 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||