{ "cells": [ { "cell_type": "markdown", "id": "4ab86ac1", "metadata": {}, "source": [ "# 『なには八ツ橋智恵の渡り』で橋渡り('24.06.05)\n", "\n", "和算書籍の眞元算法(1845年)に『浪華二十八橋智慧渡』という問題が載っている。\n", "それは、1736年にオイラーが題材とした「ケーニヒスベルクの橋の問題」問題の亜種だ。\n", "つまり、ケーニヒスベルクにある7つの橋を「ひとつの橋を2度通ることなく、全ての橋を渡って、元の場所に帰ってくることができるか？」という問題の変形バージョンである。\n", "オイラーが橋渡り問題を扱った百年後に出された『浪華二十八橋智慧渡』は、オリジナルの問題とは異なる趣向が含まれている。\n", "あるいは、オリジナルの問題の本質を外したことで、別のパズル問題となっているようだ。\n", "\n", "%\n", "\n", "```{figure} ./images/day_240604_yatsuhashi_original.png\n", "---\n", "height: 10cm\n", "---\n", "オイラーの「ケーニヒスベルクの橋の問題」論文\n", "```\n", "\n", "今回は、『浪華二十八橋智慧渡』を解くための準備をしてみようと思う。\n", "その題材として使うのは、『浪華二十八橋智慧渡』の簡易版たる[『なには八ツ橋智恵の渡り』](https://www.osakamushis.jp/news/2009/tenjigae/0908222.html)である。\n", "これは、『浪華二十八橋智慧渡』が扱ったあたりを舞台に、橋の数を8つに減らした単純バージョンだ。\n", "\n", "%\n", "\n", "```{figure} ./images/day_240604_yatsuhashi.jpg\n", "---\n", "height: 12cm\n", "---\n", "『なには八ツ橋智恵の渡り』\n", "```" ] }, { "cell_type": "markdown", "id": "89550c75", "metadata": {}, "source": [ "## 『なには八ツ橋智恵の渡り』をグラフにしてみる\n", "\n", "まずは、『なには八ツ橋智恵の渡り』をグラフ構造にしてみよう。\n", "後で実際の地名を使うことにして、とりあえずは仮地名でデータを作ってみる。" ] }, { "cell_type": "code", "execution_count": 30, "id": "6db0aff5", "metadata": { "tags": [ "hide-output", "hide-input" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "島の数 5\n", "橋の数 9\n" ] } ], "source": [ "import numpy as np\n", "import networkx as nx\n", "\n", "# c.f. https://medium.com/@victorialandaberry/solving-the-konigsberg-bridge-problem-with-python-914f9f51bb8e\n", "g = nx.MultiGraph() #create an empto Multigraph named G\n", "#add nodes one by one \n", "g.add_node(\"難波A\")\n", "g.add_node(\"難波B\")\n", "g.add_node(\"難波C\")\n", "g.add_node(\"難波D\")\n", "g.add_node(\"難波E\")\n", "#add edges\n", "g.add_edge(\"難波A\", \"難波B\")\n", "g.add_edge(\"難波B\", \"難波C\")\n", "g.add_edge(\"難波C\", \"難波E\")\n", "g.add_edge(\"難波A\", \"難波D\")\n", "g.add_edge(\"難波A\", \"難波D\")\n", "g.add_edge(\"難波B\", \"難波D\")\n", "g.add_edge(\"難波B\", \"難波D\")\n", "g.add_edge(\"難波D\", \"難波E\")\n", "g.add_edge(\"難波C\", \"難波D\")\n", "\n", "print(\"島の数\", g.number_of_nodes())\n", "print(\"橋の数\", g.number_of_edges())" ] }, { "cell_type": "markdown", "id": "0368127d", "metadata": {}, "source": [ "作成した『なには八ツ橋智恵の渡り』のグラフ構造を描画してみよう。" ] }, { "cell_type": "code", "execution_count": 26, "id": "6d764bbc", "metadata": { "tags": [ "hide-input" ] }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "難波A\n", "\n", "難波A\n", "\n", "\n", "\n", "難波B\n", "\n", "難波B\n", "\n", "\n", "\n", "難波A--難波B\n", "\n", "\n", "\n", "\n", "難波D\n", "\n", "難波D\n", "\n", "\n", "\n", "難波A--難波D\n", "\n", "\n", "\n", "\n", "難波A--難波D\n", "\n", "\n", "\n", "\n", "難波B--難波D\n", "\n", "\n", "\n", "\n", "難波B--難波D\n", "\n", "\n", "\n", "\n", "難波C\n", "\n", "難波C\n", "\n", "\n", "\n", "難波B--難波C\n", "\n", "\n", "\n", "\n", "難波E\n", "\n", "難波E\n", "\n", "\n", "\n", "難波D--難波E\n", "\n", "\n", "\n", "\n", "難波C--難波D\n", "\n", "\n", "\n", "\n", "難波C--難波E\n", "\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "from IPython.core.display import SVG, display\n", "\n", "def draw(graph):\n", " svg = nx.nx_agraph.to_agraph(graph).draw(prog='dot',format='svg')\n", " display(SVG(svg))\n", "\n", "draw(g)" ] }, { "cell_type": "markdown", "id": "701e533a", "metadata": {}, "source": [ "そして、オイラーが1736年に考えた「一筆書きで元の場所に戻れるか」を判定法を、『なには八ツ橋智恵の渡り』に適用させてみると、答えはこうなる。\n", "つまり、オリジナルの「ケーニヒスベルクの橋の問題」と同じ結果が得られる。" ] }, { "cell_type": "code", "execution_count": 24, "id": "169d72d3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "一筆書き経路で元の場所に戻ることはできません。\n" ] } ], "source": [ "def eulerpath(graph):\n", " odd=0\n", " a=list(graph.degree(graph.nodes()))\n", " for i in a:\n", " if (i[1] % 2) != 0:\n", " odd+=1\n", " if odd>0:\n", " print(\"一筆書き経路で元の場所に戻ることはできません。\")\n", " else:\n", " print(\"一筆書き経路で元の場所に戻ることができます。\")\n", "\n", "eulerpath(g)" ] }, { "cell_type": "markdown", "id": "5c0ffdc7", "metadata": {}, "source": [ "## ハシを渡りさえしばければワキの町を通り抜けても良い？の謎\n", "\n", "『なには八ツ橋智恵の渡り』には妙な解説文がある。\n", "それは「ハシを渡りさえしばければワキの町を通り抜けても良い」「工夫をすれば渡ることも簡単だ」という一節だ。\n", "この謎について、また眞元算法(1845年)で出題された『浪華二十八橋智慧渡』についても、関連する文章を参考にして、史実や真実の答えに辿り着いてみたいと思う。\n", "\n", "%\n", "\n", "```{figure} ./images/day_240604_yatsuhashi_IMG_3321B40D720A-1.jpeg\n", "---\n", "height: 10cm\n", "---\n", "『なには八ツ橋智恵の渡り』\n", "```\n" ] }, { "cell_type": "code", "execution_count": null, "id": "67bcf451", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "celltoolbar": "Tags", "kernelspec": { "display_name": "jupyter-book-py311", "language": "python", "name": "jupyter-book-py311" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.11.9" }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": false, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": false, "toc_position": {}, "toc_section_display": true, "toc_window_display": false } }, "nbformat": 4, "nbformat_minor": 5 }