graphのパズル
１．パーティー握手人数問題
このワークシートはMath by Codeの一部です。
こんなパズルがあります。
「あるパーティーにN組２N人の夫婦が参加しています。
Xさん夫婦も参加しました。どの夫婦もパートナーとは握手しませんでした。
Xさんが自分以外の参加者全員に「握手人数」取材したところ、全員バラバラでした。
Xさん夫婦は何人と握手したでしょうか。」
＜小さい数で実験＞
＊抽象的な問題に出会ったら、具体的な数で試してみる
＊そして、極端なものに着目して規則性を見つける
＊段階的に動的に調べる
という３つの方針で取り組んでみよう。
・n=２の4人パーティーの場合。
握手の最大人数は自分とパートナーをのぞく4-2=2人です。
Xさん以外は3人だから、2以下の異なる３数は｛0,1,2｝と決まりますね。
Xさんの取材した握手人数は０,1,2の3通りとわかります。
握手数で人にゼッケンをつけて調べましょう。全員のゼッケンは0,1,2,xとなりました。
次は、最大と最小に着目して段階的に調べましょう。
「２」さんは「０」「２」以外の「１」「ｘ」の２人と握手しました。
「２」「１」「０」さんはもう握手数を達成したので終了です。
このうち、「２」と握手していないのは「０」なので、「２」と「０」が夫婦ですね。
すると、残った「１」と「ｘ」が夫婦だから、それぞれ１回の握手が答えです。
・n=３の６人パーティーの場合。
握手の最大人数は自分とパートナーをのぞく６-2=4人です。
Xさん以外は５人だから、４以下の異なる５数は｛0,1,2,3,4｝と決まります。
Xさんの取材した握手人数は０,1,2,3,4の5通りとわかります。
握手数で人にゼッケンをつけて調べましょう。全員のゼッケンは0,1,2,3,4,xとなりました。
次は、最大と最小に着目して段階的に調べましょう。
「4」さんは「0」「4」以外の{１,2,3,ｘ}の4人と握手しました。
「4」「1」「0」さんはもう握手数を達成したので終了です。
このうち、「4」と握手していないのは「0」なので、「4」と「0」が夫婦ですね。
次に残った、{2,3,ｘ}を考えます。
「3」さんはさっきの「４」さんに加え{2,ｘ}の2人と握手します。
「3」「2」さんはもう握手数を達成したので終了です。
「3」と握手していないのは「1」なので、「3」と「1」が夫婦ですね。
すると、残った「2」と「ｘ」も夫婦だから、それぞれ２回の握手が答えです。
＜一般化してみよう＞
ｍ＝2nとおくと、m人の参加者のうち、Xさんが取材した人数は「m-1」人だね。
最大の「握手人数」を答えた人は、自分とパートナーの２人を除く「m-2」人と握手できる。
しかし、m-1人の取材結果がすべて異なるということは、最小の「握手人数」は「０」人となる。
そこで、簡単のために、参加者を点とし、点の名前を「握手人数」で表そう。
Xは未定で、Xさんのパートナーは０からｍ−２のどれかになる。
すると、この握手人数問題は、０、１、…,m−２とXのｍ人の連結状態を表すグラフをかく問題に置き換えることができるね。
ｍ個の点V={X, m-2,m-3,.....,2,1,0}がある。
ｍ人を握手数を達成したかどうかで２分しよう。はじめは、達成={}, 未達＝Vとなる。
握手を次のように段階的に実行してみよう。
握手会１）握手数1位のm-2が自分と{m-2,0}以外と握手。達成＝{m-2,0,1}で、m−2は未握手の０と夫婦。
握手会２）握手数2位のm-3が達成者以外と握手。新たに{m-3,2}が達成し、m-3は未握手の1と夫婦。
握手会３) 握手数3位のm-4が達成者以外と握手。新たに{m-4,3}が達成し、m-4は未握手の2と夫婦。
...................................................
握手会n-1) m-n=nが残りと握手。新たに{n, n-1)が達成し、nは未握手のn-2と夫婦となる。
こうして握手会を進めていくと、最初の達成者が3人で、それ以降は毎回2人となる。
全体が偶数人だから、最後に握手会ができない人が残る。
最後の握手会を考えてみると、
握手会ｎ）残りはm-(n+1)=n-1の1人が残る。
n-1もXもn-1回目までの握手会に参加していたが互いに未握手。だから夫婦。
結局、X夫婦は2人ともn-1回の握手をしている。
ここで面白いのは、夫婦の握手数だ。m-2+0=m-3+1=m-4+2=.....=n+1+n-2=n-1+n-1=2n-2と一定になる。
質問：握手が完了したときのグラフをかくコードはどうしたら作れますか。
whileを回して、達成点と未達点のリストを更新して作ってみよう。
[IN]Pythonで作るとこうなります。
#===================================
from matplotlib import pyplot as plt
import networkx as nx
cnt=1
def drawParty(n):
global cnt
B = nx.Graph()
m = 2*n
psum = m-2
V = list(range(m-1)) + ["x"]
Vm = list(range(n-1)) + ["x"]
Vw = sorted(list(range(n-1,m-1)),reverse=True)
B.add_nodes_from(Vm, bipartite=0)
B.add_nodes_from(Vw, bipartite=1)
colorList = ['Green']*n + ['Red']*n #色名は頭文字を大文字にする
print(f"V1は{Vm}と{Vw}の2部グラフ")
R = V
starting = psum
while len(R)>2:
source = starting
partner = psum -source
couple = [source, partner]
print(f"夫婦は{couple}")
R = set(R) - set(couple)
for destination in R:
B.add_edge(source,destination)
starting -=1
print(f"夫婦は{R}")
plt.subplot(1,3,cnt)
pos = nx.bipartite_layout(B, Vm)
nx.draw_networkx(B,pos,node_color=colorList)
print(f"夫婦{R}の握手数は2人とも",B.degree("x"))
cnt +=1
return True
for couples in range(3,6):
drawParty(couples)
#==========================================
[OUT]
V1は[0, 1, 'x']と[4, 3, 2]の2部グラフ
夫婦は[4, 0]
夫婦は[3, 1]
夫婦は{2, 'x'}
夫婦{2, 'x'}の握手数は2人とも 2
V1は[0, 1, 2, 'x']と[6, 5, 4, 3]の2部グラフ
夫婦は[6, 0]
夫婦は[5, 1]
夫婦は[4, 2]
夫婦は{3, 'x'}
夫婦{3, 'x'}の握手数は2人とも 3
V1は[0, 1, 2, 3, 'x']と[8, 7, 6, 5, 4]の2部グラフ
夫婦は[8, 0]
夫婦は[7, 1]
夫婦は[6, 2]
夫婦は[5, 3]
夫婦は{'x', 4}
夫婦{'x', 4}の握手数は2人とも 4
２．安全な川渡し、渡河問題
昔からあるパズルで、
「１人の先頭が船を使って、狼、ヤギ、キャベツを川の向こう岸に渡す。
船頭が１回で運べるのは１種類だけ。
また、狼とヤギのみの状態、ヤギとキャベツのみの状態はつくらない。
どのような手順で狼、ヤギ、キャベツをすべて向こう岸に運ぶことができるか。」
＜記号の状態変化として取り組む＞
まず、記号F,W,G,Cを使って船頭、狼、ヤギ、キャベツとしよう。GC,GWがダメな状態だ。
4つのあるなしは2^4=16通りの状態があるが、４つの物を２つの岸に分割すると考えてみる。
ダメな２通りの状態を取り除いた16-2=14通りを
FのあるものとFのないものに分けると２部グラフになる。
Fあり、Fなし、Fなし、Fありを交互に繰り返すからだ。
FありのFWGCの残りの対岸は∅
FありのFWGの残りの対岸はC
FありのFWCの残りの対岸はG
FありのFGCの残りの対岸はW
FありのFGの残りの対岸はCW
（FありのFW、FCの残りの対岸はそれぞれGC、GWとなるからこの４つの状態は除外する。
Fのみの対岸はWGCとなり無法地帯になるからこれも除外する。）
結局、可能な状態は１４−４＝１０個あり、Fあり５個とFなし５個がきれいに対応する。
しかも、スタートがFWGCでゴールが∅となるように、交互に結ぶ２部グラフを作ろう。
＜挟み打ちで経路の絞り込み＞
状態変化を考えるときはスタートとゴールの両方から挟み打ちすると無駄な調べが減りますね。
・FありのFXYの次はXかYを運ぶので、XかYになります。逆にいうとFXの前はFXYです。
だから、FWGの行き先はWかG、
FWCの行き先はWかC、
FGCの行き先はGかC、
FGの残りはGか∅です。
ただし、FWCだけはGがないので、Fだけ移動するWCを行き先にできますね。
また、FWGCの行き先はFはGを他とセットにしてうつしますから、WCだけです。
・逆にFがなくなったXにFがもどってきてFXになることはできるでしょう。
これら岸からFあり５点とFなし５点の２部グラフのありうる辺を明確にします。
（スタートから考える）
こちら岸の状態はスタートFあり→Fなし→Fあり→Fなし…のくり返しです。
FWGCの次はCWだけ。CWの次はFをつけたFWCだけです。
FWCの次はWかCかWCです。まとめると、FWGC→CW→FWC→W/C/WC。
（終わりから考える）
こちら岸の状態のゴールFなし←Fあり←Fなし←Fあり…のくり返しです。
FXで∅になるのはFGだけでした。だから、∅の前はFGです。
FGの前は∅かGですが、∅をくり返しても仕方ないので、Gですね。
Gの前はFを他をセットでくっつけてFGWかFGCです。FGWならその前はC,FGCならその前はGです。
まとめると、∅←FG←G←FGW←Wか ∅←FG←G←FGC←C
（挟み打ちする）
あとは挟み打ちするだけです。スタートからのW/C/WCとゴールからのWかCがつながります。
FWGC→CW→FWC→W→FGW→G→FG→∅
FWGC→CW→FWC→C→FGC→G→FG→∅
次の図のように、１行目が可能な辺、
２行目左がこの岸の状態変化、右が向こう岸
３行目左がこの岸の状態変化、右が向こう岸。
当たり前ではあるけれど、
部を入れ替えただけなので、左図と右図の矢線の模様が同一になるね。
＜グラフをモデルにして一般化しよう＞
さて、どうだったでしょうか。
記号化することで、状態変化が明確になりました。
質問：意味づけを捨てて、グラフ問題として定式化するにはどうしたらようでしょうか。
Fは船頭なので、これは残しましょう。
運ぶものitemsは頭文字をとってますが、これもabcなどの一般的な名前にして与えましょう。
だめな状態がab,bcならabcだけもだめなので、最初からダメ状態のリストbanを与えましょう。
Fabcのオンオフから状態全体をFabcと∅を含めた文字列の部分集合resとして生成しましょう。
Fabc-こちら岸の状態＝対岸の状態なので、banの補集合と文字入れ替えもbanに加え
ダメ文字列banzを作りましょう。
全体状態resからbanzを引いたものをbaseにします。
baseをFありの状態とFなしの状態の2部に分割します。2部グラフを作る問題になりました。
このbase
2部グラフの辺はスタートがFabcで、ゴールが∅です。
辺はFあり、Fなし、Fあり、Fなしを交互につなぐことで、スタートからゴールにいたるPathを探す
問題に変わります。
グラフのスタートとゴールからpathを探す問題は、HamiltonPathの部分です。
前回やった深さ優先探索DepthFirstSearch,dfsの出番ですね。
すると残る課題は、FなしfとFありnの２つの部を結べる辺をルールからどうやって作るのか
ということだけですね。
nからとった要素をitem, fから取った要素をfitemとします。
fitemの状態の文字列がitemの文字列を含めばFが運び去ったり、Fが運び込んだりした変化になります。
運べるのはF自身かFと１つだけなので、岸にいる数が1回で１か２しか変化しませんね。
これを両方満足するのが条件１（cond1)です。
Fと何か１つだけある状態から何もなくなる状態に変わることは可能です。これが条件２(cond2)
この２条件のどちらかを満足する要素の組み合わせのときだけ、辺をつなぎましょう。
その辺の集合をeListとして、グラフに追加します。
cond1 = (set(item) <= set(fitem)) and (len(fitem)-len(item)<3)
cond2 = item=="" and len(fitem)==2
そうすると、この辺の情報をグラフに登録して、隣接辞書を取得します。
その辞書をグラフデータとしてfind_pathに渡してやり、そのあとdfsの機能で、pathを探すだけです。
#[IN]Python
#================
from matplotlib import pyplot as plt
from itertools import combinations,permutations
import networkx as nx
from collections import defaultdict
#ここからデータ作成
def graphF(f,n):
G = nx.Graph()
G.add_nodes_from(f, bipartite=0)
G.add_nodes_from(n, bipartite=1)
return G
def digraphF(f,n):
G = nx.DiGraph()
G.add_nodes_from(f, bipartite=0)
G.add_nodes_from(n, bipartite=1)
return G
def transF(items,ban):
#F＋文字列itemsの部分集合resを作る。
res=[]
items="F"+items
n=len(items)
for i in range(n+1):
res =res + list(combinations(items,i))
res = [ ''.join(x) for x in res]
#引数の文字列リストbanからダメ状態文字列banzを作る。
bans=[] #補集合追加
zen=set(items)
for bitem in ban:
bans.append(''.join(list(zen-set(bitem))))
bans = bans + ban
banz=[] #順列生成
for items in bans:
banz = banz + [''.join(x) for x in permutations(items)]
#ダメでないグラフの基本となる点リストbaseを作る。
base = list(set(res)-set(banz))
f = list(filter(lambda x:"F" in x , base))
n = list(set(base)-set(f))
G = graphF(f,n)
#妥当な辺リストをeListを作り、それから隣接辞書を得る。
eList=[]
for item in n:
for fitem in f:
cond1 = (set(item) <= set(fitem)) and (len(fitem)-len(item)<3)
cond2 = item=="" and len(fitem)==2
if cond1 or cond2:
eList.append((item,fitem))
G.add_edges_from(eList)
adjacency_dict = nx.to_dict_of_lists(G)
#2部グラフ作成のための２部の頂点を隣接辞書を返す。
return f,n,adjacency_dict
#ここからPathの検索（深さ優先）
def dfs(graph, now_pos, visited, path,prevpath,paths):
prevpath = path
visited[now_pos] = True
path.append(now_pos)
paths.append(path)
for neighbor in graph[now_pos]:
if not visited[neighbor]:
dfs(graph, neighbor, visited, path.copy(), prevpath.copy(),paths)
else:
paths.append(prevpath.copy())
visited[now_pos] = False
path.pop()
return paths
def find_path(graph, start,end):
keys=graph.keys()
visited={}
for item in keys:
visited[item]=False
path = []
prevpath = []
paths = []
res = dfs(graph, start, visited, path, prevpath,paths)
maxlen = max(list(map(lambda x:len(x), res)))
fil= list(filter(lambda x:len(x)==maxlen and x[maxlen-1]=="", res))
return fil
def solveRiver(items, ban):
f,n,adjList = transF(items, ban)
#print(adjList) #ちゃんと動いているかを確認したいときはコメントをはずす。
results = find_path(adjList, "F"+items, "")
cnt=len(results)
num = 0
for result in results:
#print(result)
num +=1
if result:
R = digraphF(f,n)
arrowList=[]
answer = f"こちら岸の変化は、{result[0]}"
for i in range(len(result)-1):
arrowList.append((result[i],result[i+1]))
answer +=f"->{result[i+1]}"
answer +="∅"
print(answer)
R.add_edges_from(arrowList)
colorList = ['red']*len(f) + ['yellow']*len(n) #色名は頭文字を大文字にする
pos = nx.bipartite_layout(R, n)
plt.subplot(1,cnt,num)
nx.draw_networkx(R,pos,node_color=colorList)
else:
print("パスは見つかりませんでした")
#実行開始＝＝＝＝＝＝＝＝＝＝＝＝＝＝
items="wgc" #船頭Fが運ぶべきもの
ban=["gc","gw","gcw"] #船頭がいないときのダメな状態
ans = solveRiver(items,ban)
#=============================
[OUT]
こちら岸の変化は、Fwgc->wc->Fwc->w->Fwg->g->Fg->∅
こちら岸の変化は、Fwgc->wc->Fwc->c->Fgc->g->Fg->∅
＜条件を変えてためしてみよう＞
Q「船頭Fが犬d,猫c、ペットフードpを運ぶ。一度に1つだけ運べます。Fがいないと、dもcもpをたべてしまいます。どんな順番で運びますか？」
A「items="dcp"にして、ban="dc,cp,dcp"にします。」
#実行開始＝＝＝＝＝＝＝＝＝＝＝＝＝＝
items="dcp" #船頭Fが運ぶべきもの
ban=["dp","cp","dcp"] #船頭がいないときのダメな状態
ans = solveRiver(items,ban)
#=============================
[OUT]
こちら岸の変化は、Fdcp->dc->Fdc->c->Fcp->p->Fp->∅
こちら岸の変化は、Fdcp->dc->Fdc->d->Fdp->p->Fp->∅
＜意味づけによる渡河問題解法の一般化＞
渡河問題では、abcを運ぶのに、共存できない2者の組み合わせが２つあります。どうしてダメかは物語としていろいろあります。たてとえば2者の組ab, bc,caのうちのab,acがだめということにしましょう。
すると、aがダメになる原因を作っていることがわかります。次の３ステップで渡せます。
・最初にaだけ運ぶ。もどってきたら残りのa以外（bc）の片方だけ運びます。
・次はaを連れてもどります。bcのうち残りを運ぶことでaが取り残されます。
・最後にFはもどってきたら、取り残されたaを最後に向こう岸に渡します。