高校大学連携授業 2

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

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

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

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


8. 同型なグラフ

  • 頂点の位置や辺の描き方は全く自由
     
  • 同型なグラフ:同じグラフ = 頂点どうしにうまく一対一の対応をつけて,
                   すべての辺は対応する頂点の間にあるようにできる...
     

  • 【練習問題8-1】 下の2つのグラフは同型なグラフである。頂点a, b, c, d, eと頂点1, 2, 3, 4, 5をどのように対応づけるとよいか。


    【練習問題8-2】 4個の頂点をもつ同型ではない単純グラフをすべて列挙せよ。
     [ヒント:辺の本数が0,1,5,6のものはそれぞれ1つだけ。辺が2本のものと4本のものはそれぞれ2つあり,辺が3本の単純グラフは3種類ある。]

    辺0本 辺1本 辺2本
    辺3本
    辺4本 辺5本 辺6本

    【練習問題8-3】 下の3つのグラフのうち2つは同型であるが,他のものはこれらと同型ではない。どれとどれが同型か。また他のものが同型ではない理由を考えよ。



     

     

    トップページに戻る