第５章 グラフ理論 駆け足で読む『離散数学〜コンピュータサイエンスの基礎数学』

本駆け足シリーズの全体の目次はこちら

• グラフ理論の駆け足については、別の教科書で書いてある(記事はこちら)ので、今回のシリーズでは、プログラミングにつながる部分のみを中心にしたい
• グラフの基本用語
  
  • 点 vertex、辺 edge、隣接する adjacent、多重グラフ multigraph、ループ loop、部分グラフ subgraph、グラフより生成された部分グラフ a subgraph generated from a graph、有限 finite、自明な trivial、接続する incident、次数 degree、孤立点 isorated vertex、歩道 walk、閉じた歩道 closed walk、小道 trail、閉路 cycle、連結 connected

、連結成分 connected component、距離 distance、直径 diameter、切断点 cut point、周遊可能 traversable、完全 complete、次数kの正則 k-regular、２部 bipartite、非閉路的 cycle-free、無閉路 acyclic、木 tree、ラベル付きグラフ labeled graph、重み weight、同型 isomorphic、同相 homeomorphic

• グラフの行列表現
  
  • 辺行列 edge matrix、隣接行列 adgacecy matrix、連結行列 connection matrix
• プログラミング問題
  
  • 辺行列情報より、頂点リストの作成->CountVandDeg、頂点次元の算出->CountVandDeg、隣接行列作成->CreateAdjMatrix、隣接行列作成->CreateConMatrix、連結判定・連結行列作成(ただしTensor)->Connection、辺の追加->AddEdge
• ソースはこちらへ移動しました
• 第５章　終了