| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1250.1 | Not all acyclic graphs are trees | COOKIE::PBERGH | Peter Bergh, DTN 523-3007 | Sun Jun 10 1990 12:47 | 24 |
| <<< Note 1250.0 by RIPPLE::ABBASI_NA >>>
-< detect a cycle in graph >-
>> ... ( this means that
>> if no cycle exist, it is a tree (right ?).
Wrong. If the arrows have directions:
NODE1
/\
/ \
/ \
/ \
V V
NODE2 NODE3
\ /
\ /
\ /
\ /
VV
NODE4
this is not a cyclic graph but it is not a tree, either. It is a directed
acyclic graph.
|
| 1250.2 | opps. its undirected edges | RIPPLE::ABBASI_NA | | Mon Jun 11 1990 03:38 | 2 |
| You'r right, I forgot to say the graph is undirected.
/naser
|
| 1250.3 | Still not a tree. | CADSYS::COOPER | Topher Cooper | Mon Jun 11 1990 11:45 | 16 |
| Well it might, *look* like a tree, but it might not, and in any case
it wouldn't *be* a tree according to the usual definition. A tree
is usually defined to be a *directed* graph, with all nodes but one
having in-degree 1, that single node (the root) having in-degree zero,
and such that for every nonroot node there exists a path from the root
to that node --- or a definition equivalent to that one.
Since your graph is *not* directed it cannot be a tree. You didn't
specify that the graph was connected so it might look like a forrest.
Interesting question (probably easy): Can an ordering be applied to
any connected, non-directed acyclic graph so that it forms a tree?
(equivalently: can an ordering be applied to any non-directed acyclic
graph so that it forms a forrest?).
Topher
|
| 1250.4 | | GUESS::DERAMO | Colorado Rocky Mountain high | Mon Jun 11 1990 12:33 | 15 |
| re .3
>> Interesting question (probably easy): Can an ordering be applied to
>> any connected, non-directed acyclic graph so that it forms a tree?
>> (equivalently: can an ordering be applied to any non-directed acyclic
>> graph so that it forms a forrest?).
Any finite, connected, acyclic non-directed graph can be
ordered so that it forms a tree.
For the infinite case, let the graph be the union of the successor
relation and its converse over the signed integers. It is connected
and acyclic but has no root.
Dan
|
| 1250.5 | | HPSTEK::XIA | In my beginning is my end. | Mon Jun 11 1990 13:03 | 17 |
| > Sequentially (one processor) a cycle could be detected in O(n**2) if
> one exists, right? ( at least in Polynomial time any way)
> but the hard one is to show it could be done in polylogarthmic time using
> polynomial processors.
Uh... I don't quite understand this, but doesn't the depth (or
breadth) first search give O(n)? (of course we are talking about
connected graph here?)
With n processors, I think what you do is to partition the graph into
connected subgraphs then give one to each processors, and then treat
each subgraph as a node (that will give you another graph with a lot
less node). Then you just keep doing the same thing again and again.
Well, this is just off the top of my head. I don't know if this is the
standard way of doing it.
Eugene
|
| 1250.6 | Depends on exactly what we are looking for. | CADSYS::COOPER | Topher Cooper | Mon Jun 11 1990 14:45 | 20 |
| RE: .5 (Eugene)
I started to reply that systematic search would be linear in the number
of edges, which is quadratic in the number of nodes. But I realized
that a tree has one fewer edges than nodes. A forest has k fewer
edges than nodes (where k is the number of trees in the forest).
If the job is to determine that a cycle exits, then the answer is
affirmative the moment we determine that there are at least as many
edges as nodes. With a suitable representation, we can count the
number of edges in n steps (n=number of nodes).
If we are assured that the graph is connected we are finished. If
we don't we can search for a cycle in time linear in the number of
edges, which is, at worst, linear in the number of nodes.
Detecting that a cycle is present is therefore linear in the number
of nodes even on a single processor. Finding the cycle(s) that you
know are there would seem to be a bit harder.
Topher
|
| 1250.7 | | HPSTEK::XIA | In my beginning is my end. | Mon Jun 11 1990 16:46 | 7 |
| re .6,
By the way, in projectie geometry, lines and points are really the same
thing, so it isn't really necessary to differentiate them when
discussing abstract properties such as O(n) and etc.
Eugene
|
| 1250.8 | I tried these methods | RIPPLE::ABBASI_NA | | Tue Jun 12 1990 02:33 | 58 |
|
regarding .5 (Eugene)
> With n processors, I think what you do is to partition the graph into
> connected subgraphs then give one to each processors, and then treat
> each subgraph as a node (that will give you another graph with a lot
> less node). Then you just keep doing the same thing again and again.
> Well, this is just off the top of my head. I don't know if this is the
> standard way of doing it.
Well, I went along the above lines, (divid and repeate..).
This how I tried to do it:
method 1) assign a processor to each node, every processor sends
its node ID, and all the received node ID to node it points to
(Ok so its directed graph). we stop when a processor sees its ID
as in the set of ID it receives from one the nodes that point to
it. Now to get the LOG n factor we have to use what is called
parallel prefix walk (important paradigm in parallel algorithms):
First phase we send to node 1 step ahead,
next every processor adjust the next pointer to := Next->next
like this (showing for one processor, every other processor also
jumps (1,2,4,8,16,.. ie. Log(n))
--------------------------------------------------------
/ \
----------------------------- \
/ \ \
------------- \ \
/ \ \ \
o------>o------->o-------->o------->o-------->o------->o---->o---->o
\ /
---
does this work ? ( I'll find out when I get back my corrected problem
next week !)
another method is to use randomized method:
(trying to come up with random based algorithms is really intersting
and you will not lose anything, sine at wrost you'll get the best
of determinstic method (right ?, since random algorithm is an instant
of determinstic)
assign a processor to a region in the graph by random, size of region
is (log n) number of nodes, every procssor search this reagion in
O( size of region) ie O(log n), if no cysle found by any processor
then we eliminate all those paths that have a leaf at the end from
all the regions (since they dont lead to cycle), this will reduce
the number of nodes, next pahse repeate the above by assigning new
regions to the processors. so what is the probablity that well find
a cycle after log(n) pahase ? I dont know, but I think it will be
greater than .5 , so we stop in O(log n * log n) or something like
close to that .
|
| 1250.9 | Not relevant. | CADSYS::COOPER | Topher Cooper | Tue Jun 12 1990 19:29 | 30 |
| RE: .7 (Eugene)
Maybe I'm missing something, but I don't see how projective geometry
applies.
If we are given a graph with some number of nodes and edges, we can
substitute it with a topological dual with an edge for each node
and vice versa. Any topological (or projective) property of the
first has a corresponding property for the second. But that doesn't
mean that the statements are the same for both -- there is a
transformation.
In particular, in the worst case, if a graph has N nodes, its dual
will have N� nodes. An algorithm which is O(N) on the nodes of the
dual corresponds (worst case) to an algorithm which is O(N�) on the
original. That is a real difference in complexity theory.
Here is a similar argument: I can encode a weighted, undirected graph
as a list of all complete paths through it. With sufficient
information included in the list elements the two representations are
equivalent -- anything I can say about one has a corresponding
statement about the other. A single scan of the list representation
will allow me to find the shortest path among them. Therefore I
can solve the TSP in linear time, and P=NP.
Needless to say this is false because the "N" used in the "linear"
version is exponential in the "N" used in the original problem (N =
number of cities, rather than paths).
Topher
|