Laynetworks  
Web laynetworks.com Google
Home | Site Map | Tell a friends
Management Tutorials
Download
Tutorials
History
Computer Science
Networking
OS - Linux and Unix
Source Code
Script & Languages
Protocols
Glossary
IGNOU
Quiz
About Us
Contact Us
Feedback
 
Sign up for our Email Newsletter
 
Get Paid for Your Tech Turorials / Tips

 

 

Home > Computer Science >Computer Fundamentals
 
CS 01 CS 02 CS 03 CS 04 CS 05 CS 06 CS 07 CS 08 CS 09 CS 10 CS 11 CS 12 CS 13 CS 14 CS 15 CS 16 CS 17
Page : 1 2
Computer Fundamentals
 

2) Consider a directed acyclic graph (dag) with ‘e’ arcs and with two distinguished vertices ‘s’ to ‘t’. By maximal, we mean no additional path may be added, but it doesnot mean that it is the largest size such set.

SOLUTION :

In this problem one should look for all those nodes which have path from the starting vertex and from the ending vertex. This can be done by the adjacency matrix.

The following steps give brief explanation of the acyclic graph stating with its diagram :

Step 1 Make and Adjacency matrix.

Step 2 Look for all those vertices which node have a path from the starting node S.

Step 3 Now look for the same thing for the node T.

Step 4 Check for the repetitions if any.

The start node is S and end node is T.

In the following diagram all the nodes are connected to the S but all other nodes except the 1st S is not connected to the final node T.

ALGORITHM – O(e) To find a maximal set of vertex disjoint paths from ‘S’ to ‘T’

Steps
Make a adjacency matrix.
Count number of arcs or edges connected to any vertex.
Traverse the list if the no. of edges in any particular node is zero.
Count that node, the final outcome will contains all the nodes that are disjoint.
To explain the above steps, the following examples clarifies the O(e) algorithm :

Suppose that the number of nodes in the graph is constant :

i.e. arcs may be added or deleted but nodes may not.

# define MAXNODES 50

Struct node{
/* information associated with each node */
};

Struct arc{
Int adj; /* information associated with each arc */
};

Struct graph{
Struct node nodes[MAXNODES];

Struct arc arcs[MAXNODES] [MAXNODES];
};

Struct graph g;

Int adj [MAXNODES] [MAXNODES];

Void Join (int adj [ ] [MAXNODES], int node1, int node2)

{

adj [node1] [node2] = TRUE;

} /* end join */

int adjacent (int adj [ ] [MAXNODES], int node1, int node2)

{

return ((adj[node1] [node2]==TRUE)?TRUE:FALSE);

} /* end adjacent */

Each node of the graph is represented by an integer between O and MAXNODES-1 and the array field nodes represents the appropriate information assigned to each node. The array field arcs is a two dimensional array representing every possible ordered pair of nodes.

TOP
Page : 1 2
 
Donation | Useful links | Link to Laynetworks.com | Legal | SharePoint Development
Copyright © 2000-2010 Lay Networks All rights reserved.