Hello everyone! Just a side question to this discussion and after looking at #8395.
http://trac.sagemath.org/sage_trac/ticket/8395 Given a graph G, with a loop at vertex j. What is the convention followed in sage for entry j,j of the adjacency matrix? sage: G=Graph({0:[0],1:[1]},allow_loops=True);G.am() [1 0] [0 1] Just wandering if it is a bug or a feature. Cheers, Fidel On Apr 24, 9:25 pm, ablondin <alexandre.blondin.ma...@gmail.com> wrote: > Hello, everyone ! > > If I may add some comments. > > N. O'Trealy is right when he says that the best approach is to look > at the mathematical definitions of objects. On the other hand, one > needs to be careful. For instance, the set E of a graph G = (V,E), a > directed graph G = (V,E) and a multigraph G = (V,E) are all different. > For a directed graph, E is a subset of the cartesian product of V. > For an undirected one, E is a subset of all unordered pairs of V. > For a multigraph, E is a submultiset of the cartesian product of V > (multisets are unordered collections of elements with possible > repetition, also sometimes called bags). > Therefore, the degree function is well defined for all three kinds > of graphs, but has different meaning. A vertex having only a > self-loop in a directed graph will have in-degree 1, out-degree 1 and > degree 2. For undirected graph, in general, we do not define > in- and out-degree, just degree, which would be 2 for a self-loop and > it seems reasonable to set the in- and out-degree both to 2 as well. > As for multigraphs (which may be directed or not), the in-, out- and > normal degree are obtained with the definitions: > in_degree(v) = #{ u | (u,v) \in E} > out_degree(v) = #{ u | (v,u) \in E} > degree(v) = in_degree(v) + out_degree(v) if directed, > otherwise degree(v) = #{ u | {u,v} \in E}. > > I guess I did not bring much to the discussion, but I wanted to > underline > that 'directed' vs 'undirected' is distinguished by forcing elements > of E to > be either couples (ordered) or pairs (unordered), while 'multigraph' > vs 'not > multigraph' is mathematically dstinguished by forcing E to be either a > multiset (or bag) or a regular set. > > Alex > > On 23 avr, 18:22, "Nathan O'Treally" <not.rea...@online.de> wrote: > > > > > On 23 Apr., 08:37, Nathann Cohen <nathann.co...@gmail.com> wrote: > > > > For undirected graph, we settled recently on saying that the degree of > > > a single vertex with a loop is equal to 2, because we do not want the > > > inequality (sum of the degrees) = 2* (number of edges) broken. > > > Equality, I guess :-) > > > This unfortunately breaks the common definition degree(v)=#{ w | (v,w) > > in E, w in V } > > (# for cardinality; (v,w) in E <=> (w,v) in E for undirected graphs) > > > I.e., you'd have to add 1 iff (v,v) in E. > > > > Of course it is consistent. But our misunderstanding comes from the > > > fact that my answer was a bit more "technical" that you seemed to > > > think : > > > I understood this; by converting an undirected graph to a directed one > > simply all edges are "doubled" (to pairs with opposite directions). > > > > > When a graph is undirected, sage remembers the edges in both > > > > directions, so returning the out_degree is fine :-) > > > This doesn't hold for self-loops, because a self-loop in an undirected > > graph is represented by a *single* edge in the directed one. > > When talking about the number of (touching) edges, we're talking about > > the cardinality of sets. > > > > In Sage, the "degree" of a vertex in a directed graph [...] > > > is the number of edges "touching" this vertex. > > > So the degree of a vertex with only a self-loop is 2, while it has > > only 1 touching edge (and indegree+outdegree=2 in the directed case). > > > It's better to use formal definitions than prose. ;-) > > > -Leif > > > -- > > To post to this group, send an email to sage-devel@googlegroups.com > > To unsubscribe from this group, send an email to > > sage-devel+unsubscr...@googlegroups.com > > For more options, visit this group > > athttp://groups.google.com/group/sage-devel > > URL:http://www.sagemath.org > > -- > To post to this group, send an email to sage-devel@googlegroups.com > To unsubscribe from this group, send an email to > sage-devel+unsubscr...@googlegroups.com > For more options, visit this group athttp://groups.google.com/group/sage-devel > URL:http://www.sagemath.org -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
