Maxima を 用いたグ ラ フ 理論の教育
2011SE262 龍 裕真
指導教員：小藤俊幸

1

はじ めに
私は Maxima をゼミの講義内で知り, グラフ理論の分野

ン (追加指示) を表している. 単に,draw_graph(g1) とすると, 頂点の id が表示されない.

私が将来的に数学の教員を目指しているという事もあり,(%i1) load(graphs)$(%i2) g1:create_graph([1,2,3],[[1,2],[2,3],[3,1]]);
(%o2)
GRAPH
(%i3) draw_graph(g1,show_id=true)$

グラフ理論の教育に有効的な Maxima をさまざまな問題

上記のプログラムを実行すると三角形が出来る.に長けていることを知った。しかし、中学校・高校の数学教育でグラフ理論を直接的に生徒が学習する事は少ない.に用いて生徒が学習できないかと思い, 生徒への指導方法を考察してみた.

オイラー路は, グラフのすべての線をちょうど１回ずつ通る経路のことであるが, それに対して, グラフのすべての2Maxima と はMaxima は 1960 年代の MIT の Project MAC で開発された MACSYMA（MAC’s SYmbolic MAnipulation system) の DOE（エネルギー省）版を Texas 大学の Schelter氏が「Common Lisp:The language 第 1 版」(cltl1 と略記) に対応した GCL に移植したものであり、当初は Schelter 氏が Maxima の開発と管理を行っていたが,Schelter氏の死後はメイリングリストを中心に Maxima の保守・管理と開発が進められている. このソフトウェアは, 数式処理ソフトウェアと呼ばれ、, 種の市販のソフトウェアには,Mathematica や Mapple などがある. これらとの大きな違いは, 表計算ソフトウェアは, 数値計算を主目的としてやっているため, 常に数値近似であることに対して,Maxima は数学的にも厳密な計算を主目的としていることが挙げられる. 市販されている他の数式処理ソフトウェアに比べ, ユーザも少なく, アップデートなども自分でチェックしなくてはいけない不便さもあるが, 何より高額な代金を支払う必要がなく, 無料であり, 数式処理ソフトウェアとしては他のものに引けを取らない.[3]点をちょうど１回ずつ通る経路のことをハミルトン路という. ハミルトン路で, 始点と終点が一致するものをハミルトン閉路という.[1](%i3) hp:hamilton_path(g1);(%i3) hp:hamilton_cycle(g1);
上記のコマンドは g1 にハミルトン路または, ハミルトン閉路が存在するかどうかを判定するものである.

4

時間割問題
問,『ある高校で数学の６つの科目の試験が行われるとする. 科目名とその科目を担当する先生は下記の表のようになっている. 毎日１科目ずつ試験を行い, 翌日には採点した答案を返却することになっている. そのため, 先生にとっては担当する科目が２日続くと採点が大変である. そこで, 担当する科目が連続しないように試験日程を組むにはどうしたらよいだろうか.』[1]
生徒に, まず科目が点で置き換えられて表され, 点と点を線で結ぶことが出来ればグラフとなることを教える. そして, それがこの問題で求めたい試験日程だと教える. そこ

3

グラ フ の生成と 表示

