Bridges in an Undirected Graph

Question

A bridge can only exist between two articulation points or between an articulation point and a node with degree 1. This is just an observation because if a vertex is articulation point then simply disconnecting from that node will give us bridges only.

Please tell me if this is true or false.

Answer 1

/*A sample file should contain edges as follow
1,2
2,3
4,5
5,3
Output will give the set of bridge nodes
*/
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
typedef struct graph
{
  int node;
  struct graph *next;
}graph;
void init(int group[],int index[],graph *g[]);
void create_graph(graph *g[],int node1,int node2,int group[],int index[],int max_nodes);
int max(int a,int b);
int min(int a,int b);
void display(graph *g[],int group[],int max_nodes);
int query(graph *g[],int group[],int max_nodes,int first,int second);
void delete_node(graph *g[],int node1,int node2,int group[],int index[],int max_nodes);
int team=0;
int main()
{
  char filename[50],ch;
  int nodes[MAX][2],temp=0,node1,node2,group[MAX],index[MAX],max_nodes=0,i;
  FILE *fp;
  graph *g[MAX],*p;
  init(group,index,g);
  printf("Enter the filename - ");
  scanf("%s",filename);
  fp=fopen(filename,"r");
  if(fp==NULL)
  {
    printf("File does not exist");
    exit(1);
  }
  while(1)
  {
    ch=fgetc(fp);
    if(isdigit(ch))
    temp=temp*10+(ch-48);
    else
    {
      if(ch!=','&&ch!='\n'&&ch!=EOF)
      exit(1);
      if(ch==',')
      node1=temp;
      else
      {
        node2=temp;
        if(node1>max_nodes)
        max_nodes=node1;
        if(node2>max_nodes)
        max_nodes=node2;
        if(node1!=node2&&node1>0&&node2>0)
        create_graph(g,node1,node2,group,index,max_nodes);
      }
      temp=0;
    }
    if(ch==EOF)
    {
      break;
    }
  }
  display(g,group,max_nodes);
  temp=0;
  fclose(fp);
  fp=fopen(filename,"r");
  printf("Set of bridges existing - \n\n");
  while(1)
  {
    ch=fgetc(fp);
    if(isdigit(ch))
    temp=temp*10+(ch-48);
    else
    {
      if(ch!=','&&ch!='\n'&&ch!=EOF)
      exit(1);
      if(ch==',')
      node1=temp;
      else
      {
        node2=temp;
        if(node1>max_nodes)
        max_nodes=node1;
        if(node2>max_nodes)
        max_nodes=node2;
        if(node1!=node2&&node1>0&&node2>0)
        delete_node(g,node1,node2,group,index,max_nodes);
      }
      temp=0;
    }
    if(ch==EOF)
    {
      break;
    }
  }
  return 0;
}
void init(int group[],int index[],graph *g[])
{
  int i;
  graph *p=NULL;
  for(i=0;i<MAX;i++)
  {
    group[i]=index[i]=0;
    g[i]=(graph *)malloc(sizeof(graph));
    g[i]->node=0;
    g[i]->next=NULL;
  }
}
void create_graph(graph *g[],int node1,int node2,int group[],int index[],int max_nodes)
{
  int temp_index,other_index,i,minimum;
  int stack[MAX],stack_index=0;
  graph *p;
  p=g[node1];
  if(p->next)
  {
    p=p->next;
    while(p)
    {
      if(p->node==node2)
      return;
      p=p->next;
    }
  }
  if(g[node1]->node<g[node2]->node)
  {
    temp_index=node1;
    other_index=node2;
  }
  else
  {
    temp_index=node2;
    other_index=node1;
  }
  p=g[temp_index];
  p->node=p->node+1;
  while(p->next!=NULL)
  p=p->next;
  p->next=(graph *)malloc(sizeof(graph));
  p=p->next;
  p->node=other_index;
  p->next=NULL;
  p=g[other_index];
  p->node=p->node+1;
  while(p->next)
  p=p->next;
  p->next=(graph *)malloc(sizeof(graph));
  p=p->next;
  p->node=temp_index;
  p->next=NULL;
  if(group[temp_index]==group[other_index]&&group[temp_index]==0)
  {
    {
      team++;
      group[temp_index]=group[other_index]=team;
    }
  }
  else
  {
    if(group[temp_index]==0)
    {
      group[temp_index]=group[other_index];
    }
    {
      minimum=min(group[temp_index],group[other_index]);
      group[temp_index]=max(group[temp_index],group[other_index]);
      for(i=1;i<=max_nodes;i++)
      {
        if(group[i]==minimum)
        group[i]=max(group[temp_index],group[other_index]);
      }
    }
  }
}
int max(int a,int b)
{
  if(a>b)
  return a;
  return b;
}
int min(int a,int b)
{
  if(a<b)
  return a;
  return b;
}
void display(graph *g[],int group[],int max_nodes)
{
  int i;
  graph *p;
  printf("Graph\n");
  printf("Id\tGrp\tNodes\n");
  for(i=1;i<=max_nodes;i++)
  {
    printf("%d\t%d\t%d",i,group[i],g[i]->node);
    p=g[i]->next;
    while(p)
    {
      printf(" %d",p->node);
      p=p->next;
    }
    printf("\n");
  }
  printf("\n\n");
}
int query(graph *g[],int group[],int max_nodes,int first,int second)
{
  if(group[first]==group[second])
  return 1;
  else
  return 0;
}
void delete_node(graph *g[],int node1,int node2,int group[],int index[],int max_nodes)
{
  graph *p=NULL;
  int i,temp,stack_index=0,stack[MAX];
  p=g[node1];
  while(p->next->node!=node2&&p->next)
  p=p->next;
  if(p->next)
  {
    p->next=p->next->next;
    g[node1]->node=g[node1]->node-1;
  }
  p=g[node2];
  while(p->next->node!=node1&&p->next)
  p=p->next;
  if(p->next)
  {
    p->next=p->next->next;
    g[node2]->node=g[node2]->node-1;
  }
  team++;
  group[node2]=team;
  stack_index=0;
  temp=node2;
  p=g[temp]->next;
  while(p)
  {
    stack[stack_index++]=p->node;
    p=p->next;
  }
  for(i=0;i<stack_index;i++)
  {
    if(group[stack[i]]!=team)
    {
      group[stack[i]]=team;
      p=g[stack[i]]->next;
      while(p)
      {
        stack[stack_index++]=p->node;
        p=p->next;
      }
    }
  }
  if(query(g,group,max_nodes,node1,node2)==0)
  printf("%d %d\n",node1,node2);
  create_graph(g,node1,node2,group,index,max_nodes);
}

