第６章 平面的グラフ・彩色・木 駆け足で読む『離散数学〜コンピュータサイエンスの基礎数学』

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

• グラフ理論の駆け足については、別の教科書で書いてある(記事はこちら)ので、今回のシリーズでは、(第５章に同じく)プログラミングにつながる部分のみを中心にしたい
• 平面的グラフ(辺が交叉しないように平面的に描けるグラフ)の用語
  
  • 平面的 planar、地図 map、連結 connected、次数 degree、非平面的グラフ、設備グラフ utility graph、星グラフ star graph、彩色 coloring、n-彩色可能 n-colorable、染色数 chromatic number、地図の双対 dual、木 tree、森 forest、退化木 denegerate tree、全域木 spanning tree、根付き木 rooted tree、根 root、水準 level、深さ depth、葉 leaf、枝 branch、先行する precedes、後続する follows、直後 immediately follows、順序根付き木 ordered rooted tree、番地付け address、一般番地系 universal address system、(番地の)前半部分 initial segment、辞書式順序 lexicographic order、前置記法 prefix form、ポーランド記法 Polish notation、後置記法 postfix form
• プログラミング問題
  
  • 彩色問題->WelchPowell
  • 最小全域木->MinimumSpanningTree(ソースはこちらへ移動しました)

• 第６章終了