【Matlab / Octave】一筆書き

令和3年度 秋期 応用情報技術者試験 午後問題 問3 に出題された「一筆書き」のプログラムを Matlab / Octave で作成した。

問題文

グラフは,有限個の点の集合と,その中の 2 点を結ぶ辺の集合から成る数理モデルである。グラフの点と点の間をつなぐ辺のことを経路という。本問では,任意の 2 点間で,辺をたどることで互いに行き来することができる経路が存在する(以下,強連結という)有向グラフを扱う。強連結な有向グラフの例を図 1 に示す。辺は始点と終点の組で定義する。各辺には 1 から始まる番号が付けられている。

図 1 強連結な有向グラフ

一筆書き

本問では,グラフの全ての辺を 1 回だけ通り,出発点から出て出発点に戻る閉じた経路をもつグラフを,一筆書きができるグラフとする。

一筆書きの経路の求め方

一筆書きの経路を求めるためには,出発点から辺の向きに従って辺を順番にたどり,出発点に戻る経路を見つける探索を行う。たどった経路(以下,探索済の経路という)については,グラフ全体が通過していない辺(以下,未探索の辺という)がない場合は,この経路が一筆書きの経路となる。未探索の辺が残っている場合は,探索済の経路を,未探索の辺が接続する点まで遡り,その点を出発点として,同じ点に戻る経路を見つけて,遡る前までの経路に連結することを繰り返す。

各点を始点とする辺を接続辺という。グラフの各点に対して接続辺の集合が決まり,辺の番号が一番小さい接続辺を最初の接続辺という。同じ始点をもつ接続辺の集合で,辺の番号を小さいものから順番に並べたときに,辺の番号が次に大きい接続辺を次の接続辺ということにする。

図 1 のグラフの各点の接続辺の集合を表 1 に示す。図 1 において,点 b の最初の接続辺は辺 2 である。辺 2 の次の接続辺は辺 5 となる。辺 5 の次の接続辺はない。

接続辺の集合
点 a辺 1
点 b辺 2, 辺 5
点 c辺 3
点 d辺 4,辺 7
点 e辺 6
点 f辺 8
表 1 図 1 のグラフの各点の接続辺の集合

一筆書きの経路の探索において,一つの点に複数の辺がある場合には,最初の接続辺から順にたどることにする。

図 1 のグラフで点 a を出発とした一筆書きの経路の求め方を図 2 に示す。

経路を構成する辺とその順番が,これ以上変わらない場合,確定済の経路という。

図 2 図 1 のグラフで点 a を出発点とした一筆書きの経路の求め方

一筆書きの経路を求める手順

点 a から探索する場合は,点 a の最初の接続辺である辺 1 から始め,辺 1 の終点 b の最初の接続辺である辺 2 をたどり,同様に辺 3,辺 4 をたどる。辺 4 の終点 a からたどれる未探索の辺は存在しないので,これ以上探索が進められない(図 2 [1])。

しかし,未探索の辺 5,辺 6,辺 7,辺 8 が残っているので,未探索の辺が接続する点まで遡る。

終点 a から辺 4 を遡ると,辺 4 の始点 d で未探索の辺 7 が接続している。遡った経路は途中で未探索の辺が存在しないので,これ以上,辺の順番が変わらず,辺 4 は,一筆書きの経路の一部として確定済の経路となる(図 2 [2])。

点 d から同様に辺 7 → 辺 8 → 辺5 → 辺 6 と探索できるので,辺 3 までの経路と連結した新しい探索済の経路ができる(図 2 [3])。

辺 6 の終点からは,辺 6 → 辺 5 → 辺 8 → 辺 7 → 辺 3 → 辺 2 → 辺 1 と出発点の点 a まで遡り,これ以上,未探索の辺がないことが分かるので,全ての辺が確定済の経路になる(図 2 [4])。

一筆書きの経路は,次の 1. ~ 4. の手順で求められる。

  1. 一筆書きの経路の出発点を決める。
  2. 出発点から,未探索の辺が存在する限り,その辺をたどり,たどった経路を探索済の経路に追加する。
  3. 探索済の経路を未探索の辺が接続する点又は一筆書きの経路の出発点まで遡る。遡った経路は,探索済の経路から確定済の経路にする。未探索の辺が接続する点がある場合は,それを新たな出発点として,2. に戻って新たな経路を見つける。
  4. 全ての辺が確定済の経路になった時点で探索が完了して,その確定済の経路が一筆書きの経路になる。

一筆書きの経路を求めるプログラム

一筆書きの経路を求める関数 directedE のプログラムを作成した。

実装に当たって,各点を点 n(n は 1 ~ N)と記す。例えば,図 1 のグラフでは,点 a は点 1,点 b は点 2 と記す。

グラフの探索のために,あらかじめ,グラフの点に対する最初の接続辺の配列 edgefirst 及び接続辺に対する次の接続辺の配列 edgenext を用意しておく。edgenext において,次の接続辺がない場合は,要素に 0 を格納する。

図 1 のグラフの場合の配列 edgefirst,edgenext を図 3 に示す。

図 3 図 1 のグラフの場合の配列 edgefirst, edgenext

edgefirst によって点 2 の最初の接続辺が辺 2 であることが分かり,点 2 から最初にたどる接続辺は辺 2 となる。edgenext によって,辺 2 の次の接続辺が 5 であることが分かるので,点 2 から次にたどる接続辺は辺 5 となる。辺 5 の次の接続点はないので,点 2 からたどる接続辺はこれ以上ないことが分かる。

Matlab / Octave で作成した一筆書きのプログラム

Matlab / Octave で作成した一筆書きのプログラムを示す。

N=6;# グラフの点の個数
M=8;# グラフの辺の個数
start1=[1,2,3,4,2,5,4,6];# 辺 m の始点の番号
end1=[2,3,4,1,5,4,6,2];# 点 m の終点の番号
edgefirst=[1,2,3,4,6,8];# 点 n の最初の接続辺
edgenext=[0,5,0,7,0,0,0,0];# 辺 m の次の接続辺
# 点 n を始点とする未探索の辺の中で最小の番号を格納する。点 n を始点とする未探索の辺がない場合は 0 を格納する。
#current=[];
# 一筆書きの経路を構成する探索済の辺の番号を順番に格納する。(探索済の経路)
#searched=[];
# 一筆書きの経路を構成する確定済の辺の番号を順番に格納する。(確定済の経路)
#path=[];

function directedE(N,M,start1,end1,edgefirst,edgenext)
  for i=1:1:N
    current(1,i)=edgefirst(1,i);
  endfor
  top=1;
  last=M;
  x=1;
  while last >= 1
    if current(1,x) ~=0
      temp=current(1,x);
      searched(1,top)=temp;
      current(x)=edgenext(1,temp);
      x=end1(temp);
      top=top+1;
    else
      top=top-1;
      temp=searched(1,top);
      path(last)=temp;
      x=start1(temp);
      last=last-1;
    endif
  endwhile
  path
endfunction

directedE(N,M,start1,end1,edgefirst,edgenext)

上記のプログラムを実行した結果を示す。

path =

   1   2   3   7   8   5   6   4

参考文献

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です