0030算法筆記——最大團問題和圖的m著色問題

     1、最大團問題

     問題描述

     給定無向圖G=(V, E),其中V是非空集合,稱為頂點集;E是V中元素構成的無序二元組的集合,稱為邊集,無向圖中的邊均是頂點的無序對,無序對常用圓括號“( )”表示。如果U∈V,且對任意兩個頂點u,v∈U有(u, v)∈E,則稱U是G的完全子圖(完全圖G就是指圖G的每個頂點之間都有連邊)。G的完全子圖U是G的團當且僅當U不包含在G的更大的完全子圖中。G的最大團是指G中所含頂點數最多的團。

     如果U∈V且對任意u,v∈U有(u, v)不屬於E,則稱U是G的空子圖。G的空子圖U是G的獨立集當且僅當U不包含在G的更大的空子圖中。G的最大獨立集是G中所含頂點數最多的獨立集。

     對於任一無向圖G=(V, E),其補圖G'=(V', E')定義為:V'=V,且(u, v)∈E'當且僅當(u, v)∈E。
     如果U是G的完全子圖,則它也是G'的空子圖,反之亦然。因此,G的團與G'的獨立集之間存在一一對應的關系。特殊地,U是G的最大團當且僅當U是G'的最大獨立集。

     例:如圖所示,給定無向圖G={V, E},其中V={1,2,3,4,5},E={(1,2), (1,4), (1,5),(2,3), (2,5), (3,5), (4,5)}。根據最大團(MCP)定義,子集{1,2}是圖G的一個大小為2的完全子圖,但不是一個團,因為它包含於G的更大的完全子圖{1,2,5}之中。{1,2,5}是G的一個最大團。{1,4,5}和{2,3,5}也是G的最大團。右側圖是無向圖G的補圖G'。根據最大獨立集定義,{2,4}是G的一個空子圖,同時也是G的一個最大獨立集。雖然{1,2}也是G'的空子圖,但它不是G'的獨立集,因為它包含在G'的空子圖{1,2,5}中。{1,2,5}是G'的最大獨立集。{1,4,5}和{2,3,5}也是G'的最大獨立集。

 
 

     算法設計

     無向圖G的最大團和最大獨立集問題都可以用回溯法在O(n2^n)的時間內解決。圖G的最大團和最大獨立集問題都可以看做是圖G的頂點集V的子集選取問題。因此可以用子集樹來表示問題的解空間。首先設最大團為一個空團,往其中加入一個頂點,然後依次考慮每個頂點,查看該頂點加入團之後仍然構成一個團,如果可以,考慮將該頂點加入團或者舍棄兩種情況,如果不行,直接舍棄,然後遞歸判斷下一頂點。對於無連接或者直接舍棄兩種情況,在遞歸前,可采用剪枝策略來避免無效搜索。為瞭判斷當前頂點加入團之後是否仍是一個團,隻需要考慮該頂點和團中頂點是否都有連接。程序中采用瞭一個比較簡單的剪枝策略,即如果剩餘未考慮的頂點數加上團中頂點數不大於當前解的頂點數,可停止繼續深度搜索,否則繼續深度遞歸當搜索到一個葉結點時,即可停止搜索,此時更新最優解和最優值。

     算法具體實現如下:

[cpp]
//最大團問題 回溯法求解  
#include "stdafx.h"  
#include <iostream>  
#include <fstream>  
using namespace std; 
 
const int N = 5;//圖G的頂點數  
ifstream fin("5d7.txt");    
 
class Clique 

    friend int MaxClique(int **,int[],int); 
    private: 
        void Backtrack(int i); 
        int **a,        //圖G的鄰接矩陣  
            n,          //圖G的頂點數  
            *x,         //當前解  
            *bestx,     //當前最優解  
            cn,         //當前頂點數  
            bestn;      //當前最大頂點數  
}; 
 
int MaxClique(int **a, int v[], int n); 
 
