📢 Webサイト閉鎖と移転のお知らせ
このWebサイトは2026年9月に閉鎖いたします。
新しい記事は移転先で追加しております。（旧サイトでは記事を追加しておりません）
| (同じ利用者による、間の2版が非表示) | |||
| 46行目: | 46行目: | ||
<br> | <br> | ||
点の次数(degree)とは、その点を端点とする辺の本数のことである。下図において、点Qの次数は4である。<br> | 点の次数(degree)とは、その点を端点とする辺の本数のことである。下図において、点Qの次数は4である。<br> | ||
[[ファイル:Graph Theory 1 1.jpg|フレームなし|中央]] | |||
<br> | <br> | ||
グラフとは点の集合とそれらの結び方の表現である。<br> | グラフとは点の集合とそれらの結び方の表現である。<br> | ||
| 53行目: | 54行目: | ||
以下の性質を満たすとき、2つのグラフは同形(あるいは同型)であると言う。<br> | 以下の性質を満たすとき、2つのグラフは同形(あるいは同型)であると言う。<br> | ||
片方のグラフで2つの点が結ばれる。 ⇔ 他方のグラフの対応している2点が結ばれる。<br> | 片方のグラフで2つの点が結ばれる。 ⇔ 他方のグラフの対応している2点が結ばれる。<br> | ||
[[ファイル:Graph Theory 1 2.jpg|フレームなし|中央]] | |||
<br> | <br> | ||
===== 多重辺 ループ 単純グラフ ===== | ===== 多重辺 ループ 単純グラフ ===== | ||
| 59行目: | 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|フレームなし|中央]] | |||
<br> | <br> | ||
===== 特別な性質を持った歩道を含むグラフ ===== | ===== 特別な性質を持った歩道を含むグラフ ===== | ||
オイラーグラフ(Eulerian graph)とは、全ての辺を1回ずつ通って元の点に戻る歩道を含むグラフのことである。<br> | オイラーグラフ(Eulerian graph)とは、全ての辺を1回ずつ通って元の点に戻る歩道を含むグラフのことである。<br> | ||