高校大学連携授業 2

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

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

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

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


1. 関係を数学的に定義すると

 集合 A と集合 B の直積集合 A×B の任意の部分集合を“A から B への関係”という。 A から A への関係を単に“A 上の関係”という。以下では A 上の関係だけを考える。

  • 集合って何?
    ある“もの”の集まりを集合という。

    [例1-1] 例えば: A = {a, b, c} とか B = {リンゴ, ミカン, ナシ, ブドウ} など

  • 直積集合 A×B とは?
    A の要素と B の要素のペアを全部集めた集合。2つの要素 x と y のペアを (x, y) と書く。

    [例1-2]
       A×B = {(a, リンゴ), (a, ミカン), (a, ナシ), (a, ブドウ),
               (b, リンゴ), (b, ミカン), (b, ナシ), (b, ブドウ),
               (c, リンゴ), (c, ミカン), (c, ナシ), (c, ブドウ)}
       A×A = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
       B×B = {(リンゴ, リンゴ), (リンゴ, ミカン), (リンゴ, ナシ), ..., (ブドウ, ブドウ)}

  • 部分集合とは,もとの集合からいくつかの要素を集めてできる集合。もとの集合の要素を全部集めてもよい。

    [例1-3] 次の集合はすべて A×A の部分集合であるから, A上の関係である。
       R1 = {(a, a), (b, b), (c, c)}
       R2 = {(a, b), (a, c), (b, a), (b, c), (c, c)}
       R3 = {(a, a), (a, b), (b, a), (b, b), (c, c)}
       R4 = {(a, c), (b, c), (c, a), (c, b)},
       R5 = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)} = A×B
【練習問題1】 果物の集合B = {リンゴ, ミカン, ナシ, ブドウ}上の関係の例をひとつあげよ。その関係に特別な意味づけをする必要はない。








 

 

トップページに戻る