Talk:Multigraph

From Wikipedia, the free encyclopedia

/{/{move|Labeled directed multigraph/}/}

This is because of the given definition is for a directed graph and not for a undirected one. Batztown 14:31, 21 Apr 2005 (UTC)

Surely that's just an oversight that could be corrected; it doesn't require a move. Gdr 20:52, 2005 May 6 (UTC)

Agreed. On checking history reveals change already made by User:Mikkalai. Removed move request. Zanaq 5 July 2005 21:57 (UTC)

[edit] "Multiset" is wrong for "multidigraph"

"Multidigraph" should not be defined in terms of multisets, which do not support for example the notion of the multidigraph of all subsets of a set X and the functions between them. This notion arises for example in category theory as the underlying graph of the category of those subsets (underlying in the sense of forgetting the composition). In that notion the set of edges from one vertex to another is simply a set, not a multiset. Multisets have multiplicities of members, see the Wikipedia article multiset, there is no multiplicity here.

If you mean that each member of E is an edge (u,v) and that this edge has a multiplicity n, this doesn't work for a couple of reasons. First one wants the individual edges to work like the elements of a set, which doesn't happen if you only have the information that there are some number say 57 of them, as opposed to an actual set of them. For example if X has subsets Y and Z of size 2 and 4 respectively, then the multiplicity of the edge from Y to Z is the same as that from Z to Y, namely 16, when what you really need there is two distinct sets of edges, one set from Y to Z, the other from Z to Y, each set having 16 elements. Second, if X is an infinite set then you need an infinite multiplicity, also not catered for by multisets. And if you try to extend the notion of multiset by allowing infinite numbers, whether as cardinals or ordinals, this only makes matters worse.

A workable definition of a multigraph is as a quadruple (V,E,s,t) where s,t:E->V are two functions giving respectively the source and target vertex of each edge. No axioms are needed, the functions do the job on their own. An alternative definition is (E,s,t) where s,t:E->E give respectively the source and target of each edge as another edge; in this case one does need axioms, namely s(t(e)) = t(e) = t(t(e)) and s(s(e)) = s(e) = t(s(e)). One can then pick out the vertices as those special edges e for which s(e) = t(e), i.e. self-loops. This second definition makes a multigraph an algebra with signature (similarity type) 1-1 meaning two unary operations and satisfying the above axioms defining its equational theory. Multigraphs defined in either way form a variety, and moreover one which along with its homomorphisms forms a topos. Vaughan Pratt 15:12, 19 August 2006 (UTC)