Ctrl+K

『なにわ十六橋智恵の渡り』には「オイラー閉路」が存在する。('24.06.06)

『なにわ十六橋智恵の渡り』には「オイラー閉路」が存在する。('24.06.06)#

「保古帖」（甲雑-58）巻19収録の「なにわ十六橋智恵の渡り」#

昨日は、『なには八ツ橋智恵の渡り』を、単純な「ケーニヒスベルグの橋の問題」として解いてみた。 つまり、「すべての橋を1度だけ渡り、同じ場所に戻ってくることができるか」という、ケーニヒスベルグの橋の問題として解いてみた。

「保古帖」（甲雑-58）巻19には、「なにわ十六橋智恵の渡り」という、同様の問題が収録されている。 そこで、今日は、「なにわ十六橋智恵の渡り」を、やはり単純な※ケーニヒスベルグの橋の問題として解いてみようと思う。

※「単純な」という言葉の意味については、後述しようと思う。

_images/day_240606_graphx_naniwa_16.jpeg

図 26 「なにわ十六橋智恵の渡り」#

「なにわ十六橋智恵の渡り」は一筆書き可能#

「なにわ十六橋智恵の渡り」は、少し見づらいのだけれど、題目通りに16の橋がある。 一見すると、14橋しかないように見えるが、島内部にある橋がひとつ、折り目に重なる橋がひとつあり、合計で16の橋がある。 そして、橋で繋がれた島は、合計7つある。 島内部にある橋は、「ケーニヒスベルグの橋の問題」としては存在を無視して良い。 したがって、「なにわ十六橋智恵の渡り」はこういう問題だ。 「7つの頂点間を結ぶ15の辺を、ちょうど1度だけ通るオイラー閉路が存在するか？」

まずは、「なにわ十六橋智恵の渡り」を表現する、グラフ構造を作ってみよう。 下記では、同一頂点に戻る一辺を含む「7つの頂点間を結ぶ16の辺」を作っているが、「ケーニヒスベルグの橋の問題」としては、「7つの頂点間を結ぶ15の辺」と扱っても構わない。

Hide code cell source 
import numpy as np
import networkx as nx

# c.f. https://medium.com/@victorialandaberry/solving-the-konigsberg-bridge-problem-with-python-914f9f51bb8e
g = nx.MultiGraph() #create an empto Multigraph named G
#add nodes one by one 
g.add_node("難波A")
g.add_node("難波B")
g.add_node("難波C")
g.add_node("難波D")
g.add_node("難波E")
g.add_node("難波F")
g.add_node("難波G")
#add edges
g.add_edge("難波A", "難波B")
g.add_edge("難波A", "難波B")
g.add_edge("難波A", "難波D")
g.add_edge("難波A", "難波D")
g.add_edge("難波B", "難波C")
g.add_edge("難波B", "難波F")
g.add_edge("難波B", "難波B")
g.add_edge("難波C", "難波G")
g.add_edge("難波D", "難波E")
g.add_edge("難波D", "難波F")
g.add_edge("難波D", "難波F")
g.add_edge("難波D", "難波F")
g.add_edge("難波E", "難波F")
g.add_edge("難波F", "難波G")
g.add_edge("難波F", "難波G")
g.add_edge("難波F", "難波G")

print("島の数",  g.number_of_nodes())
print("橋の数", g.number_of_edges())

from IPython.display import display,SVG

def draw(graph):
    svg = nx.nx_agraph.to_agraph(graph).draw(prog='dot',format='svg')
    display(SVG(svg))

draw(g)

島の数 7
橋の数 16
_images/3d360137189cacd24d4044c468c875b6a54fa0147987ffcf623602bc93b95e93.svg
_images/day_240606_graphx_naniwa_graph.png

図 27 「なにわ十六橋智恵の渡り」のグラフ構造#

そして、オイラー閉路が存在するかどうかを判定する、昨日書いたコードを実行してみる。 すると、「一筆書き経路で元の場所に戻ることができます」という結果が得られる。 つまり、すべての島＝頂点に繋がる橋＝辺は偶数なので、「なにわ十六橋智恵の渡り」には「オイラー閉路が存在する」というのが答えだ。

Hide code cell source 
def eulerpath(graph):
    odd=0
    a=list(graph.degree(graph.nodes()))
    for i in a:
        if (i[1] % 2) != 0:
            odd+=1
    if odd>0:
        print("一筆書き経路で元の場所に戻ることはできません。")
    else:
        print("一筆書き経路で元の場所に戻ることができます。")

eulerpath(g)

一筆書き経路で元の場所に戻ることができます。

一筆書き経路（オイラー閉路）を計算してみる。#

一筆書き経路（オイラー閉路）が存在するとわかれば、その経路を計算するのは簡単だ。 島や橋の数が多ければ計算時間は掛かるけれど、今回の「なにわ十六橋智恵の渡り」くらいの計算量であれば、一瞬で経路例を作り出すことができる。

Hide code cell source 
for (u,v) in list(nx.eulerian_circuit(g)):
    print(u,'から',v,'に渡る。')

難波A から 難波D に渡る。
難波D から 難波F に渡る。
難波F から 難波G に渡る。
難波G から 難波F に渡る。
難波F から 難波D に渡る。
難波D から 難波F に渡る。
難波F から 難波G に渡る。
難波G から 難波C に渡る。
難波C から 難波B に渡る。
難波B から 難波B に渡る。
難波B から 難波F に渡る。
難波F から 難波E に渡る。
難波E から 難波D に渡る。
難波D から 難波A に渡る。
難波A から 難波B に渡る。
難波B から 難波A に渡る。

「なにわ十六橋智恵の渡り」の舞台「中之島」あたりを眺めてみる#

「ケーニヒスベルグの橋の問題」が、現実の町に存在する島や橋を題材にしたように、大阪を舞台とした「ケーニヒスベルグの橋の問題」も、実際の町を踏まえた観光計算問題だ。 ちなみに、「なにわ十六橋智恵の渡り」の舞台は中之島あたりである。 東西南北の方向は異なるが、現在の地図を貼り付けてみると、下のような具合だ。

_images/day_240606_graphx_naniwa_.png

図 28 「なにわ十六橋智恵の渡り」の舞台となった場所（現在）#

和算の「橋渡り問題」はまだ続く#

『浪華二十八橋智慧渡』や『なには八ツ橋智恵の渡り』あるいは『なにわ十六橋智恵の渡り』といった具合で、和算書物などに登場する「大阪、水の都での橋渡り問題」は多い。 古地図と和算の出題図を眺めながら、大阪の町を歩いてみるのも面白いかもしれない。

目次