四十三庵

蔀の雑記帳

グラフ理論

データ構造とアルゴリズム (新・情報 通信システム工学)

前提

本を読んだだけだと、グラフ理論そのものがよくわらかなかったので、前提を調べた。

内容

  • 最終的なアウトプットが表になるかTreeになるかでわかれる
  • グラフ理論では頂点のことをVertex、辺のことをEdgeと呼ぶ慣習があるよう。
    • Vertex = Node, Edge = link / line
  • 全域木/Spanning tree/極大木→全頂点を含むような辺の集合
  • より厳密に定義するなら、無向グラフ G1 = (V1, E1), G2 = (V2, E2)において、V1=V2かつE1⊆E2になるTree

f:id:st43:20200417185511p:plain
f:id:st43:20200417185540p:plain
f:id:st43:20200417185602p:plain

  • 単純に数え上げると部分木の数は2n-1になる
    (テキストには2nとあるが、頂点が1個でも2個の部分木ができる???)
    →あれ2n-1だとしても、2個の頂点で2個の部分木はできないように思う
    →いやそれはできるか。a-b とb-aがあるのかな。
    →とすると、3つ(a, b, c)になったとき、a-b-c, a-c-b, b-a-c, b-c-a, c-a-b, c-b-a,
    →ちょっと考え方がよくわからない。2nで正しいのかな