高校大学連携授業 2

「関係を図で表現する道具」(坂本 明雄)

  1. はじめに
  2. 関係を数学的に定義すると
  3. 関係を座標図で表現する
  4. 関係を矢線図で表現する
  5. 関係を有向グラフで表現する
  6. ケーニヒスベルグの七つの橋:グラフ理論の誕生
  7. 握手の定理
  8. ハミルトングラフ:難しい問題の例
  9. 同型なグラフ

印刷用PDFファイル [本文(190KB)] [解答(65KB)]

※一部特殊文字を使用しているため環境によっては、文字化けが起こる場合があります。その場合は、印刷用PDFファイルをご覧ください。


4. 関係を有向グラフで表現する

 矢線図では,集合のひとつの要素に対応する小さな白丸が左と右にそれぞれひとつずつある。そこで,同じ要素に対応する白丸をひとつにまとめ,これを頂点と呼ぶ。頂点は一列に並べる必要はなく,平面上のどこに書いてもよい。要素のペア (x, y) が関係に選ばれているとき,要素 x の白丸(頂点)から要素 y の白丸(頂点)へ矢印がついた線を引くことによってできる図を関係の有向グラフという。矢印がついた線は有向辺と呼ばれる。ただし,要素のペア (x, x) に対しては, x の頂点から出てその頂点へ帰ってくる有向辺になり,これを特にループと呼ぶ。

[例4] 集合 A = {a, b, c} 上の関係 R2 = {(a, b), (a, c), (b, a), (b, c), (c, c)} の有向グラフは右のようになる。頂点 c にループがある。

【練習問題4】 集合 A = {a, b, c} 上の2つの関係 R3 = {(a, a), (a, b), (b, a), (b, b), (c, c)} と R4 = {(a, c), (b, c), (c, a), (c, b)} を有向グラフでそれぞれ表現せよ。








 

 

トップページに戻る