「第1回グラフ理論の概要と応用」の版間の差分

📢 Webサイト閉鎖と移転のお知らせ

このWebサイトは2026年9月に閉鎖いたします。

移転先はhttps://mochiu.net/index.php?title=第1回グラフ理論の概要と応用です。

新しい記事は移転先で追加しております。（旧サイトでは記事を追加しておりません）

ビジュアルウィキテキスト

@@ 46行目: / 46行目: @@
 <br>
 点の次数(degree)とは、その点を端点とする辺の本数のことである。下図において、点Qの次数は4である。<br>
+[[ファイル:Graph Theory 1 1.jpg|フレームなし|中央]]
 <br>
 グラフとは点の集合とそれらの結び方の表現である。<br>
@@ 53行目: / 54行目: @@
 以下の性質を満たすとき、2つのグラフは同形(あるいは同型)であると言う。<br>
 片方のグラフで2つの点が結ばれる。 ⇔ 他方のグラフの対応している2点が結ばれる。<br>
+[[ファイル:Graph Theory 1 2.jpg|フレームなし|中央]]
 <br>
 ===== 多重辺 ループ 単純グラフ =====
@@ 59行目: / 61行目: @@
 単純グラフ(simple graph)とは、多重辺やループを含まないグラフのことである。<br>
 <br>
-===== 歩道 道 閉路 =====
+===== 歩道 / 道 (経路) / 小道 / 閉路 / 回路 =====
-歩道(walk)とは、ある点から別の点への行き方のことである。(連結した辺の列)<br>
+* 歩道 (walk)
-例 : 下図のグラフにおいて、P→Q→Rは長さ2の歩道で、P→S→Q→T→S→Rは長さ5の歩道である。<br>
+*: ある点から別の点への行き方のことである。(連結した辺の列)
+*: 例 : 下図のグラフにおいて、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>
-道(path)とは、どの点も高々一度しか現れない歩道のことである。<br>
+[[ファイル:Graph Theory 1 3.jpg|フレームなし|中央]]
-例 : 下図のグラフにおいて、P→T→S→Rは道である。<br>
-<br>
-閉路(cycle)とは、Q→S→T→Qのような形をした道のことである。(元の点に戻ってくる道)<br>
 <br>
 ===== 特別な性質を持った歩道を含むグラフ =====
 オイラーグラフ(Eulerian graph)とは、全ての辺を1回ずつ通って元の点に戻る歩道を含むグラフのことである。<br>
@@ 165行目: / 179行目: @@
 *: 安定的マッチングとは、離婚する可能性の低いペアの集まりのことである。
 *: 現実的な応用が多数存在する問題で、医師臨床研修マッチング制度などがある。
+<br>
+===== インターネット関連グラフ問題 =====
+コンピュータを点とし、コンピュータ間の回線を辺で表すとインターネットのグラフができる。<br>
+このグラフの構造を調べることでインターネット上の様々な事象を解明しようとする研究がある。<br>
+<br>
+例<br>
+* WWWにおけるハイパーリンクで繋がれたドキュメント全体の構造
+* インターネットの接続構造
+* SNSのコミュニティ構造
+<br>
+===== 複雑ネットワーク問題 =====
+複雑ネットワークとは、現実世界に存在する巨大で複雑なネットワーク、<br>
+あるいはそれらネットワークの性質について考察する問題および分野のことである。<br>
+<br>
+複雑ネットワークは、現実世界の様々な現象を説明するためのパラダイムの1つである。<br>
+<br>
+例<br>
+* WWW
+* 食物連鎖ネットワーク
+* 論文の被引用関係ネットワーク
+* 映画俳優の共演グラフ
+* 線虫の神経回路網グラフ
+* 送電網グラフ
+<br>
+複雑ネットワークの性質<br>
+* スモールワールド性(一見赤の他人に見えても、実際は中間に少数の人を介するだけで繋がっているという性質)
+* スケールフリー性(一部の人は非常に多くの知人を持っているが、大多数の人々は知人の数は少ないという性質)
+* クラスター性(多くの人が互いに知り合いであるようなグループが存在するという性質)
+<br>
+複雑ネットワークのグラフモデル<br>
+* スモールワールドモデル(スモールワールド性を持つグラフのモデル)
+* バラバシ=アルバートモデル(スケールフリー性を持つグラフのモデル)
+<br>
+スモールワード現象<br>
+スモールワールド現象とは、世界中の人の中から任意に2人を選んだとき、その2人は驚くほど少ない知人を介して繋がっているという現象。<br>
+<br>
+例<br>
+ベーコン数とは、アメリカの俳優ケヴィン・ベーコンと映画で共演したことのある俳優のベーコン数を1、<br>
+ベーコン数nの俳優と共演関係にある俳優のベーコン数をn + 1とする。<br>
+世界中の俳優のベーコン数を調べると大多数がベーコン数3から4の範囲に収まる。<br>
+<br>
+スモールワールドネットワーク<br>
+スモールワールド現象に関連する具体的なグラフはスモールワールドネットワークと呼ばれる。<br>
+<br>
+特徴<br>
+* 頂点の数に対して辺の数が少ない。
+* 2頂点間の距離の平均は意外と小さい。
+* 小さなクラスターがたくさんある。
+<br>
+病気の感染や噂の伝達が驚くほど速いのは、人々がスモールワールドネットワークで繋がっているからだと考えられている。<br>
+<br><br>
+== 様々な事象をグラフで表すことのメリット ==
+* グラフに表すことで、複雑な事象の全体が視覚的にとらえられ、理解しやすくなる。
+* 全体の構造を把握しやすくなる。
+* 各点の特徴がとらえやすくなる。
+<br>
+以上のメリットにより、社会の複雑な現象の解明に役立つ。<br>
 <br><br>
 __FORCETOC__
 [[カテゴリ:グラフ理論]]

「第1回 グラフ理論の概要と応用」の版間の差分

「第1回グラフ理論の概要と応用」の版間の差分