OKI Miyuki
blade****@ybb*****
2003年 2月 18日 (火) 01:30:01 JST
oki です。
> > ありゃ、おおぼけかましちゃった？
> > つう事は、閉路（循環している部分）の事を指してたですか？
>
> 僕が訳した所に出てきたのは"tree edge" "non-tree edge"という表現で、
> （幅優先探索などで）ある木が定まったとき、「その木に含まれる辺」、「その木
に
> 含まれない辺」という事のようです。
> ＃実際に使って実行結果を見た限りでは。
>
> "non-tree"の所だけ緑にしたので混乱させてしまったかも。すいません。
>
> 定訳が無いなら、長いですが、「木に含まれる辺」、「木に含まれない辺」にしま
> しょうか。
いやー混乱したのではなくて、いつも自爆です(^_^;。
それで、breadth_first_search のソースを追ってみたんですが、
各頂点を最初は白色にして始点の役目が終えたら黒色、
一度通過すると灰色としてて、non_tree_edge は、灰色か黒色の
事を指すようなので、笠原さん指摘のように、循環（Cycle） な
部分の事みたいです。
> > の日本語訳では、後退弧/交差弧/先行弧となっていますし、
> > とりあえずこれで良い気がします。
> > (もっとも、その本では edge のことを arc と呼んでいるので、
> > この場合は、後退辺/交差辺/先行辺、でしょうか。)
>
> では、「後退辺」「交差辺」「先行辺」で行きますか？
そうですね（厳密な意味が、まだ、わからないけど）。
predecessor 先行頂点
successor 後続頂点
というのは、見た事があったんですが、辺に対しての修飾って
どうもまだ、ピンと来ない感じがあります。
弱連結になるような反対向きの辺
強連結になるような正方向の辺
これらの組を 後退辺・先行辺と呼ぶのか、
単に先行頂点のある辺と、後続頂点のある辺の組を
先行辺・後退辺と呼ぶのか、全然違う意味なのか…？
循環している閉路同士、あるいは
閉路と木の交差する場所が交差辺なのか、単に
複数に分岐しているのが交差辺なのか…？