13,005
回編集
「第1回 グラフ理論の概要と応用」の版間の差分
ナビゲーションに移動
検索に移動
→歩道 道 閉路
| 61行目: | 61行目: | ||
単純グラフ(simple graph)とは、多重辺やループを含まないグラフのことである。<br> | 単純グラフ(simple graph)とは、多重辺やループを含まないグラフのことである。<br> | ||
<br> | <br> | ||
===== 歩道 道 閉路 ===== | ===== 歩道 / 道 (経路) / 小道 / 閉路 / 回路 ===== | ||
歩道(walk) | * 歩道 (walk) | ||
例 : | *: ある点から別の点への行き方のことである。(連結した辺の列) | ||
*: 例 : 下図のグラフにおいて、P→Q→Rは長さ2の歩道で、P→S→Q→T→S→Rは長さ5の歩道である。 | |||
*: <br> | |||
* 道 (path) | |||
*: どの<u>点</u>も高々一度しか現れない歩道のことである。 | |||
*: 例 : 下図のグラフにおいて、P→T→S→Rは道である。 | |||
*: <br> | |||
* 小道 | |||
*: どの<u>辺</u>も高々一度しか現れない歩道のことである。 | |||
*: <br> | |||
* 閉路 (cycle) | |||
*: 全ての<u>点</u>が異なるQ→S→T→Qのような形をした道のことである。(元の点に戻ってくる道) | |||
*: <br> | |||
* 回路 (circuit) | |||
*: 全ての<u>辺</u>が異なるQ→S→T→Qのような形をした小道のことである。(元の点に戻ってくる小道) | |||
<br> | <br> | ||
[[ファイル:Graph Theory 1 3.jpg|フレームなし|中央]] | [[ファイル:Graph Theory 1 3.jpg|フレームなし|中央]] | ||
<br> | <br> | ||
===== 特別な性質を持った歩道を含むグラフ ===== | ===== 特別な性質を持った歩道を含むグラフ ===== | ||
オイラーグラフ(Eulerian graph)とは、全ての辺を1回ずつ通って元の点に戻る歩道を含むグラフのことである。<br> | オイラーグラフ(Eulerian graph)とは、全ての辺を1回ずつ通って元の点に戻る歩道を含むグラフのことである。<br> | ||