課題９３：最長回路発見
ノード数 $n$ の無向グラフが隣接行列 $G$ で表されています。 $G$ は $n$ 行 $n$ 列の正方対称行列で、ノード $i$ とノード $j$ が隣接していれば $G_{i,j} = 1$、隣接していなければ $G_{i,j} = 0$ になっています。 $G$ を入力した時に、最大ノード数をもつ回路のうち１つを出力する関数を作成してください。回路が存在しない場合は、空の配列を返すようにしてください。
例1
n = 5
G = \
[[0, 0, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 1, 0],
[0, 1, 1, 0, 1],
[1, 1, 0, 1, 0]]
[1, 4, 3]
例2
n = 8
G = \
[[0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 1, 0, 0, 1, 0],
[0, 1, 1, 0, 1, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0]]
[]
例3
n = 10
G = \
[[0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
[0, 1, 0, 1, 0, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 1, 0, 0, 1, 0, 0, 0]]
[0, 9, 3, 7, 8, 1]
課題提出方法
-
基本的にGoogle Colaboratoryを用いてプログラミングしてください。どうしても Google Colaboratory を用いることができない場合のみ、Jupyter Notebook または Jupyter Lab を用いてください。
-
課題１つごとに、ノートブックを新規作成してください。１つのノートブックで複数の課題を解かないでください。
-
ノートブックを新規作成すると「Untitled.ipynb」のような名前になりますが、それを「学籍番号・氏名・課題番号」のような名前に変更してください。
-
質問・感想・要望などございましたらぜひ書き込んでください。
-
もし課題を解くにあたって参考になったウェブサイトがあれば、それについても触れてください。
-
課題を計算し終わった ipynb ファイルを提出するときは、指定したメールアドレスに Google Drive で共有する形で授業担当者に提出してください。