Re: Help about Graphy Theory and Communication Networks plz..
- From: "Randy Poe" <poespam-trap@xxxxxxxxx>
- Date: 15 Nov 2005 15:23:30 -0800
xeyder wrote:
> Hi everyone..
> I need help about graph theory ( network problems) ..
>
> I have below problem . Does anyone know any existence algorithms or
> solutions to this problem ??
>
>
> The Problems is:
> " We can use graphs to represent a communication network. In such
> graphs, the vertices
> represent communication stations and the edges represent communication
> links. Critical points are the vertices whose failure will result in
> the network
> becoming disconnected. Similarly, critical links are the edges whose
> failure will result a
> loss of communication. Sub components are the graphs which don't
> contain no critical
> points.
>
> In this experiment, you are supposed to develop a program that
> generates graph structure
> of a communication network given and implements some graph algorithms
> which help
> managing the network.
> For the given a communication network as an undirected graph G(V,E),
Your first problem is to figure out a representation. A pretty standard
one for graphs is an adjacency matrix: If there are N vertices, then
the adjacency matrix is an N x N matrix of 0's and 1's where
a_ij = 1 if and only if node i is adjacent to node j. An undirected
graph
has a symmetric adjacency matrix (a_ij = a_ji). You can also
include edge weights by having nonzero values other than 1.
The 1's in column (or row) i tell you the neighbors of node i. The
sum of column (or row) i is the degree of i.
Now you can think of how different operations would be reflected in
the adjacency matrix. For instance, deleting a node corresponds to
zeroing row i and column i. Deleting edge ij corresponds to zeroing
elements a_ij and a_ji.
> write a program
> that will do the following :
There might be a more efficient way, but I suggest something like
this: write a subprogram that can start at any node, find all its
neighbors, find all THOSE nodes' neighbors, etc, until you find
all the nodes connected to a given node by any path.
> a) Find all critical points in G.
To test if a node is a critical point: delete it, then use the above
subprogram on the neighbors of that node: are they still
connected?
> b) Find all critical edges in G.
Similar to above, but with edges.
> c) Find the sub components in G."
That's what's left when you delete the critical points and edges.
- Randy
.
- References:
- Prev by Date: Re: More of an Algorithems question
- Next by Date: Re: Prove of sylow p-subgroup
- Previous by thread: Help about Graphy Theory and Communication Networks plz..
- Next by thread: Re: monic polynomials
- Index(es):
Relevant Pages
|
