# Questions tagged [multigraphs]

A multigraph is a graph that can have multiple edges with the same end nodes. Thus, two vertices may be connected by more than one edge.

23 questions
Filter by
Sorted by
Tagged with
4k views

### What is the edge set of a multigraph?

An edge set of a graph is a set of doubletons, pairing edges. For example: has an edge set of $\{\{6,4\},\{4,5\},\{4,3\},\{5,2\},\{5,1\},\{3,2\},\{1,2\}\}$. A set, by definition, cannot have ...
5k views

### Directed Multigraph or Directed Simple Graph?

I have the following two questions in my book: Question # 1 Determine whether the graph shown has directed or undirected edges, whether it has multiple edges, and whether it has one or more loops. ...
443 views

### Directed multigraph with numbered edges

Let we have a directed multigraph such that or every its vertex the set of edges from this vertex is finite and ordered (in other words, numbered $1,\dots,n$). I need this construct to describe (...
885 views

34 views

### How to read the mathematical notation for multigraphs?

How to read the mathematical notation for multigraphs: $$E \rightarrow V \cup[V]^2$$ $E$ is a set of edges $V$ is the set of vertices I am having trouble especially with this part $$[V]^2$$ ...
33 views

### What is the name of a set of parallel edges in a multigraph?

In directed multigraph, two vertices, $a$ and $b$, may have zero or more parallel edges connecting them in one direction or the other. Does this set of parallel edges have a name? I seem to remember ...
341 views

### Topological sort of a subgraph of a multigraph

Is there a good algorithm for doing a topological sort of a subgraph of a multigraph? More specifically, given a multigraph G and a node n in the graph. Consider the subgraph G' all the nodes ...
97 views

### Clarification on the definition of multigraph

If I have a graph that has an edge that straight connects vertice $A$ to $B$ and another that connects vertice $A$ to $C$ then to $B$ is it considered a multigraph? Clarification will be much ...
1k views

### Difference between graph and multigraph

Does there exist a multigraph $G$ of order $8$ such that the minimal $d(G) = 0$ while maximal $d(G) = 7$? What if ‘multigraph $G$’ is replaced by ‘graph $G$’? Answer: such multigraph does not exist, ...
33 views

### Help proving a theorem about node ordering of a directed multigraph

We a have polytree $G = (V, E)$. Note that every vertice $v_i$ can only have one outgoing edge. Now lets add a new type of edge which we call an red edge. $R$ is the set of all these edges. So we ...