Have you tried google? For (1), delete that particular edge and test whether the resulting graph is connected (i.e., do a depth-first search). This solution is optimal if you want to check whether removing a particular edge disconnects the graph. In the slightly more general case in which you want to check whether removing any one edge disconnects the graph -- that is, whether the graph is 2-edge-connected -- there is a linear time max flow solution that is slightly less obvious.
For (2), I never thought about this problem myself, but google had reasonable solutions. Here is one: http://portal.acm.org/citation.cfm?id=1187436.1216582 The description in (3) is too vague for me (this is usually the case for real problems that show up in practice). Also, why are you using graph-theoretic terms within quotations? Are you using those terms in a non-standard way? If this is the case, it would help if you would define them first. On Feb 5, 5:27 pm, Jake <[EMAIL PROTECTED]> wrote: > Hey, > I have a couple questions concerning graph theory. > > 1) If I have a connected graph G(V,E), how can I determine if the > removal of a particular graph edge leaves the remaining graph still > "connected"? I mean specifically, how do you test for this in a fast > way? > > 2) Is there any robust free-ware / algorithms / psuedocode for > identifying the cycle basis > (loops) for a sparse undirected, unweighted graph that has a > reasonable complexity? > > 3) The real problem. My graph actually represents local topological > connections between a surface mesh tessalation of triangular cells. > The vertices of my graph are the triangles. The edges of my graph are > the topological edges which connect exactly 2 triangles. I need to > partition the edges of the graph into its spanning tree edge space > and > it independent loop space (sum of loops + tree edges = total no. of > graph edges). Based on my topology, I can easily find the "local" > loops which "cycle" around the topological vertices of the mesh - and > these comprise the vast majority of the total loops. But how can I > quickly find the reamining "global" loops which could be present due > to genuses or holes in the mesh? These don't necessarily have to be > minimal if that would ease the complexity requirement. We call this a > loop-tree decomposition. Can anybody offer some assistance here > to help a non-graph theory expert? > > Can anybody out there point me in the right direction? > Thanks --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
