川渡り問題を一般化してみる

「川渡り問題」というパズルがあります。Wikipediaから拾ってきますと、

オオカミとヤギを連れキャベツを持った農夫が川岸にいる。川にはボートがあるが農夫の他には動物一頭かキャベツ一個しか乗せられない。農夫がいなければオオカミはヤギを襲うし、ヤギはキャベツを食べてしまう。すべてを無事に対岸に渡すにはどうしたらよいか?(Wikipedia 川渡り問題より)

というものです。この問題を一般化してみようと思います。すると、こうなります。

ｎ頭の動物を持った農夫が川岸にいる。川にはボートがあるが、農夫の他には動物ｋ頭しか乗せられない。農夫がいなければ、いくつかの動物はほかの動物を食べてしまう。すべてを無事に対岸に渡すにはどうしたらよいか?

この「いくつかの動物はほかの動物を食べてしまう」という捕食関係については、各動物は点、食う食われるは辺として、グラフで表してみます。上のオオカミ、ヤギ、キャベツの場合は下のようになります。

食う食われるといっても、同席してはいけないだけなので、グラフが有向である必要はありません。
このグラフ上で辺で結ばれている動物を農夫のいないところに残さないようにしながら、すべての動物を対岸に渡すことを考えます。

さて、ここで考えたいのは、「与えられたグラフに対して、川を渡ることのできる最小のｋはいくつか？」という問題です。オリジナルの問題については、k=1で渡ることができます。
グラフに辺がない場合はk=1でできますし、グラフが完全グラフならk=n-1か最小となります。

ということで、n≦4の場合について、グラフに対する最小のkを調べてみました。

以下、「k」は「グラフに対する最小のk」を指します。手順は載せていません(そのうち載せるかも…？)。

グラフ		n		k		備考
		2		1		非連結
		2		1		完全グラフ
		3		1		非連結
		3		1		非連結
		3		1		オオカミ、ヤギ、キャベツの問題
		3		2		完全グラフ
		4		1		非連結
		4		1		非連結
		4		1		非連結
		4		2		非連結
		4		2		非連結
		4		2
		4		2
		4		2
		4		2
		4		2
		4		3		完全グラフ

非連結な場合は、(そのグラフのk)≦(各連結成分ごとのkの和)が成り立つはずです。等号は成り立つ場合も成り立たない場合もあります(どちらも上の表の中にあります)。
n=5も調べてありますが、グラフの画像を作れていないので、またそのうち。