13,009
回編集
「第2回 グラフの基礎概念と例」の版間の差分
ナビゲーションに移動
検索に移動
→単純グラフの表現法
(→隣接) |
|||
| 123行目: | 123行目: | ||
* 表現法1 | * 表現法1 | ||
*: 隣接点をリストする方法。グラフの各点に隣接している点をリストにする。 | *: 隣接点をリストする方法。グラフの各点に隣接している点をリストにする。 | ||
*: <br> | |||
*: 下図に、単純グラフGの隣接点をリストする方法を示す。 | |||
[[ファイル:Graph Theory 2 6.jpg|フレームなし|中央]] | |||
* 表現法2 | * 表現法2 | ||
*: 行列を使用する方法。隣接行列と接続行列を使用する。 | *: 行列を使用する方法。隣接行列と接続行列を使用する。 | ||
*: <br> | |||
*: 下図に、隣接行列を使用する方法を示す。 | |||
* | |||
*: 単純グラフGの点が{1, 2, ..., n}とラベル付けされているとき、 | *: 単純グラフGの点が{1, 2, ..., n}とラベル付けされているとき、 | ||
*: 単純グラフGの隣接行列Aとは、点iとjを結ぶ辺の本数をij要素とするn×n行列である。 | *: 単純グラフGの隣接行列Aとは、点iとjを結ぶ辺の本数をij要素とするn×n行列である。 | ||
* | *: <br> | ||
*: 下図に、接続行列を使用する方法を示す。 | |||
*: 単純グラフGについて、更に、辺が{1, 2, ..., m}とラベル付けされているとき、 | *: 単純グラフGについて、更に、辺が{1, 2, ..., m}とラベル付けされているとき、 | ||
*: 単純グラフGの接続行列Mとは、点iが辺jに接続しているときij要素が1であり、接続していないとき0であるようなn×m行列である。 | *: 単純グラフGの接続行列Mとは、点iが辺jに接続しているときij要素が1であり、接続していないとき0であるようなn×m行列である。 | ||
[[ファイル:Graph Theory 2 7.jpg|フレームなし|中央]] | |||
<br><br> | <br><br> | ||