yea. it's connected. i tried the spanning trees too, but I had to look ob how the trees differ, depending on how they are build.
I've just one small (opticial) problem remaining. if I plot the tree all vertices are ordert on each level but beacause of this many lines are crossing. I dont need to have them sorted, but it would be nice to have as less as possible edges crossing. greatz Johannes Am 05.02.2011 16:02, schrieb Luiz Felipe Martins: > Oh, I was imprecise. If it has no loops, it is a forest. So you have to get > a spanning tree for each component. > > On Sat, Feb 5, 2011 at 10:01 AM, Luiz Felipe Martins < > luizfelipe.mart...@gmail.com> wrote: > >> Sorry, I didn't get the beginning of the thread, but if you need the graph >> without loops, it is a tree. So, you can compute a maximal spanning tree of >> the graph, and see if you get the whole graph together. This will also tell >> you what edges to remove, if the graph is not a tree. Of course, the maximal >> spanning tree is not unique, so the set of edges to be removed will not be >> uniquely determined. >> >> Sorry if this was already mentioned, or if it is actually unrelated to what >> you need. >> >> >> On Sat, Feb 5, 2011 at 7:37 AM, Johannes <dajo.m...@web.de> wrote: >> >>> thnx for your answers. >>> >>> I'm dealing with an undirectred graph. In the beginning I have a given >>> number of vertices (53 in my case now) and a list or relations between >>> them. All I do is adding a new edge (a <-> b) if a is in relatoin to be. >>> My problem is, i dont know form the beginning if it's loopsless. but I >>> need to have it without any loops. >>> >>> greatz Johannes >>> >>> >>> >>> Am 05.02.2011 07:53, schrieb Nathann Cohen: >>>> >>>>> >>>>> how can i add a new edge (a->b) to a given graph G (n.n. connected), >>>>> just in the case that there is no path (a -> ... -> b) before? >>>> >>>> >>>> >From your question, I can not infer whether you are dealing with >>> directed or >>>> undirected graphs. So just in case : >>>> >>>> - If your graph is undirected and there are no paths between two >>> vertices a >>>> and b, it means that a and b lie in different connected components. >>> Given a >>>> graph g, you can obtain the list of connected components with >>>> g.connected_components(). It is a list of list (a partition of the >>>> vertices). Two vertices are joined by a path if and only if they are in >>> the >>>> same connected component (in a Graph, "being linked by a path" is an >>>> equivalence relation). As soon as you add an edge between two connected >>>> components, you "merge" them :-) >>>> >>>> http://en.wikipedia.org/wiki/Connected_component_(graph_theory) >>>> >>>> - If your graph is directed, there is no equivalence relation anymore, >>>> because it is not even reflexive. You may have a path from a to b, but >>> no >>>> path from b to a. We are then talking about strongly connected >>> components >>>> (g.strongly_connected_components()), g.is_strongly_connected()). If you >>> have >>>> two strongly conected components A and B in your graph, [ (adding one >>> arc >>>> from any vertex of A to any vertex of B) AND (adding one arc from any >>> vertex >>>> of B to any vertex of A) ] will ensure that for any pair of vertices in >>> A U >>>> B there exist paths in both directions. Pretty often you just need to >>> add >>>> ONE arc instead of two. You can get this information with the method >>>> strongly_components_digraph >>>> >>>> Strongly connected components : >>>> http://en.wikipedia.org/wiki/Strongly_connected_component >>>> >>>> In any case, you will often have a HUGE number of paths in your graphs, >>>> while checking whether there exists a path from a to b is almost >>>> instantaneous. You can do it manually with g.distance(a,b) <= g.order() >>> or >>>> len(g.shortest_path(u,v)) > 0. The methods connected_components() or >>>> strongly_connected_components() actually test all the pairs at the same >>>> time, which is faster than actually computing shortest paths or >>> distances >>>> between all pair. These methods are the most efficient you will find in >>> Sage >>>> : they are very simple and implemented in Cython, as they appear very, >>> very >>>> often in graph algorithms. >>>> >>>> (if I missed your point, please also tell me whether you are dealing >>> with >>>> graphs/digraphs) :-) >>>> >>>> Nathann >>>> >>> g >>> >>> -- >>> To post to this group, send email to sage-support@googlegroups.com >>> To unsubscribe from this group, send email to >>> sage-support+unsubscr...@googlegroups.com<sage-support%2bunsubscr...@googlegroups.com> >>> For more options, visit this group at >>> http://groups.google.com/group/sage-support >>> URL: http://www.sagemath.org >>> >> >> > -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
