@siddharam: i think the above example is isomorphic............ because in isomopic we check for the degree of each node in one tree to the corresponding degree of another tree is present or not .....
like eg:- p-----q------r-------s is isomorphic with a------b------c-------d On Thu, Sep 15, 2011 at 10:15 AM, siddharam suresh <siddharam....@gmail.com>wrote: > as per your example > > preorder inorder > tree1: ab ba > tree2: ab ab > > both are not isomorphic. > > its easy to extend preorder/DFS to > replace two calls to children with for loop considering the graph is > N-array tree. > > > > Thank you, > Sid. > > > > On Wed, Sep 14, 2011 at 5:50 PM, bugaboo <bharath.sri...@gmail.com> wrote: > >> @siddharam: >> >> Performing inorder and pre/postorder will still have false positives. >> >> Consider 2 trees one with root node "a" with node "b" as left child, >> another tree with root node "a" with node "b" as its right child. >> >> Anyway, for binary trees, I am aware of a recursive solution to find >> out similarity or isomorphism. Not sure how this extends for a graph. >> Always thought a DFS and/or BFS should suffice but apparently not. >> >> On Sep 14, 1:43 am, siddharam suresh <siddharam....@gmail.com> wrote: >> > bharath.sriram, >> > perform inorder traversal and peorder/postorder traversal on both tree >> then >> > compare both the result of two tree. >> > Thank you, >> > Sid. >> > >> > >> > >> > >> > >> > >> > >> > On Wed, Sep 14, 2011 at 10:22 AM, bugaboo <bharath.sri...@gmail.com> >> wrote: >> > > This brings up another interesting question. How do you find out if 2 >> > > graphs are identical? (By identical, I mean exact similarity and NOT >> > > isomorphism). Clearly, checking to see if both the DFS traversal and >> > > BFS traversal match seem to have false positives as Bharathkumar >> > > mentioned. >> > >> > > On Sep 13, 12:50 am, bharatkumar bagana <bagana.bharatku...@gmail.com >> > >> > > wrote: >> > > > @nishaanth: >> > > > ex: >> > > > 1 >> > > > 2 3 >> > > > 4 >> > > > 5 >> > > > bfs:12345 >> > > > dfs:12345 >> > > > branching factor of this tree is not 1 .......... >> > >> > > > On Tue, Sep 13, 2011 at 9:38 AM, nishaanth <nishaant...@gmail.com> >> > > wrote: >> > > > > yes branching factor should be 1. it can be not equal to 1 only >> for the >> > > > > penultimate node. by penultimate node i mean whose children are >> the >> > > leaves >> > > > > of the tree. rest all cases it should be 1. >> > >> > > > > On Tue, Sep 13, 2011 at 9:24 AM, siddharam suresh < >> > > siddharam....@gmail.com >> > > > > > wrote: >> > >> > > > >> cant say if there more than one leaf element >> > > > >> still both the algo give same result >> > > > >> Thank you, >> > > > >> Sid. >> > >> > > > >> On Tue, Sep 13, 2011 at 7:52 AM, Sundi <sundi...@gmail.com> >> wrote: >> > >> > > > >>> if the dfs and bfs of a graph is same, does it mean that if the >> > > > >>> branching factor of a graph is one? >> > >> > > > >>> a>b>c>d >> > >> > > > >>> example: both dfs abd bfs are same here.... >> > >> > > > >>> -- >> > > > >>> You received this message because you are subscribed to the >> Google >> > > Groups >> > > > >>> "Algorithm Geeks" group. >> > > > >>> To post to this group, send email to algogeeks@googlegroups.com >> . >> > > > >>> To unsubscribe from this group, send email to >> > > > >>> algogeeks+unsubscr...@googlegroups.com. >> > > > >>> For more options, visit this group at >> > > > >>>http://groups.google.com/group/algogeeks?hl=en. >> > >> > > > >> -- >> > > > >> You received this message because you are subscribed to the >> Google >> > > Groups >> > > > >> "Algorithm Geeks" group. >> > > > >> To post to this group, send email to algogeeks@googlegroups.com. >> > > > >> To unsubscribe from this group, send email to >> > > > >> algogeeks+unsubscr...@googlegroups.com. >> > > > >> For more options, visit this group at >> > > > >>http://groups.google.com/group/algogeeks?hl=en. >> > >> > > > > -- >> > > > > S.Nishaanth, >> > > > > Computer Science and engineering, >> > > > > IIT Madras. >> > >> > > > > -- >> > > > > You received this message because you are subscribed to the Google >> > > Groups >> > > > > "Algorithm Geeks" group. >> > > > > To post to this group, send email to algogeeks@googlegroups.com. >> > > > > To unsubscribe from this group, send email to >> > > > > algogeeks+unsubscr...@googlegroups.com. >> > > > > For more options, visit this group at >> > > > >http://groups.google.com/group/algogeeks?hl=en. >> > >> > > > -- >> > >> > > > **Please do not print this e-mail until urgent requirement. Go >> Green!! >> > > > Save Papers <=> Save Trees >> > > > *BharatKumar Bagana* >> > > > **http://www.google.com/profiles/bagana.bharatkumar< >> > >http://www.google.com/profiles/bagana.bharatkumar> >> > > > * >> > > > Mobile +91 8056127652* >> > > > <bagana.bharatku...@gmail.com> >> > >> > > -- >> > > You received this message because you are subscribed to the Google >> Groups >> > > "Algorithm Geeks" group. >> > > To post to this group, send email to algogeeks@googlegroups.com. >> > > To unsubscribe from this group, send email to >> > > algogeeks+unsubscr...@googlegroups.com. >> > > For more options, visit this group at >> > >http://groups.google.com/group/algogeeks?hl=en. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