int main() 

    int v[N+1]; 
    int **a = new int *[N+1];   
    for(int i=1;i<=N;i++)     
    {     
        a[i] = new int[N+1];     
    }  
     
    cout<<"圖G的鄰接矩陣為:"<<endl; 
    for(int i=1; i<=N; i++)   
    {   
        for(int j=1; j<=N; j++)   
        {   
            fin>>a[i][j];       
            cout<<a[i][j]<<" ";     
        }   
        cout<<endl;   
    } 
 
    cout<<"圖G的最大團解向量為:"<<endl; 
    cout<<"圖G的最大團頂點個數為:"<<MaxClique(a,v,N)<<endl; 
 
    for(int i=1;i<=N;i++)     
    {     
        delete[] a[i];    
    }  
    delete []a; 
    return 0; 

 
// 計算最大團  
void Clique::Backtrack(int i) 

    if (i > n) // 到達葉結點  
    { 
        for (int j = 1; j <= n; j++) 
        { 
            bestx[j] = x[j]; 
            cout<<x[j]<<" "; 
        } 
        cout<<endl; 
        bestn = cn; 
        return; 
    } 
    // 檢查頂點 i 與當前團的連接  
    int OK = 1; 
    for (int j = 1; j < i; j++) 
    if (x[j] && a[i][j] == 0) 
    { 
        // i與j不相連  
        OK = 0; 
        break; 
    } 
 
    if (OK)// 進入左子樹  
    { 
        x[i] = 1; 
        cn++; 
        Backtrack(i+1); 
        x[i] = 0; 
        cn–; 
    } 
 
    if (cn + n – i >= bestn)// 進入右子樹  
    { 
        x[i] = 0; 
        Backtrack(i+1); 
    } 

 
int MaxClique(int **a, int v[], int n) 

    Clique Y; 
 
    //初始化Y  
    Y.x = new int[n+1]; 
    Y.a = a; 
    Y.n = n; 
    Y.cn = 0; 
    Y.bestn = 0; 
    Y.bestx = v; 
    Y.Backtrack(1); 
    delete[] Y.x; 
    return Y.bestn; 

//最大團問題 回溯法求解
#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;

const int N = 5;//圖G的頂點數
ifstream fin("5d7.txt");  

class Clique
{
 friend int MaxClique(int **,int[],int);
 private:
  void Backtrack(int i);
  int **a,  //圖G的鄰接矩陣
   n,   //圖G的頂點數
   *x,   //當前解
   *bestx,  //當前最優解
   cn,   //當前頂點數
   bestn;  //當前最大頂點數
};

int MaxClique(int **a, int v[], int n);

int main()
{
 int v[N+1];
 int **a = new int *[N+1]; 
    for(int i=1;i<=N;i++)   
    {   
        a[i] = new int[N+1];   
    }
 
 cout<<"圖G的鄰接矩陣為:"<<endl;
 for(int i=1; i<=N; i++) 
    { 
        for(int j=1; j<=N; j++) 
        { 
            fin>>a[i][j];     
            cout<<a[i][j]<<" ";   
        } 
        cout<<endl; 
    }

 cout<<"圖G的最大團解向量為:"<<endl;
 cout<<"圖G的最大團頂點個數為:"<<MaxClique(a,v,N)<<endl;

 for(int i=1;i<=N;i++)   
    {   
        delete[] a[i];  
    }
 delete []a;
 return 0;
}

// 計算最大團
void Clique::Backtrack(int i)
{
 if (i > n) // 到達葉結點
 {
  for (int j = 1; j <= n; j++)
  {
   bestx[j] = x[j];
   cout<<x[j]<<" ";
  }
  cout<<endl;
  bestn = cn;
  return;
 }
 // 檢查頂點 i 與當前團的連接
 int OK = 1;
 for (int j = 1; j < i; j++)
 if (x[j] && a[i][j] == 0)
 {
  // i與j不相連
  OK = 0;
  break;
 }

 if (OK)// 進入左子樹
 {
  x[i] = 1;
  cn++;
  Backtrack(i+1);
  x[i] = 0;
  cn–;
 }

 if (cn + n – i >= bestn)// 進入右子樹
 {
  x[i] = 0;
  Backtrack(i+1);
 }
}

