極大平面的グラフの頂点彩色と四色問題②
２、木
閉路のない連結なグラフを木と呼ぶ。
定理２・１
木において、位数をp、サイズをqとすると、
p=q+1
が成り立つ。
(証明)数学的帰納法で証明する。
①位数p=1のとき、サイズq=0である。
q≧2とすると、p=2のとき、q=1により式が成り立つ。
②位数がp-1以下のすべての木について定理が成り立つと仮定する。
木Tが1つの辺を取り除くと、2つの木T1、T2に分かれるとする。
このとき、木T1、T2の位数をp1、p2、サイズをq1、q2とすると、帰納法の仮定より、
p1=q1+1、p2=q2+1
が成り立つ。木Tについては
p=p1+p2、q=q1+q2+1
が成り立ち、
p=p1+p2=(q1+1)+(q2+1)=(q1+q2+1)+1=q+1
よって、公式が成り立つ。(証明終わり)
３，平面的グラフ
グラフGで、どの2辺もその端点以外では交差しないよう幾何学的に平面上に描くことができたとき、Gを平面的グラフと呼ぶ。
平面的でないグラフを非平面的グラフと呼ぶ。
平面的グラフを平面への埋め込み(Gに同形なグラフを平面上に描くこと)を行って、平面上にどの辺も交差しないように描かれた平面的グラフを平面グラフと呼ぶ。
平面グラフを、有限個の領域に分ける。これらの領域をそれぞれ平面グラフの面と呼ぶ。
各平面グラフは1つの有界ではない面をもち、これを無限面という。その他の面は有限面である。
定理３・１(オイラーの公式)
Gを連結平面グラフとする。Gの位数をp、サイズをq、面の個数をrとすれば、
p-q+r=2
が成り立つ。
(証明)Gの辺の数に関しての数学的帰納法で証明する。
①q=0のとき、Gは連結であるのでp=1、無限面しかないので、r=1である。
したがって、p-q+r=1-0+1=2。よって、公式は成り立つ。
②q-1本以下の辺を持つすべてのグラフGで公式が成り立つと仮定する。
いま、グラフGにはq本の辺があるとすると、もしGが木ならば、q=p-1であり、r=1であるから、
p-q+r=p-(p-1)+1=2
で公式が成り立つ。
Gが木でない場合、Gの閉路に含まれる1つの辺をeとし、このeを取り除くと、面が1つ減る。
p-(q-1)+r-1=p-q+r=2
となり、公式は成り立っている。(証明終わり)
平面的グラフGにおいて隣接していない任意の2点に1つの辺を加えると、非平面的グラフになるとき、この平面的グラフGを極大平面的グラフと呼ぶ。
系３・２
グラフGを位数p(p≧3)の極大平面的グラフとすると
q=3p-6、r=2p-4
である。
(証明)
グラフGの面の数をrとすると、極大平面的グラフの場合、すべての面が3つの辺からなっていて、しかも、どの辺も2つの面の境界をもつ。よって、
3r=2q
である。この式をオイラーの公式とで面の数rを消去するとq=3p-6が導かれ、サイズを消去するとr=2p-4が導かれる。(証明終わり)
極大平面的グラフの頂点彩色と四色問題①
（注）この極大平面的グラフの頂点彩色と四色問題の記事の内容や定理の証明は、「グラフ理論序説」の内容をそのままお借りしているところがあります。
１，グラフ
グラフGとは、集合の対(V(G)、E(G))である。
V(G)をグラフGの頂点集合、V(G)の元を頂点という。
E(G)をグラフGの辺集合、E(G)の元を辺という。
しばしば、V(G)、E(G)をそれぞれV、Eで表す。
グラフは、頂点集合Vが有限集合か無限集合かによって、有限グラフあるいは無限グラフという。
辺がe、e={u、v}のとき、辺は頂点とを”結ぶ”という。
グラフのうち、2つの頂点を2本以上の辺(多重辺)で結ぶことを認めるグラフを多重グラフと呼ぶ。
グラフのうち、同じ頂点を結ぶ辺(ループ)を認めるグラフをループグラフと呼ぶ。
グラフのうち、頂点集合が有限でループも多重辺も認めないグラフを単純グラフと呼ぶ。
以下、グラフといえば単純グラフを意味するものとする。
辺e={u、v}のとき、辺eに対して頂点u、vを辺eの端点という。
このとき、辺eは端点u、vに”接続している”といい、頂点u、vは辺eに”接続している”という。
また、頂点uと頂点vは互いに”隣接している”という。
グラフGの頂点集合の要素の個数をGの位数、辺の本数をGのサイズという。
以下では、位数をp、サイズをqで表す。このとき、Gを(p、q)グラフと呼ぶ。
Gの頂点vに接続するGの辺の個数をvの次数といい、dG(v)で表す。
グラフGがグラフHに同型であるとは、V(G)からV(H)への1対1対応fで
{u、v}がE(G)の元であるとき、そのときに限り、{f(u)、f(v)}がE(H)の元である
ことを満たすものが存在することである。
定理1・1(握手補題)
Gは(p、q)グラフとし、V(G)={v1、v2、・・・、vp}とする。このとき、次の式が成り立つ。
Σ{p、i=1}dG(vi)=2q
(証明)
グラフGの次数の総和Σ{p、i=1}dG(vi)は、Gの中で、各辺の両端で1回ずつ合計2回数えている。したがって、次数の総和は辺の本数qの2倍である。(証明終わり)
グラフGにおいて、歩道とは、Gの頂点と辺とが交互に現れる有限列
W=v0e1v1e2v2・・・ekvk
であって、各辺ei(1≦i≦k)は頂点vi-1とviを端点としてもつようなものである。
頂点v0、vkをそれぞれ歩道の始点、終点と呼ぶ。始点と終点が一致するとき、Wは”閉じている”という。
すべての辺が異なる歩道を小道といい、すべての頂点が異なる歩道を道という。
歩道や道の辺の個数をそれらの長さという。
閉じている小道は回路といい、閉じている道は閉路という。
グラフG内の2頂点u、vに対してG内のu-v道が存在するとき、u、vは”連結している”という。
グラフGのどの2頂点も連結しているとき、Gは連結グラフであるという。
連結でないグラフは非連結グラフである。
ハーベル-ハキミの判定法
「やさしいグラフ論」を読んでプログラムしたくなったので、載せておきます。
入力：負でない整数の列s：d1,d2,・・・,dn(d1≧d2≧・・・≧dn)
出力：sがグラフ的であるならばグラフを出力、そうでないならばNoを出力。
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int main(){
//負でない整数列の入力
int N = 0;
cin >> N;
vector<int> d(N,0);
for(int i = 0; i < d.size(); i++){
cin >> d[i];
}
int INF = 0x3fffffff;
bool check = true;
vector< pair<int, vector<int> > > L;
int d_max = 0;
int K = N;
while( (d_max = *max_element(d.begin(),d.end())) >= 1 && check == true){
if( !(K >= d_max+1) ){
check = false;
break;
}
auto itr_i = find(d.begin(), d.end(), d_max);
int i = itr_i - d.begin();
d[i] = -INF;
vector<int> l;
for(int x = i+1; x < d.size(); x++){
int x_max = *max_element(d.begin()+x,d.end());
auto itr_x_i = find(d.begin()+x,d.end(),x_max);
int x_i = itr_x_i - d.begin();
//cout << x_max <<" "<< x_i << endl;
l.emplace_back(x_i);
d[x_i]--;
d_max--;
if(d_max == 0){
break;
}
}
L.emplace_back(make_pair(i,l));
//for(int i =0; i < d.size(); i++){
// cout << d[i] << " ";
//}cout << endl;
for(int j = 0; j < d.size(); j++){
if(d[j] == -1){
check = false;
break;
}
}
if(check == false){
break;
}
K--;
}
if(check == false){
cout << "No" << endl;
}else{
vector< vector<int> > G(N);
vector<int> l;
for(int j = L.size()-1; j >= 0; j--){
int u = L[j].first;
l = L[j].second;
for(int v = 0; v < l.size(); v++){
G[u].emplace_back(l[v]);
G[l[v]].emplace_back(u);
}
}
for(int i = 0; i < G.size(); i++){
cout << i << ":";
for(int j = 0; j < G[i].size(); j++){
cout << G[i][j] << " ";
}cout << endl;
}
}
return 0;
}
エルデス-ガライの定理(判定法)
「やさしいグラフ論」を読んでプログラムしたくなったので、載せておきます。
入力：負でない整数の列s：d1,d2,・・・,dn(d1≧d2≧・・・≧dn)
出力：sがグラフ的であるならばYes、そうでないならばNo。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
//負でない整数の列の入力
int N = 0;
cin >> N;
vector<int> d(N+1,0);
for(int i = 1; i < d.size(); i++){
cin >> d[i];
}
//前計算
vector<int> sum(N+1,0);
for(int i = 1; i < d.size(); i++){
sum[i] = d[i];
}
for(int i = 1; i < sum.size(); i++){
sum[i] = sum[i-1] + sum[i];
}
//次数の総数が偶数かどうかの判定
bool check = true;
if(sum[sum.size()-1] % 2 != 0){
check = false;
}else{
int sub = 0;
for(int k = 1; k <= N-1; k++){
sub = k * (k-1);
for(int i = k+1; i <= N; i++){
sub = sub + min(k, d[i]);
}
if(sum[k] <= sub){
}else{
check = false;
break;
}
}
}
if(check == true){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
return 0;
}
windows10でのC++のプログラミング環境設定(mingw-w64+VSCode)
今回の記事はほとんど自分用です。
windows10でのC++のプログラミング環境の方法を載せます。
①7-Zip.exeのダウンロードとインストール
圧縮・解凍ソフト7-Zipをダウンロードしてインストールします。(mingw64の解凍用です)
②mingw-w64のダウンロードと解凍
mingw-w64のダウンロードページ
https://sourceforge.net/projects/mingw-w64/files/
に行って、インストーラではなくその下の
x86_64-win32-seh
をクリックして7zファイルをダウンロードします。
「x86_64-8.1.0-release-win32-seh-rt_v6-rev0.7z」というファイルがダウンロードされるので、これを解凍します。
[2022/4/22:追記] 2022/4/22現在の最新バージョンのファイル
WinLibs standalone build of GCC and MinGW-w64 for Windows
に行って、
GCC 11.2.0 + MinGW-w64 10.0.0(UCRT)のWin64の
7-Zip archive
をクリックして7zファイルをダウンロードします。
「winlibs-x86_64-posix-seh-gcc-11.2.0-mingw-w64ucrt-10.0.0-r1.7z」というファイルがダウンロードされるので、これを解凍します。
解凍したら、「mingw64」というファイルができるので、このファイルをC直下に移動させます。
③VSCode(VisualStudioCode)のダウンロードとインストールおよび設定
VSCodeのダウンロードページへ行って、User Installerをダウンロードします。
https://azure.microsoft.com/ja-jp/products/visual-studio-code/
実行し、インストールします。
起動したら、左側にある「Extentions」で「C/C++」と「Japanese Language Pack for Visual Studio Code」をインストールします。再起動すると日本語環境になります。
「フォルダを開く」でソースコードを置くフォルダを開きます。
「新規ファイル」でファイルを作成し、「名前を付けて保存」で保存します。
簡単なプログラム(helloworldなど)を作成します。
上側にある「表示」の「コマンドパレット」から「C/C++:構成の編集(UI)」をクリックします。
コンパイラパスの欄に「C:\mingw64\bin\g++.exe」を入力します。
IntelliSenseモードを「windows-gcc-x64」に変更します。
[2022/4/24:追記] コンパイラ引数の追加
コンパイラ引数に
-static
-lstdc++
-lgcc
-lwinpthread
を入力すると、実行ファイルの実行の際に、システムエラーが出ずに、実行されます。
ビルドしたいファイル(先ほど作成したファイル)を表示した状態で
「コマンドパレット」から「タスク:既定のビルドタスクを構成する」をクリックします。
ビルドしたいファイルを表示した状態で上にある「ターミナル」から「ビルドタスクの実行」をクリックすると、「ファイル名.exe」の実行ファイルが作成されます。
実行はコマンドプロンプトでします。
「スタートメニュー」の「windowsシステムメニュー」に「コマンドプロンプト」があるので、クリックして実行します。cdコマンドで先ほど作成したフォルダに移動し、実行ファイルのファイル名を入力すると実行されます。
実行すると「libstdc++-6.dll」と「libgcc_s_seh-1.dll」が見つからないとシステムエラーが出るので、「mingw64」のフォルダから検索して、実行ファイルのあるフォルダにコピーします。
[2022/4/22:追記] 「libwinpthread-1.dll」の追加
GCC 11.2.0 + MinGW-w64 10.0.0(UCRT)の場合「libwinpthread-1.dll」も見つからないとシステムエラーが出るので、「mingw64」フォルダから検索して、実行ファイルのあるフォルダにコピーします。
これで無事にwindows10でC++のプログラミングができるようになりました。
グラフ同型性判定プログラム
グラフ同型性判定の本を読んで書いてみました。
その本自体にはプログラムは載っていなかったので、間違っているかも・・・。
ちなみにC++です。
入力はN頂点M辺のグラフG1、G2
出力は同型ならYes、そうではないならばNo
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int main(){
//G1,G2の作成
int N1 = 0, M1 = 0;
cin >> N1 >> M1;
vector< vector<int> > G1(N1);
for(int i = 0; i < M1; i++){
int a = 0, b = 0;
cin >> a >> b;
G1[a].emplace_back(b);
G1[b].emplace_back(a);
}
int N2 = 0, M2 = 0;
cin >> N2 >> M2;
vector< vector<int> > G2(N2);
for(int ii = 0; ii < M2; ii++){
int a = 0, b = 0;
cin >> a >> b;
G2[a].emplace_back(b);
G2[b].emplace_back(a);
}
for(int i = 0; i < G1.size(); i++){
sort(G1[i].begin(), G1[i].end());
}
for(int ii = 0; ii < G2.size(); ii++){
sort(G2[ii].begin(), G2[ii].end());
}
/*
cout << "G1" <<endl;
for(int i = 0; i < G1.size(); i++){
for(int j = 0; j < G1[i].size(); j++){
cout << G1[i][j] << " ";
}cout << endl;
}cout << endl;
cout << "G2" <<endl;
for(int ii = 0; ii < G2.size(); ii++){
for(int jj = 0; jj < G2[ii].size(); jj++){
cout << G2[ii][jj] << " ";
}cout << endl;
}cout << endl;
*/
//全順列用の頂点集合の作成
vector<int> perm(N1, 0);
for(int i = 0; i < N1; i++){
perm[i] = i;
}
//同型性チャック用
bool check = true;
map<int, int> mp;
do{
for(int i = 0; i < perm.size(); i++){
mp[i] = perm[i];
}
//G2からG3を作成する
vector< vector<int> > G3(N2);
for(int ii = 0; ii < G2.size(); ii++){
for(int jj = 0; jj < G2[ii].size(); jj++){
int a = mp[ii];
int b = mp[G2[ii][jj]];
G3[a].emplace_back(b);
}
}
for(int iii = 0; iii < G3.size(); iii++){
sort(G3[iii].begin(), G3[iii].end());
}
/*
cout << "G3" <<endl;
for(int iii = 0; iii < G3.size(); iii++){
for(int jjj = 0; jjj < G3[iii].size(); jjj++){
cout << G3[iii][jjj] << " ";
}cout << endl;
}cout << endl;
*/
//同型性チャック
//G1とG2が同型ならば
//G2から作ったG3のどれかはG1と同じ
check = true;
if(G1.size() == G3.size()){
for(int i = 0; i < G1.size(); i++){
if(check == false){
break;
}
if(G1[i].size() == G3[i].size()){
for(int j = 0; j < G1[i].size(); j++){
if(check == false){
break;
}
if(G1[i][j] == G3[i][j]){
}else{
check = false;
}
}
}else{
check = false;
}
}
}else{
check = false;
}
//全ての辺が同じならばcheckはtrueになっている。
if(check == true){
break;
}
}while(next_permutation(perm.begin(), perm.end()));
if(check == true){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
return 0;
}
