離散数学のカット枝について

質問

以下のような問題がありました。回答が掲載されていないので回答例を教えてください

1.切断枝（カット枝、橋）の定義を書け
2.グラフの枝がカット枝であるための必要十分条件は、その枝がどの閉路にも属さないことであることを証明せよ。

よろしくお願いします。

回答No.1

tmpname · ベストアンサー

1. 定義はここに書いてあります
https://ja.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E3%82%B0%E3%83%A9%E3%83%95#.E8.BE.BA.E9.80.A3.E7.B5.90.E5.BA.A6
要は、「連結グラフにおいて、それを取り除くと（グラフ全体が）非連結になってしまうような辺」のことを「切断辺（橋）」という。なお、枝も辺も同じです。

2.
方針だけ書きます。細かい記述（きちんと記号等をつかって「証明っぽく」書くにはどうするか）は一度考えてみてください。
対偶をとって、「A: 辺が切断辺でない」事と「B: 辺が何らかの閉路に属する」ことの同値性を示す。

A→B
切断辺の定義から、「頂点CDをつなぐ辺eが切断辺でない」でないなら、辺eを取り除いてもそのグラフは連結であるので、頂点CとDとの間は（辺eを使わない）パスがある。そのパスと辺eを再びつなげば、それは閉路になる。

B→A
「頂点CDをつなぐ辺eがある閉路に属する」から、その閉路に着目すると、頂点CからDへ辺eを使った後、DからCへ辺eを使わずに戻るパスxがある。従って、ある頂点EからFへのパスで辺eを使うものは、辺eの部分をパスx（もしくはパスxの逆向き）に置き換え、頂点の重複をのぞけば、EからFへのパスで辺eを使わないものが作れる。
従ってそのグラフから辺eを取り除いてもグラフは連結のままで、辺eは橋ではない。