@sada1110 先生からのご下問に答えてみるシリーズ第二回。
いくつかの用語の定義
エッジ
直感的には移動経路。適当に始点と終点があって、経路そのものに名前（アルファベット1文字）が付されている。自動車での移動を前提としているが、場合によっては徒歩等での移動もありえる。ただし、移動経路として道路以外の場所を認めるかどうかは悩ましい。 数学的には、一筆書き可能な図形。適当に「書き始めの点」と「書き終わりの点」があって、図形に名前（アルファベット1文字）が付されている。「書き始めの点」と「書き終わりの点」は同一点の場合もあるが、別々の点の場合もある。図形は、二次元多様体上にあるものとする。従って、これは、線分（一次元多様体） ［0,1］ の二次元多様体へのはめ込みである。エッジの表記
直感的には、「始点をＰ，終点をＱとするようなエッジａを ａ：［Ｐ，Ｑ］ で表すこととする。［Ｐ，Ｑ］は省略可能である（始点、終点が分かっているのであれば）。 上記表記は、数学的にも valid である。エッジ集合
直感的には、移動経路をいくつか集めた集合。 数学的には、エッジ全体の集合Ａの任意の部分集合。 エッジ集合は、｛a, b, c, ･･･ ,m, n ｝のように、普通の集合と同じ表記で表現できる。エッジ集合族
直感的には、エッジ集合を要素に持つような集合。 数学的には、エッジ全体の集合Ａの部分集合からなる集合族。わざわざ「集合族」を設けるのは、考慮対象とするエッジ集合を選択する（絞り込む）ためである。エッジの接続
直感的には、終点Ｑを持つエッジに対して、始点Ｑを持つようなエッジを「継ぎ足す」ことができる。a:[P,Q] + b:[Q,R] を （a+b）:[P,R] と書くことは可能である。 数学的には、(a+b) も一筆書き可能な図形である。 (a+b) が定義されるようなエッジを「接続可能」と呼ぶ。より正確には、「エッジ a には、右から（後ろから）エッジ b が接続可能である」あるいは「エッジ b には、左から（前から）エッジ a が接続可能である」と呼ぶ。エッジの分割
直感的には、あるエッジａ：［Ｐ，Ｑ］に対して、移動経路の途中に一点Ｓを設けて、新しい２本のエッジ a1：［Ｐ，Ｓ］と a2：［Ｓ，Ｑ］を考えることができる。ここで (a1＋a2）がもとのａであることに注意。この２本のエッジを、「エッジａの点Ｓにおける分割」と呼ぶ。 数学的には、(a+b) も一筆書き可能な図形である。
ａ：［Ｐ，Ｐ］で、「Ｐ点に留まる」を表現できる。
このとき、ａをどのように分割しても ｂ：［Ｐ，Ｐ］しか得られない場合（本当に動いていない場合）と、分割の仕方によっては ｃ：［Ｐ，Ｑ］が得られる場合（動き回って元の所に戻ってくる場合）の２通りが考えられる。
エッジ上の動作
直感的には、あるエッジａ：［Ｐ，Ｑ］に対して、移動経路上で特定の動作 λ を行うように指示することができる。たとえば「東京から大阪までのエッジで、途中ずっと歌をうたう」とかである。 数学的には、ａ：［Ｐ，Ｑ；λ］と書くことにする。λ = NULL の場合は「何もしない」である。ａ：［Ｐ，Ｑ；null］はａ：［Ｐ，Ｑ］と省略して書くことができるものとする。
ａが ｂ＋ｃ＋ｄ に分割可能である時、ｃのみで動作を指示させることもできる。ａ：［Ｐ．Ｑ］に対して、ｂ：［Ｐ，Ｓ；null］，ｃ：［Ｓ，Ｓ；λ］，ｄ：［Ｓ，Ｑ；null］ が接続されたものと仮定すれば、このエッジａでは、途中の点Ｓのみにおいて動作λを行わせることになる。「車で移動するが、途中１回だけトイレ休憩が挟まれる」などの記述に向いている。
エッジ集合族に課せられる制約条件
以下の条件を課すかどうかは、クライアントである @sada1110 先生のお考えによる。
- 同値関係 ≡（本当は、３本線の一番上は波線にしたかった）
- 始点と終点が同じ場合に同値であるとみなすか、始点と終点が同じであって途中の移動経路も全て同じである場合に同値であると見なすか、２通りの考え方がある。
- 数学的には、第一の場合はホモトープに近い。第二の場合は合同である。厳密な議論においては合同であることを求めると予想されるが、経路探索においてはホモトープな図形であれば良いとする場合もあるだろう。
- たとえば、ａ：［Ｐ，Ｑ］，ｂ：［Ｑ，Ｐ］において、（ａ＋ｂ）は「動かない」のか、「動き回るが元の位置に戻ってくる」のか、という区別ができる。
- エッジ集合における接続可能性
- どんなエッジ集合でも考慮対象とする、という立場が考えられる
- エッジを上手に並び替えれば、全てのエッジが接続可能となる、という立場が考えられる。
- エッジを並び替えなくても、登場順に全てのエッジが接続可能となる、という立場が考えられる。
- 後になるほど条件は厳しくなる。おそらく２番目の条件が現実的である可能性が高い気がする。
（当然）続く・・・・
