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

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

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

(注意)この記事は間違っているかもしれません。

 

 

 命題5・2

  極大平面的グラフGの位数をp(p≧3)、サイズq=3p-6、面r=2p-4とすると、Gは4-彩色可能である。

  (証明)

   ⓪p=3のとき、色0、1、2で3-彩色可能であることがわかる。よって、4-彩色可能である。

   このとき、q=3p-6=9-6=3、r=2p-4=6-4=2で極大平面的グラフは構成できる。

   面-頂点色リストを作成する。面-頂点色リストとは、面に番号を付け、面に接する頂点の色をリストにして(頂点色リストと呼ぶ)、その面番号と頂点色リストをリストにしたものである。p=3のときは{1、{0、1、2}}と{2、{0、1、2}}の2つである。

   ①p=4のとき、色3の頂点を1つ追加して、色0、1、2の頂点と辺で結ぶ。これにより、4-彩色可能である。このとき増える面は2つである。

    サイズは3+3=6、面は2+2=4である。

    これはq=3p-6=12-6=6、r=2p-4=8-4=4に等しい。

    よって極大平面的グラフを構成できる。

    面-頂点色リストを更新する。更新の仕方は次のとおりである。面-頂点色リストから色3のない面を1つ選び、頂点色リストの中から2つ選ぶ組み合わせに色3を付け足して頂点色リストにし、面に重複の無いように番号をつけ、その面番号と作成した頂点食リストをリストにして、面-頂点色リストに加える。選んだ面番号のリストは面-頂点色リストから削除する。頂点色リストの中から2つ選ぶ全組み合わせは、3C2=3!/( (3-2)!2! )=3通りあり、色0、1、2がない面が1つずつ必ずできる。

   ②p=5のとき、色0の頂点を1つ追加して、色1、2、3の頂点と辺で結ぶ。これにより、4-彩色可能である。このとき増える面は2つである。

    サイズは6+3=9、面は4+2=6である。

    これはq=3p-6=15-6=9、r=2p-4=10-4=6に等しい。

    よって、極大平面的グラフを構成できる。

    面-頂点色リストを更新する。このとき、色0のない面が必ず1つ以上は存在する。

   ③p=i(i≥5)のとき、色(i-1)mod4の頂点を1つ追加して、その他の色の頂点と辺で結ぶ。これにより、4-彩色可能である。このとき増える面は2つである。

    サイズは6+3(i-4)=3i-6、面は4+2(i-4)=2i-4である。

    これはq=3p-6=3i-6、r=2p-4=2i-4に等しい。

    よって、極大平面的グラフを構成できる。

    面-頂点色リストを更新する。更新の仕方は次のとおりである。面-頂点色リストから色(i-1)mod4のない面を1つ選び、頂点色リストの中から2つ選ぶ組み合わせに色(i-1)mod4を付け足して頂点色リストにし、面に重複の無いように番号をつけ、その面番号と作成した頂点色リストをリストにして、面-頂点色リストに加える。選んだ面番号のリストは面-頂点色リストから削除する。頂点色リストの中から2つ選ぶ全組み合わせは、3C2=3!/( (3-2)!2! )=3通りあり、色(i-1)mod4以外の色がない面は一つずつ必ずできる。

   ④p=i+1のとき、色(i+1-1)mod4の頂点を1つ追加して、その他の色の頂点と辺で結ぶ。これにより、4-彩色かのうである。このとき増える面は2つである。

    サイズは6+3(i+1-4)=3i-3、面は4+2(i+1-4)=2i-2である。

    これは、q=3p-6=3(i+1)-6=3i-3、r=2p-4=2(i+1)-4=2i-2に等しい。

    よって、極大平面的グラフを構成できる。

    面-頂点色リストを更新する。p=iのときに色(i-1)mod4以外の色がない面はひとつずつ必ずできるので、更新可能である。

 

     帰納法により、極大平面的グラフは4-彩色可能である。

 

 四色問題

  すべての平面的グラフは4-彩色可能である。

  (証明)

   命題5・1、5・2よりすべての平面的グラフは4-彩色可能である。

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