int MaxClique(int **a, int v[], int n)
{
 Clique Y;

 //初始化Y
 Y.x = new int[n+1];
 Y.a = a;
 Y.n = n;
 Y.cn = 0;
 Y.bestn = 0;
 Y.bestx = v;
 Y.Backtrack(1);
 delete[] Y.x;
 return Y.bestn;
}     程序運行結果如圖:

 
 

     2、圖的m著色問題

     問題描述

       給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色,每個頂點著一種顏色。是否有一種著色法使G中每條邊的2個頂點著不同顏色。這個問題是圖的m可著色判定問題。若一個圖最少需要m種顏色才能使圖中每條邊連接的2個頂點著不同顏色,則稱這個數m為該圖的色數。求一個圖的色數m的問題稱為圖的m可著色優化問題。

     四色猜想:四色問題是m圖著色問題的一個特例,根據四色原理,證明平面或球面上的任何地圖的所有區域都至多可用四種、顏色來著色,並使任何兩個有一段公共邊界的相鄰區域沒有相同的顏色。這個問題可轉換成對一平面圖的4-著色判定問題(平面圖是一個能畫於平面上而邊無任何交叉的圖)。將地圖的每個區域變成一個結點,若兩個區域相鄰,則相應的結點用一條邊連接起來。多年來,雖然已證明用5種顏色足以對任一幅地圖著色,但是一直找不到一定要求多於4種顏色的地圖。直到1976年這個問題才由愛普爾,黑肯和考西利用電子計算機的幫助得以解決。他們證明瞭4種顏色足以對任何地圖著色。

 
 

     算法設計

     考慮所有的圖,討論在至多使用m種顏色的情況下,可對一給定的圖著色的所有不同方法。通過回溯的方法,不斷的為每一個節點著色,在前面n-1個節點都合法的著色之後,開始對第n個節點進行著色,這時候枚舉可用的m個顏色,通過和第n個節點相鄰的節點的顏色,來判斷這個顏色是否合法,如果找到那麼一種顏色使得第n個節點能夠著色,那麼說明m種顏色的方案是可行的。

     用m種顏色為無向圖G=(V,E)著色,其中,V的頂點個數為n,可以用一個n元組x=(x1,x2,…,xn)來描述圖的一種可能著色,其中,xi∈{1, 2, …, m},(1≤i≤n)表示賦予頂點i的顏色。例如,5元組(1, 2, 2, 3, 1)表示對具有5個頂點的無向圖(a)的一種著色,頂點A著顏色1,頂點B著顏色2,頂點C著顏色2,如此等等。如果在n元組X中,所有相鄰頂點都不會著相同顏色,就稱此n元組為可行解,否則為無效解。容易看出,每個頂點可著顏色有m種選擇,n個頂點就有mn種不同的著色方案,問題的解空間是一棵高度為n的完全m叉樹,這裡樹高度的定義為從根節點到葉子節點的路徑的長度。每個分支結點,都有m個兒子結點。最底層有mn個葉子結點。例如,表示用3種顏色為3個頂點的圖著色的狀態空間樹。如圖所示,對第i(i>=1)層上的每個頂點,從其父節點到該節點的邊上的標號表示頂點i著色的顏色編號。

 
 

    算法具體實現代碼如下:

[cpp]
//圖的著色問題 回溯法求解  
#include "stdafx.h"  
#include <iostream>  
#include <fstream>  
using namespace std; 
 
const int N = 5;//圖的頂點數  
const int M = 3;//色彩數  
ifstream fin("5d8.txt");  
 
class Color 

    friend int mColoring(int, int, int **); 
    private: 
        bool Ok(int k); 
        void Backtrack(int t); 
        int n,      //圖的頂點數  
            m,      //可用的顏色數  
            **a,    //圖的鄰接矩陣  
            *x;     //當前解  
        long sum;   //當前已找到的可m著色方案數  
}; 
 
int mColoring(int n,int m,int **a); 
 
