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

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

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

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

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

２、木 閉路のない連結なグラフを木と呼ぶ。 定理２・１ 木において、位数をp、サイズをqとすると、 p=q+1 が成り立つ。 (証明)数学的帰納法で証明する。 ①位数p=1のとき、サイズq=0である。 q≧2とすると、p=2のとき、q=1により式が成り立つ。 ②位数がp-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++のプログラミング環境の方法を載せます。 ①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>…

next_permutationを久しぶりに使った。

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

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

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