『線路の問題』

　インターネットは災害に強いとよく言われますね。
不通の個所が少々できても、遠回りをすれば全体としては連絡可能な場合が多いからです。

今回のテーマはネットワークについての問題です。

今、いくつかの点（頂点と呼びます）を、曲線（辺と呼びます）で結んだ図形を考えます。
頂点は駅、辺は線路として、鉄道の線路網を思い出してもらえばよいと思います。
今、事故で線路が切断されたとして、最大何カ所切断されても全体として不通にならないか（切断数と呼びます）を考えます。

◆図１
　
頂点は５個、辺の数は４本です。
この線路は事故で一カ所切断されただけで、不通になります。

◆図２
　
頂点は５個、辺の数は５本です。
環状線になっているので、一カ所切断されても大丈夫です。

◆図３
　
頂点は１０個、辺の数は１１本です。
二カ所切断されても、全体としては不通になりません。

【問題１】

　切断数は、辺の数と頂点の数を用いて表すことができます。

（１）その関係式を予想してください。

（２）環状線を一つも含まないとき（木といいます）、その式が正しいことを示してください。

（３）（２）を利用して、一般の場合にも、（１）の式が正しいことを示してください。

【問題２】

　次の線路網は最大で何カ所事故で切断されても、全体としては不通にはならないでしょうか。

　
切断数を計算してください。

　◆図形問題へもどる