int main() 

    int **a = new int *[N+1];   
    for(int i=1;i<=N;i++)     
    {     
        a[i] = new int[N+1];     
    }  
     
    cout<<"圖G的鄰接矩陣為:"<<endl; 
    for(int i=1; i<=N; i++)   
    {   
        for(int j=1; j<=N; j++)   
        {   
            fin>>a[i][j];       
            cout<<a[i][j]<<" ";     
        }   
        cout<<endl;   
    } 
    cout<<"圖G的著色方案如下:"<<endl; 
    cout<<"當m="<<M<<"時,圖G的可行著色方案數目為:"<<mColoring(N,M,a)<<endl; 
    for(int i=1;i<=N;i++)     
    {     
        delete[] a[i];    
    }  
    delete []a; 

 
void Color::Backtrack(int t) 

    if (t>n) 
    { 
        sum++; 
        for (int i=1; i<=n; i++) 
        cout << x[i] << " "; 
        cout << endl; 
    } 
    else 
    { 
        for (int i=1;i<=m;i++) { 
            x[t]=i; 
            if (Ok(t)) Backtrack(t+1); 
        } 
    } 

 
bool Color::Ok(int k)// 檢查顏色可用性  

    for (int j=1;j<=n;j++) 
    { 
        if ((a[k][j]==1)&&(x[j]==x[k])) //相鄰且顏色相同  
        { 
            return false; 
        } 
    } 
    return true; 

 
int mColoring(int n,int m,int **a) 

    Color X; 
 
    //初始化X  
    X.n = n; 
    X.m = m; 
    X.a = a; 
    X.sum = 0; 
    int *p = new int[n+1]; 
    for(int i=0; i<=n; i++) 
    { 
        p[i] = 0; 
    } 
    X.x = p; 
    X.Backtrack(1); 
    delete []p; 
    return X.sum; 

//圖的著色問題 回溯法求解
#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;

const int N = 5;//圖的頂點數
const int M = 3;//色彩數
ifstream fin("5d8.txt");

class Color
{
 friend int mColoring(int, int, int **);
 private:
  bool Ok(int k);
  void Backtrack(int t);
  int n,  //圖的頂點數
   m,  //可用的顏色數
   **a, //圖的鄰接矩陣
   *x;  //當前解
  long sum; //當前已找到的可m著色方案數
};

int mColoring(int n,int m,int **a);

int main()
{
 int **a = new int *[N+1]; 
    for(int i=1;i<=N;i++)   
    {   
        a[i] = new int[N+1];   
    }
 
 cout<<"圖G的鄰接矩陣為:"<<endl;
 for(int i=1; i<=N; i++) 
    { 
        for(int j=1; j<=N; j++) 
        { 
            fin>>a[i][j];     
            cout<<a[i][j]<<" ";   
        } 
        cout<<endl; 
    }
 cout<<"圖G的著色方案如下:"<<endl;
 cout<<"當m="<<M<<"時,圖G的可行著色方案數目為:"<<mColoring(N,M,a)<<endl;
 for(int i=1;i<=N;i++)   
    {   
        delete[] a[i];  
    }
 delete []a;
}

void Color::Backtrack(int t)
{
 if (t>n)
 {
  sum++;
  for (int i=1; i<=n; i++)
  cout << x[i] << " ";
  cout << endl;
 }
    else
 {
  for (int i=1;i<=m;i++) {
   x[t]=i;
   if (Ok(t)) Backtrack(t+1);
  }
 }
}

bool Color::Ok(int k)// 檢查顏色可用性
{
 for (int j=1;j<=n;j++)
 {
  if ((a[k][j]==1)&&(x[j]==x[k])) //相鄰且顏色相同
  {
   return false;
  }
 }
 return true;
}

int mColoring(int n,int m,int **a)
{
 Color X;

 //初始化X
 X.n = n;
 X.m = m;
 X.a = a;
 X.sum = 0;
 int *p = new int[n+1];
 for(int i=0; i<=n; i++)
 {
  p[i] = 0;
 }
 X.x = p;
 X.Backtrack(1);
 delete []p;
 return X.sum;
}     圖m可著色問題的解空間樹中內結點個數是。對於每一個內結點,在最壞情況下,用ok檢查當前擴展結點的每一個兒子所相應的顏色可用性需耗時O(mn)。因此,回溯法總的時間耗費是。程序運行結果如圖:

 


 

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。