パズル『えだぶり』雑文【グラフ理論のつまみ食い(3)「二部グラフ」とは何なのか？】

　普段は自作のパズル『えだぶり』の「問題」を投稿していますが，今回は前回に続き「雑文」として，グラフ理論についてお勉強（つまみ食い）したことを書いていきます。
　初学者の文章なので，間違いもあるかもしれません。
　詳しい方からのご指導ご鞭撻がいただければ幸いです。

　それでは，まず「グリッドグラフ」を説明します。

　例えば，上のグラフは「5×5 のグリッドグラフ」と呼べば，それで伝わるようです。

　では，次に「部分グラフ」を説明します。

　さらに

　それではいよいよ「二部グラフ」を説明です。

　さて，『えだぶり』はグリッドグラフの全域部分グラフを考えるパズルですが，実はグリッドグラフは二部グラフです。次の図のように，白い丸と黒い丸に分けて考えると，白い丸同士は隣接せず，黒い丸同士も隣接しません。

　さらに，「木」は（それがグリッドグラフの「木」ではなくても）必ず二部グラフになります。

　そして，こんなことがいえます。

　例えば上記の図の場合で言うと「白い丸の次数の和と黒い丸の次数の和は等しい」となります。
　白い丸は必ず黒い丸とつながっているのだから，白い丸から出る辺の数の総和と黒い丸から出る辺の数の総和は一致します。

　また，前回の『グラフ理論のつまみ食い(2)』で示したように

　･･･なので，こんなことがいえます。

　したがって，《例２》の場合，白い丸の次数の和も黒い丸の次数の和も頂点の数から１を引いた数になります。

　では問題です。

　前回の『グラフ理論のつまみ食い(2)』と同じパターンです。
　《第179問》では (2) の方が元になっています。そこから，いくつかの頂点の次数を 〇 にしてわからなくしたのが《第179問》の (1) です。
　では，どういう規則で 〇 にしたかわかりますか？

　上記の《第179問》を白い丸と黒い丸で分けてみます。

　この問題は $${ 10 \times 15 = 150 }$$ で，150 個の頂点を持ちます。
　また，白い丸の内，次数のわからない 〇 は 30 個あり，次数のわからない 〇 を除いた白い丸の次数の和は 119 になります。
　したがって，白い丸の次数の和は $${ 150－1=149 }$$ で，149 でなければいけないので，30 個の 〇 の次数の和は $${ 149 - 119 = 30 }$$ で 30 になるはずです。
　よって，〇 はすべて ① だったことがわかります。

　同様に考えます。
　黒い丸の内，次数のわからない ● は 11 個あり，次数のわからない ● を除いた黒い丸の次数の和は 105 になります。
　したがって，黒い丸の次数の和は $${ 150 - 1 = 149 }$$ で，149 でなければいけないので，11 個の ● の次数の和は $${ 149 - 105 = 44 }$$ で 44 になるはずです。
　$${ 44 = 4 \times 11 }$$ です。
　よって，● はすべて ❹ だったことがわかります。

　これにより，(1) の問題（難易度★★）を(2) の問題（難易度★）にして解くという別解が可能になります。
　ただ，前回同様まったく実用的ではありません。あくまで「二部グラフ」という見方の『えだぶり』への応用例ということでご理解ください。

《追記１》
　普段は『えだぶり』という自作のパズルを投稿しています。
　『えだぶり』のルールはシンプルです。
　上下左右に隣接する丸を閉路ができないようにつなげていき，すべての丸がつながれば完成です。
　丸の中の数字は，その丸が直接つながる丸の個数になります。
　詳しいルールはこちらをご覧ください。

《追記２》
　主観的ではありますが，問題に難易度をつけて投稿しています。
　若干の例外はありますが，易しい方から順に ｢☆｣｢★｣｢★☆｣｢★★｣｢★★☆｣｢★★★｣ の６段階です。

《追記３》
　今回は「雑文」ということで，問題はあくまでオマケでしたが，問題をメインにした投稿もたくさんあります。今まで投稿した問題の一覧はこちらです。

《追記４》
　今回も問題と解答のPDFファイルを無料でダウンロードできるようにしてあります。A4判に印刷することを想定していますが，適宜，拡大･縮小印刷してご利用ください。

《追記５》
　作問者（赤い矮星）は，今回の記事に掲載した問題（第179問）及びその解答の一切の著作権を放棄します。個人利用，商用利用の区別なく，転載，複製，改変，頒布など，自由に行うことができます。ただし，それらの行為によって生じたトラブルや損害などについては一切の責任を負いかねます。あくまでも自己責任でお使いください。