Talk:Multigraph

Single character labels?

Is seems that this definition allows only for single character labels. Is that correct? —Preceding unsigned comment added by Khatchad (talk • contribs) 10:46, 12 June 2008 (UTC)[reply]

/{/{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)

A multigraph is an object with many sides. —Preceding unsigned comment added by 72.82.66.161 (talk) 22:19, 4 November 2009 (UTC)[reply]

"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)[reply]

Random Multigraphs

We determine a random multigraph beginning only with a set of n vertices. After we proceed in steps. In each step we add one undirected edge uv, corresponding to an ordered pair (u,v) chosen uniformly from the set of the n² ordered pairs {(1,1),(1,2),…(1,n), (2,1),(2,2),…(2,n),…,(n,n)}. Some authors use the term multigraph process to name the procedure described above.

When we want to determine a random graph, each step adds one new edge uv, and removes uv from the set of the ${n \choose 2}$ edges when the process begins.

We see that the graph process always produce a graph, but the multigraph process can generate multigraphs with multiple edges, and self-loops. A self-loop is generated with probability 1/n², while an edge uv, u distinct of v, is generated with probability 2/n².

In practice we stop a process when a given event happens. Examples of such events:
(i) The first m edges are added.
(ii) Multiple edges first appear in the resulting multigraph.

If one throws a pair of “fair” dice until a total of seven happens, we see a multigraph process stopped when “a seven arises”. In this case n = 6. The set of the 6² ordered pairs is {(1,1),…, (1,6),(2,1),…(2,6),…,(6,6)}.

With dice we can generate the edges of a multigraph. The sequence of pairs (1,2),(2,1),(2,2),(3,4), corresponds to the multigraph depicted on the right side.

Now suppose that one shuffles a deck of playing cards, and repeatedly deals one pair of cards from the deck until the sum of the values of the cards of a pair is 11, (face cards with value 10), or until there is no cards. In this way we always generate a graph, since two pairs with the same cards never appear, nor a pair of equal cards. Here n = 52, and there are ${52 \choose 2}$ possible edges, or possible pairs of cards that we can see.

So essentially we have sampling with and without replacement.

The graph processes described here, with discrete uniform probability distributions are very simple, and can be understood by a person with modest mathematical background. Computer simulations of this processes are easy to implement, and provide exercises that can help a student to understand the basic concepts necessary to use results of the theory of random graphs developed by great mathematicians. --Webonfim (talk) 02:44, 24 January 2008 (UTC)[reply]

Contradiction

From the current article version: Multigraphs might be used to model the possible flight connections offered by an airline. In this case the pseudograph would be a directed graph with pairs of directed parallel edges connecting cities to show that it is possible to fly both to and from these locations.

But the article says directed graphs are exclusive to multidigraphs. ?! --Abdull (talk) 08:49, 16 July 2008 (UTC)[reply]

Office machine

Possibly some mention should be made and an article spun off with a hatnote at the top of this article about the office machine popular in the first half of the 20th century called the "Multigraph". [1] [2] photo. -- Infrogmation (talk) 22:10, 16 March 2010 (UTC)[reply]

Simple vs multi

Is every graph either a multigraph or a simple graph? If yes, could this be added to the article here? -- RolfSander (talk) 12:06, 29 May 2017 (UTC)[reply]

It kind of depends on the definition of "simple", but arguably a graph with a self-loop but with one one edges between any pair of vertices is neither a simple graph nor a multigraph. --Saforrest (talk) 12:35, 31 March 2022 (UTC)[reply]