解答つきグラフ理論ワークシート

示されたグラフΣ degのすべての頂点の次数の和を求めてください。

単純グラフに 6 個の頂点があり、次数は 3, 3, 3, 2, 2, 1 です。辺は何本|E|ありますか？

連結グラフに 16 個の頂点と 23 本の辺があります。全域木にするには、辺を何本k取り除く必要がありますか？

連結グラフに 9 個の頂点と 18 本の辺があります。全域木にするには、辺を何本k取り除く必要がありますか？

プリム法は、頂点 F から始めて最小全域木をつくります。それが 5 番目に加える辺をクリックしてください。

1. 1辺 AB
2. 2辺 AC
3. 3辺 BC
4. 4辺 BD
5. 5辺 CE
6. 6辺 DE
7. 7辺 DF
8. 8辺 EF

ダイクストラ法を使って、重み付きグラフで A から F までの最短経路の長さd(F)を求めてください。