yokobuttonの不定期で競技プログラミングをするブログ

不定期で解けた競技プログラミングコンテストの問題を載せています。

2021-04-23から1日間の記事一覧

極大平面的グラフの頂点彩色と四色問題③

4,グラフの頂点彩色 単純グラフGの隣接するどの2頂点も異なる色になるようにGのすべての頂点を色分けすることをGの頂点彩色という。k種類の色によるGの頂点彩色をGのk-彩色といい、Gがk-彩色できるとき、Gはk-彩色可能であるという。 グラフの頂点vに色を…

極大平面的グラフの頂点彩色と四色問題②

2、木 閉路のない連結なグラフを木と呼ぶ。 定理2・1 木において、位数をp、サイズをqとすると、 p=q+1 が成り立つ。 (証明)数学的帰納法で証明する。 ①位数p=1のとき、サイズq=0である。 q≧2とすると、p=2のとき、q=1により式が成り立つ。 ②位数がp-1以…

極大平面的グラフの頂点彩色と四色問題①

(注)この極大平面的グラフの頂点彩色と四色問題の記事の内容や定理の証明は、「グラフ理論序説」の内容をそのままお借りしているところがあります。 1,グラフ グラフGとは、集合の対(V(G)、E(G))である。 V(G)をグラフGの頂点集合、V(G)の元を頂点という…