stould's blog

By stould, 7 years ago, In English,
I'm reading about bipartite graphs, but I can't implement It....
I now:
G[V,E]
For each V[white], their friends must to be V[black], and Each friend V[black] must to have friends V[white].

Can you help-me sending some articles about this ?

P.S.: The article would have to be in english please.

I'm reading about it to solve: http://br.spoj.pl/problems/MESA/

Translated to english by google translate:
http://translate.google.com/translate?hl=pt-BR&sl=pt&tl=en&u=http%3A%2F%2Fbr.spoj.pl%2Fproblems%2FMESA%2F
 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You should put your links within the link tags, also, a Bipartite graph doesn't contain odd-length cycles and is bi-colorable, you can try to bi-colorate your graph in a DFS, with the trick of different number for the colors in the visited array.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you give me more information?

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Here is Link with the proofLink

      And if you want something more practical:

      bool dfs(int node, int c) {
          if(color[node] != 0) {
              if(color[node] == c) {
                  return true;
              } else {
                  return false;
              }
          }
          color[node] = c;
          for(int i = 1; i <= n; i++) if(gr[node][i] == 1) {
              if(!dfs(i, -c)) {
                  return false;
              }
          }
          return true;
      }
      

      If you're using an adjacency and the graph is 1-> based, it's just call:

      dfs(1, 1);
      
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Bipartite graph could be found by using DFS or BFS. Just run dfs from any vertex and let's take one more variable cur which switches each time(such as 1 and 2). And when two vertices have the same "color", then this graph is not bipartite. It is better to show code:

bool bipartite = true;
int a[MaxN][MaxN], color[MaxN];

void dfs(int v, int cur){
  mark[v] = true;
  color[v] = cur; // color this vertex as cur
  for (int i = 0; i < n; i++)
     if (a[v][i] == 1){ // if there is edge between v and i
         if (color[i] == cur) { // if color of vertex i is equal to color of v, that is cur
               bipartite = false; // graph is definitely not bipartite, so return
               return;
         }
         if (!mark[i]) dfs(v, cur==1?2:1); // continue dfs
     }
};

int main(){
...
dfs(0, 1); 
cout << bipartite;
...
}

Then, if graph is bipartite, all vertices colored with 1 are in one group and with color 2 is in another respectively.

Try to debug this program and try to understand and analyze. It is obviously that there is no edge between two vertices from the same group.

Sorry for my poor English)

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your solution. I have some questions regarding it

    where is "mark" defined and what is the usage of this array?

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      mark[] is an array of booleans which can be true or false. If mark[i]==true then it means that we have already visited vertex i, otherwise we haven't visited it yet. May be I did not understand your question? Sorry for my poor English :)

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you for your fast reply :)

        I have another question: In which line in the above code the variable ' v ' changes its value? it is always set to zero. Is that right?