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

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

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

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を彩色すること…

17人で3つの話題

漫画「数学ゴールデン」の1巻に次のような問題が出てくる。それを解いてみた。 「17人それぞれが他の全員と互いに手紙のやりとりをしている。 その手紙では3つの話題のみがやりとりされている。 そして、同じ2人組の間でなされる話題は常に同じ1つのやりとり…

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

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)の部分集合 を満たすグラフのことである。特に、…

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

(注意)この記事は間違っているかもしれません。 命題5・2 極大平面的グラフGの位数をp(p≧3)、サイズq=3p-6、面r=2p-4とすると、Gは4-彩色可能である。 (証明) ⓪p=3のとき、色0、1、2で3-彩色可能であることがわかる。よって、4-彩色可能である。 このとき…

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

(注意)この記事は間違っているかもしれません。 5,極大平面的グラフと四色問題 命題5・1 位数p(p≧3)、サイズqm=3p-6の極大平面的グラフがk-彩色可能ならば、このグラフからi(0≦i≦qm)の辺を取り除いた平面的グラフGiはk-彩色可能である。 (証明) ①題意よ…

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

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>…

windows10でのC++のプログラミング環境設定(mingw-w64+VSCode)

今回の記事はほとんど自分用です。 windows10でのC++のプログラミング環境の方法を載せます。 ①7-Zip.exeのダウンロードとインストール 圧縮・解凍ソフト7-Zipをダウンロードしてインストールします。(mingw64の解凍用です) ②mingw-w64のダウンロードと解凍 …

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

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

AtCoder Beginner Contest 198 D - Send More Money

next_permutationを久しぶりに使った。

AtCoder Beginner Contest 198 E - Unique Color

木(グラフ)を作って、dfs。解説そのまま。

AtCoder Beginner Contest 196 D - Hanjo

解説のソースコードみたいにすっきりとはいかなかったけれど、再帰関数で通りました。

AtCoder Beginner Contest 197C-ORXORの問題

解説を見るとb it全探索と書いてあるので全探索でできると思い、再帰関数で書いてみたら通りました。 ソースコードはAtCoder Beginner Contest 197のページのC問題、言語はC++、ユーザはyokobuttonで検索してください。