Answer 2

"The key issue is determining how the reachability relation impacts whether vertex v is an articulation vertex. There are three cases: • Root cut-nodes – If the root of the DFS tree has two or more children, it must be an articulation vertex. No edges from the subtree of the second child can possibly connect to the subtree of the first child. • Bridge cut-nodes – If the earliest reachable vertex from v is v, then deleting the single edge (parent[v], v) disconnects the graph. Clearly parent[v] must be an articulation vertex, since it cuts v from the graph. Vertex v is also an articulation vertex unless it is a leaf of the DFS tree. For any leaf, nothing falls off when you cut it. • Parent cut-nodes – If the earliest reachable vertex from v is the parent of v, then deleting the parent must sever v from the tree unless the parent is the root." - The algorithm design manual by Steve Skiena

Answer 3

In an undirected graph, a bridge can only exist between two articulation points. That goes straight from the definitions:

• Bridge is an edge, such that removing it from the graph increases the number of connected components.
• If you remove any of its endpoints, you therefore increase the number of connected components as well, and that's exactly the definition of articulation point.

I'm not sure what you mean with the part or between an articulation point and a node with out-degree 0. What would out-degree mean in an undirected graph?

Here are nice slides on Tarjan's algorithm, including its usage for detecting bridges and articulation points in graphs.