(注意)この記事は間違っているかもしれません。

 

5,極大平面的グラフと四色問題

 命題5・1

  位数p(p≧3)、サイズqm=3p-6の極大平面的グラフがk-彩色可能ならば、このグラフからi(0≦i≦qm)の辺を取り除いた平面的グラフGiはk-彩色可能である。

  (証明)

   ①題意より、位数pでサイズがqmの平面的グラフは、極大平面的グラフでk-彩色可能である。

    k-彩色可能ということは、頂点のk色の組み合わせがkC2=k!/( (k-2)!2! )個あり、c1、c2、・・・、cmaxである。このとき、max=k!/( (k-2)!2! )である。cjの最大数をc{j、m}とすると、cjは0以上c{j、m}以下である。

   ②i本(0≦i≦qm)の辺を取り除いた平面的グラフをGiとする。G0は①と同じグラフなのでk-彩色可能である。

   ③Gi(i≠qm)の平面的グラフがk-彩色可能であるする。

    Gi+1の平面的グラフはGiから辺を1つ取り除いた平面的グラフである。

    頂点のk色の組み合わせから辺を1つ取り除いても、cjの本数は0以上c{j、m}以下なのでk-彩色可能である。

   ④Gqmの平面的グラフは、辺が1つもないので、k-彩色可能である。

   これにより、すべての平面的グラフGiはk-彩色可能である。(証明終わり)

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

 

4,グラフの頂点彩色

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

 グラフの頂点vに色を塗ることを頂点vを着色するという。

 グラフGがk-彩色可能で、かつ(k-1)-彩色可能でないとき、グラフGはk-染色的であるという。

 

 定理4・1(四色問題)

  すべての平面的グラフは4-彩色可能である。

 

  1976年にスーパーコンピュータを利用して証明された。

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

2、木

 閉路のない連結なグラフを木と呼ぶ。

 

 定理2・1

  木において、位数を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

    よって、公式が成り立つ。(証明終わり)

 

3,平面的グラフ

 グラフGで、どの2辺もその端点以外では交差しないよう幾何学的に平面上に描くことができたとき、Gを平面的グラフと呼ぶ。

 平面的でないグラフを非平面的グラフと呼ぶ。

 平面的グラフを平面への埋め込み(Gに同形なグラフを平面上に描くこと)を行って、平面上にどの辺も交差しないように描かれた平面的グラフを平面グラフと呼ぶ。

 平面グラフを、有限個の領域に分ける。これらの領域をそれぞれ平面グラフの面と呼ぶ。

 各平面グラフは1つの有界ではない面をもち、これを無限面という。その他の面は有限面である。

 

 定理3・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を極大平面的グラフと呼ぶ。

 

 系3・2

  グラフGを位数p(p≧3)の極大平面的グラフとすると

   q=3p-6、r=2p-4

  である。

  (証明)

   グラフGの面の数をrとすると、極大平面的グラフの場合、すべての面が3つの辺からなっていて、しかも、どの辺も2つの面の境界をもつ。よって、

    3r=2q

   である。この式をオイラーの公式とで面の数rを消去するとq=3p-6が導かれ、サイズを消去するとr=2p-4が導かれる。(証明終わり)

    

 

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

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

 

1,グラフ

 グラフ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は連結グラフであるという。

 連結でないグラフは非連結グラフである。

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

「やさしいグラフ論」を読んでプログラムしたくなったので、載せておきます。

ソースコードC++です。

 

入力:負でない整数の列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;
}

 

 

 

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

「やさしいグラフ論」を読んでプログラムしたくなったので、載せておきます。

ソースコードC++です。

 

入力:負でない整数の列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;
}