前回に引き続き、網構造のデータモデリングパターン、今回は無向グラフについてです。

結論からいうと、次のようにすると無向グラフを表せます。

図-1

【辺】と【端点】が1対多の関係にありますが、「多」の側の脇に「2」と書いてあるのは、一つの【辺】に対して【端点】が2つずつ現れる、と言う意味です。1対多の特殊ケースとして1対2を表現しているわけです。IDEF1Xの表記法の説明をしておくと、このように1対多をもうすこし限定的に表現する方法として、次のようなものがあります。

上の例は「ちょうどｍ」で「ｍ＝2」のケースですね。【端点】という概念が分かりにくいと思いますので、実際の例を考えます。典型的には「一筆書き」問題のようなものが無向グラフになります。2つの「もの」の隣接関係も無向グラフです。さらに有向グラフで常に行きと帰りがペアになっているような場合は、無向グラフとして表現することも可能です。実際にはこのようなケースに無向グラフを適用することが多いでしょう。たとえば、鉄道線路は無向グラフですが、列車の運行まで考えると、2本の向きが違う【辺】が常にペアで現れる有向グラフになります。

今回は、関東圏の都・県庁所在地と其れを結ぶ国道（とりあえず複雑になるので2ケタの国道まで）の関係を考えます。

図-2

線の交差を避けるために、位置関係が異なっています（“宇都宮”が“東京”の右下に来たりしています）が、繋がり方の関係はこの図のとおりです。（細かい注釈を付けておくと“国道16号”は“横浜”から出て“さいたま”、“千葉”をとおり“横浜”に帰る環状線ですが、「海の上」を通っているので“千葉－横浜”間は省略しています。）

こういう無向グラフを表現するＥＲ図は上のパターンを次のように読み換えます。

図-3

【頂点】→【都市】
【辺】→【国道】
【端点】→【経由】

【国道】を表現するのに、“国道16号”の“横浜－さいたま”間と“さいたま－千葉”間を区別して考えなければならないので、起点から順に“国道16_1”、“国道16_2”とよぶことにしましょう。（今回は無向グラフの解説をするためにこういう作り方をしていますが、実際は【国道区間】を《国道番号》《区間番号》の複合キーにするような構造にして【国道】は「外に出す」ような設計をすると思います。）国道17号も同じです。“東京”と“横浜”は“国道1号”と“国道15号”の2つで繋がっていますが、こういう場合でもこのパターンできちんと表現できます。

【都市】

【国道】

【経由】

【経由】あるいはもとのパターンの【端点】にどのようにデータが入るかご理解いただけたと思います。【経由】には《国道番号》が2回ずつ現れています。上で述べたように、これは【辺】には【端点】が2つずつあるということに対応しています。

このデータ構造は「使いにくいのではないか」とご心配になる向きもあるかも知れません。使いにくければ実装するときに物理設計で手を入れればよいのですが、このままの構造で、しかもSQLだけでどういうことができるのか、サンプルをお見せしましょう。（以下のサンプルでは、【国道】の一般属性に《距離》を追加してあります。）まずは「となりのとなり」を表示してみます。以下に示すのは MS-Access で生成した SQL です。

SELECT 都市.都市名, 経由.国道番号, 国道.距離, 経由_2.都市名, 経由_3.国道番号, 国道_1.距離, 経由_1.都市名
FROM 都市 INNER JOIN
　　(国道 INNER JOIN
　　　　(
　　　　　　(
　　　　　　　　(
　　　　　　　　　　(経由 INNER JOIN 経由 AS 経由_2 ON 経由.国道番号 = 経由_2.国道番号)
　　　　　　　　　　INNER JOIN 経由 AS 経由_3 ON 経由_2.都市名 = 経由_3.都市名
　　　　　　　　)
　　　　　　　　INNER JOIN 経由 AS 経由_1 ON 経由_3.国道番号 = 経由_1.国道番号 　　　　　　)
　　　　　　INNER JOIN 国道 AS 国道_1 ON 経由_3.国道番号 = 国道_1.国道番号
　　　　) ON 国道.国道番号 = 経由.国道番号
　　) ON 都市.都市名 = 経由.都市名
WHERE(
　　(
　　　　(経由_2.都市名)<>[都市].[都市名]
　　)
　　AND
　　(
　　　　(経由_1.都市名)<>[都市].[都市名] AND (経由_1.都市名)<>[経由_2].[都市名]
　　)
);
この結果、すべての「となりのとなり」の組み合わせを得ることができます。

これを拡張すれば、たかだか7都市しかないわけですから7つの都市をすべて1度ずつ訪れる巡回経路を列挙することもできます。

前橋-(50)-水戸-(51)-千葉-(16)-さいたま-(16)-横浜-( 1)-東京-( 4)-宇都宮
千葉-(51)-水戸-(50)-前橋-(17)-さいたま-(16)-横浜-( 1)-東京-( 4)-宇都宮
前橋-(50)-水戸-(51)-千葉-(16)-さいたま-(16)-横浜-(15)-東京-( 4)-宇都宮
千葉-(51)-水戸-(50)-前橋-(17)-さいたま-(16)-横浜-(15)-東京-( 4)-宇都宮
横浜-(16)-さいたま-(17)-前橋-(50)-水戸-(51)-千葉-(14)-東京-( 4)-宇都宮
宇都宮-( 4)-東京-(14)-千葉-(51)-水戸-(50)-前橋-(17)-さいたま-(16)-横浜
宇都宮-( 4)-東京-( 1)-横浜-(16)-さいたま-(17)-前橋-(50)-水戸-(51)-千葉
宇都宮-( 4)-東京-(15)-横浜-(16)-さいたま-(17)-前橋-(50)-水戸-(51)-千葉
宇都宮-( 4)-東京-( 1)-横浜-(16)-さいたま-(16)-千葉-(51)-水戸-(50)-前橋
宇都宮-( 4)-東京-(15)-横浜-(16)-さいたま-(16)-千葉-(51)-水戸-(50)-前橋

“宇都宮”が袋小路になっているので、「巡回セールスマン問題」のようにぐるっと一周して元に戻ることはできませんが、ここまでくれば「最短経路問題」や「最大木問題」の解まであと一歩のところまで来ていることが分かります。

参考資料

MS-Access で実装した国道モデル　kokudou.mdb(368KB)

ご意見募集

ここまでの内容で質問やコメントがある方は、 編集部までお問い合わせお問い合わせ下さい。
「入門」なのであまり高度な質問にはお答えできませんが、みなさまの役に立ちそうな内容については、この連載の中でとりあげたいと思います。