 | | From: | Joe | | Subject: | two questions about unicyclic graph | | Date: | 17 Jan 2005 06:56:11 -0800 |
|
|
 | Hello,
I have two problems when dealing with unicyclic graph:
1. a linear algorithm to find the centre of a unicyclic graph
2. a linear algorithm to judge whether two unicyclic graphs are
isomorphic
I have thought about it for several days but cannot get a good answer,
so anybody could give me some hint or help ?
|
|
| | From: | Matt Timmermans | | Subject: | Re: two questions about unicyclic graph | | Date: | Fri, 21 Jan 2005 23:22:28 -0500 |
|
|
| "Joe" wrote in message
news:4db7e4f7.0501170656.7875c149@posting.google.com...
> Hello,
>
> I have two problems when dealing with unicyclic graph:
>
> 1. a linear algorithm to find the centre of a unicyclic graph
> 2. a linear algorithm to judge whether two unicyclic graphs are
> isomorphic
1. A unicyclic graph is a forest of trees rooted in the cycle. The center
is the set of roots of minimum height trees. Just find the cycle, and then
measure the height of each tree formed by the remaining edges.
2. Let the hash of a tree be the sum of the SHA-1 hashes of its subordinate
subtrees. Find the cycle in each graph and then, starting at the leaves
(vertices with degree 1), calculate the hash of each tree rooted in the
cycle. Get the lists of hashes around each cycle, and then verify that they
match under an appropriate cyclic shift, possibly with one of them reversed.
--
Matt
|
|
| | From: | sandey | | Subject: | Re: two questions about unicyclic graph | | Date: | 18 Jan 2005 04:18:33 -0800 |
|
|
| Hi,
Can you please explain what is the centre of a unicycle ?
thank you
Sandeep Dey
|
|
