$\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\inset}[2]{\{#1 \mid #2\}}$ $\newcommand{\name}[1]{\emph{#1}}$ $\newcommand{\size}[2][]{\left| #2^{#1} \right|}$ $\newcommand{\sig}[1]{\mathcal{#1}}$

Chordal Graph

最近Chordal Graphがマイブームです． このシリーズの記事でわからないところやこれ間違っているぞっというのがあったら Twitterで教えてくれると僕が喜びます．

Chordal Graphとは

Chordal Graphとは任意の長さ4以上のサイクルに対して弦が存在するグラフです．wikiへのリンク ここで，ある辺$e$がサイクル$C = (u_1, \dots, u_k)$の弦（chord）とは，$e = \set{u_i, u_j}$かつ，$e$が$C$に含まれない辺のことです． つまり，$C$をより短いサイクルにする辺ということですね．こんな感じの例です．

f:id:chocobaby-aporo:20171104213013j:plain

これだけ聞くと，なんの感想もわかないのですが，実は色々と面白い性質があって最近勉強中です． この記事のネタ本はこれです． これから何回かに分けて自分の勉強を兼ねてこの本の内容を紹介をしていこうと思います．

とりあえず紹介しようかと思っている内容のキーワード