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

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

グラフ理論

平面性テストと埋め込みのプログラム

// an implementation of the hopcroft and tarjan planarity test and embedding algorithmを参考に平面性テストと埋め込みのプログラムを作成しました。// 入力 : 頂点数n,辺数mの単純無向グラフG// 出力 : Gが平面的ならばPLANARと頂点数n,辺数mの平面的…

木の同型性判定プログラム

//木の同型性判定プログラム//"Explanation for Tree isomorphism talk"と"木を隠すなら森の中"を参考にプログラミングしてみました。//ソースコードはC++//入力:頂点数n、(辺数n-1)、の二つの根なし無向木T1とT2//出力:T1とT2が同型ならば"Yes"、そうでない…

グラフの平面性テスト(Left-Right Planarity Test)

//グラフの平面性テストのプログラムです。//Ulrik BrandesのThe Left-Right Planarity Testを参考にしてプログラミングしてみました。//Embeddingのところは未完成なので参考程度にどうぞ。//ソースコードはC++です。//入力:頂点数n、辺数mの単純無向グラフ…

リスト彩色とリスト彩色予想②

2,リスト彩色予想 リスト彩色予想 任意の単純グラフGは、ch1(G)=χ1(G)である。 (証明) 1つ反例を示すことで、予想を否定する。 完全グラフKpの位数が奇数の場合を考える。Kpのサイズqはp(p-1)/2である。 完全グラフKpに対してχ1(Kp)=p(pが奇数)、p-1(pが偶…

リスト彩色とリスト彩色予想①

(注意)この記事はディーステル「グラフ理論」の内容をお借りしている部分が多いです。 1、リスト彩色 グラフGと、その各頂点に対して塗ることが許される色のリストが与えられている。このとき、そのリストから選んだ色を頂点に割り当てて、Gを彩色すること…

完全グラフと全彩色予想④

4,全彩色 グラフGの全彩色とは、Gの隣接するどの2元、または接続するどの2元も異なる色を持つようなGの元(頂点と辺)に色を付けることである。k個の色を用いる全彩色をk-全彩色という。グラフGに対して、k-全彩色が存在するときGはk-全彩色可能であるという…

完全グラフと全彩色予想③

3,辺彩色 グラフGの隣接する辺が異なる色になるように、グラフGの各辺に色をつけることを、Gの辺彩色といい、k個の色が使われているとき、それをk-辺彩色という。グラフGに対して、k-辺彩色が存在するときGはk-辺彩色可能であるという。Gがk-辺彩色可能で…

完全グラフと全彩色予想②

2、線グラフと全グラフ グラフGにおいて、頂点集合E(G)を持ち、その中の2頂点は、G内の隣接する2辺であるとき、かつそのときに限って隣接するようなグラフをGの線グラフといいL(G)で表す。 グラフGの全グラフT(G)とは、集合V(G)⋃E(G)と1対1対応する頂点集合…

完全グラフと全彩色予想①

(注意)完全グラフと全彩色予想の内容や定理の証明は「グラフ理論序説」からお借りしている部分が多いです。 1,因子分解 グラフHがグラフGの部分グラフであるとは、Hが V(H)がV(G)の部分集合 かつ E(H)がE(G)の部分集合 を満たすグラフのことである。特に、…

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

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)の元を頂点という…

ハーベル-ハキミの判定法

「やさしいグラフ論」を読んでプログラムしたくなったので、載せておきます。 ソースコードはC++です。 入力:負でない整数の列s:d1,d2,・・・,dn(d1≧d2≧・・・≧dn) 出力:sがグラフ的であるならばグラフを出力、そうでないならばNoを出力。 #include<iostream>#inclu</iostream>…

エルデス-ガライの定理(判定法)

「やさしいグラフ論」を読んでプログラムしたくなったので、載せておきます。 ソースコードはC++です。 入力:負でない整数の列s:d1,d2,・・・,dn(d1≧d2≧・・・≧dn) 出力:sがグラフ的であるならばYes、そうでないならばNo。 #include<iostream>#include<vector>#include<algorithm> usin</algorithm></vector></iostream>…

グラフ同型性判定プログラム

グラフ同型性判定の本を読んで書いてみました。 その本自体にはプログラムは載っていなかったので、間違っているかも・・・。 ちなみにC++です。 入力はN頂点M辺のグラフG1、G2 出力は同型ならYes、そうではないならばNo #include<iostream>#include<vector>#include<map>#include<algorithm> u</algorithm></map></vector></iostream>…