Maxima は Linux の入力画面で Maxima と入力すると立ち上がる. グラフに関する機能を利用するためには, パッケージ graphs をロードしなければならない. graphs は,無向グラフを基本としている. 頂点を整数で表し (0 や負の整数を使ってもよい), 頂点を表す整数を頂点の id と呼ぶ.
辺 (向きのない辺) を [i, j](i, j は頂点の id) の形に表し, 頂点のリストと辺のリスト (ともに, 要素の列を角括弧 [ ] でくくる) でグラフを生成する. Maxima は, ユーザの入力する入力文に対して, 出力文を出力する形 (対話形式) で実行される. 入力文には, 最後に必ず ;(セミコロン) か (ドルマーク) の一方 (だけ) を付ける. を付けると, 出力文が表示されない. また,(の入力文は,g1 に creat を代入するという意味になる. (は,「頂点の id を表示する」というオプショ

で, 点と点はどのような関係性でむすばれているかを生徒自身に考えさせる.
考えさせた後, 生徒に科目の担当者が重なっていない場合に限り, その科目つまり点の間を線で結ぶ事が出来ると伝える.
表1 表
科目

先生

１数学 Ia,bba,ccba

２数学 A
３数学 II
４数学 B
５数学 III
６数学 C

『解法』

ンクという.[2]問題文の表からから点と点の関係は, 担当者が重なる事がないように Maxima に打ち込ませる. その後に, 問題と問,『下記のネットワーク図における最大流を求めよ.』

して聞かれているハミルトン路が存在するかどうかを判定

この問題においては出発地点が １ で目標到達地点がするコマンド

４ である. つまり, この問題は １ の地点から ４ の(%i3) hp:hamilton_path(g1);

地点で一度に送ることの出来る最大値はいくつなのかと読を入力させる. さらに, 頂点が表示されないと科目との関み換える事が出来る.

連性がなくなってしまうため頂点表示コマンドも入力させる.

11se262@localhost:~$ maxima(%i1) load(graphs)$(%i2) g1:create_graph([1,2,3,4,5,6],[[1,4],[2,3],[2,4],[2,6],[3,5],[4,5],[4,6],[5,6]]);
(%o2)
GRAPH
(%i3) hp:hamilton_path(g1);(%o3)[1, 4, 2, 3, 5, 6](%i4) draw_graph(g1,show_edges=vertices_to_path(hp),show_id=true)$

図1

Maxima は無向グラフを基本としているが, このネット
ワーク図は有向なのでそれに従いコマンドを入力する.

Maxima を用いて完成したグラフがハミルトン路になっ

11se262@localhost:~$ maxima(%i1) load(graphs)$(%i2) net:create_graph([1,2,3,4],[[[1,2],4],[[1,3],1],[[2,3],1],[[2,4],1],[[3,4],3]],directed);(%o2)
DIGRAPH(%i3) max_flow(net,1,4);(%o3) [3, [[[1, 2], 2], [[1, 3], 1], [[2, 3], 1],[[2, 4], 1], [[3, 4], 2]]]ている事を視覚的に確認させる. そのグラフにおいてハミルトン路を見つける事が出来れば, それが求めたい試験日(%i3) max_flow(net,1,4);程であると教える.のコマンドはさまざまな点の結び方があるが, 出た答えは複数ある答えの中の１つであることを確認させる. 最後に点に置き換えた科目を戻すと問題の答えの１つとなる試験日程が得ら１の地点から４の地点までの最大流を求めよという意味である.

6

おわり にれていると学習する.

本論では生徒が,Maxima を用いてグラフ理論を活用でこの問題の場合,きる問題を学習出来ないかと考察してみた. Maxima を用

数学 I ー数学 B ー数学 A ー数学 II ー数学 III ー数学 C

いる学習は応用的な内容になるため, 実際に学校現場で使という試験日程が得られる.

用する際は, 学習意欲がある生徒や, 理解度の高い生徒に対して使用する事が適切であると感じた. また、その問題に5最大流問題生徒に最大流問題とは何か説明する. 最大流問題とは, 最対しより興味を持ち, 視覚的理解を得やすい考え方としてMaxima を用いる事を授業内で生徒に紹介する事が最適だと思った.

大の流量を求める問題である.
例えば, 登山である地点から他の地点に物資を送るとする. このとき, いくつかの地点を経由し, 分岐や合流をしながら物資が送られるとする. 送られる過程で, それぞれの地点からそれぞれの地点に一度に送ることのできる量の最大

参考文献[1] 小林みどり：『文科系の応用数学入門』．牧野書店，東京，2014.

値が決まっている際, 全体で一度に送れる量の最大値はい[2] http://dic.nicovideo.jp/a/最大流問題

くらなのか. これを考えるのが最大流問題である. 最大流問

[3] http://www.eonet.ne.jp/ kyo-ju/maxima.pdf

題では, 送られる量をフロー, 出発点をソース, 終着点をシ