無向グラフが木であるかどうかを調べる

Question

私は、無向グラフと無向グラフについて研究しました。私のアプローチは、DFSアルゴリズムを使用することです。私はvisitedM[iVertices]がtrueであるか、またはノードが2回訪問されたときにはそれがツリーではないことを意味します。私はまた、グラフが次の定理を使用する木かどうかを決定します。

Theorem: Any connected graph with n vertices and n-1 edges is a tree 

私のコードは、各エッジがソース頂点と目的地頂点と一行上に記載されている見ることができるように

6 7 
1 2 
1 5 
1 6 
2 5 

以下のようにファイルから頂点と辺の数の数を読み取ることによって初期化され。頂点は1から始まります。エッジは無向であり、最小の頂点IDで始まるファイルには が一度リストされます。たとえば、エッジ2-5,5-2の場合、ファイルは2-5しかありません。

私の問題は、ノードのメモリを割り当てる必要があるかどうか、ノードをグラフに挿入する方法、DFSコードからの私の返信方法をツリーではないことです。また、私はvoid dfsを訪問先の頂点の数を返すint関数として持っています。 int dft(grapg *g, int iV, int VisitedM[])。関数はvoid DFSと似ていますが、visitedM[iV],visitedM[iV] = TRUEの場合は0 を返し、iCountを返します。 私はまた私のデータ構造が乱雑であると推測します。

#define MAX_VERTICES 100 
typedef struct EdgeNode 
{ 
    int y; 
    int w;   //weight 
    int iVertex  //susbcript in vertexM for TO Vertex 
    struct EdgeNode *pNextEdge; 
}EdgeNode; 

typedef struct Vertex 
{ 
    char szLabel[100 +1 ]; 
    EdgeNode *successorList; 
}Vertex; 

typedef struct 
{ 
    int iNumVertices; 
    int iNumEdges; 
    int iDirected; 
    Vertex vertexM[MAX_VERTICES +1]; 

    int iParent[MAX_VERTICES + 1]; 
    int iVisitedM[MAX_VERTICES + 1]; 

    int degree[MAX_VERTICES + 1]; 
    EdgeNode *edge[MAX_VERTICES +1]; 
}GraphImp; 
typedef GraphImp *Graph; 


    int main(int argc, char *argv[]) 
    { 
     FILE *pFile; 
     Graph graph; 
     char szInputBuffer[100]; 
     int numEdges, numVertices; 
     pFile = fopen("a.txt","r"); 

     if(pFile == NULL) 
     { 
      printf("FILE DOES NOT EXIST \n"); 
      return; 
     } 
     //reads file until EOF 
     while(fscanf(pFile, "%d%d", &graph.iVertices, &graph.iEdges) != EOF) 
     { 
      //printf is to track the input from file 
      printf("num of vertices: %d \n num of edeges: %d \n",graph.iVertices, graph.iEdges); 
     } 

     fclose(pFile); 
    } 
      void dft(Graph *g, int iV, int visitedM[]) 
     { 
      EdgeNode *e; 
      if(visitedM[iV]) 
       return; 
      for(e = g->vertexM[iV].sucessorList; e!= NULL; e = e->pNextEdge) 
      { 
       dft(g, e->iVertex, visitedM); 
      } 
     } 

Answer 1

私はあなたに少し違うアプローチを与えます。

質問{{6,7}, {1,2}, {1,5}, {1,6}, {2,5}}の辺の集合を考えると、5つの頂点{1,2,5,6,7}と5つの辺があります。定理によれば、5つの頂点を有するグラフは4つの辺を持たなければならないので、グラフは木ではないとすぐに結論づける。

問題を少し難しくするには、エッジの1つを削除して、{{6,7}, {1,2}, {1,6}, {2,5}}のままにします。今、私たちは正しい数の辺を持っているので、定理によれば、はグラフが接続されていることを証明するだけです。これは、グラフに色を付けることによって行うことができます。

---

、グラフを着色エッジは、2つの無着色の頂点を接続する場合は、これらの3つのルール

• を実装し、エッジが無色頂点に着色された頂点を接続する場合、それらの頂点に新しい色
• を与えることエッジが2つの異なる色の頂点を接続している場合は、無色の頂点に色を割り当てる

すべての頂点が同じ色で終わると、グラフが接続されます。

---

次の表は、各エッジが処理されるにつれて色の割り当てがどのように変化するかを示しています。番号0最初のエッジ{6,7}は、頂点6及び7に新しい色を割り当てることにより、第2のエッジ{1,2}を示し

開始時

 |  color assignments 
vertex | start {6,7} {1,2} {1,6} {2,5} 
-------+------------------------------- 
    1 | 0  0  2  1  1 
    2 | 0  0  2  1  1 
    3 | 0  0  0  0  0 
    4 | 0  0  0  0  0 
    5 | 0  0  0  0  1 
    6 | 0  1  1  1  1 
    7 | 0  1  1  1  1 

、頂点の全ては無着色であり、頂点1と2に新しい色を割り当てます。3番目のエッジ{1,6}は異なる色を持つ頂点を結びつけるので、色2のすべての頂点が色1に変更されます。最後のエッジ{2,5}は、着色された頂点と無色の頂点を結びつけます。頂点5

すべての辺が処理された後、色付きの頂点はすべて同じ色になり、グラフが接続されます。また、辺の数は頂点の数より1少ない。したがって、グラフはツリーです。