0
$\begingroup$

Can a simple graph have weighted edges or is it a multigraph as soon as it has weights?

To me it seems like the adjacency matrix would look the same (as from a multigraph). Also I thought I had read that a multigraph has weighted edges. But I can not find the source again.

$\endgroup$
  • $\begingroup$ What do you mean with weighted? If you take it to be a function $E \rightarrow \mathbb R$ from the set of edges to the reals, then it does not really matter, which type of graph you have. You can have $E \subseteq \binom{V}{2}$ (simple graph), $E \subseteq V \times V$ (directed graph with potential loops) or $E \subseteq \mathcal P(V)$ (hypergraph) without any problems... $\endgroup$ – PrudiiArca Mar 21 at 16:45
0
$\begingroup$

Yes, a simple graph can have weighted edges.

Depending on context and application, you might view this as a function from the set of edges to the set of real numbers (or the integers, or the complex numbers, ...).

Or you might choose to encode it in an adjacency matrix, by letting the entry in position $i,j$ be the weight of the edge from vertex $i$ to vertex $j$, or zero if there is no edge. This makes an unweighted graph equivalent to a weighted one where every edge has weight 1, and assumes that weight 0 can't be assigned to an edge, or is equivalent to the edge being absent.

And yes, you could interpret a weighted simple graph whose weights are natural numbers as equivalent to an unweighted multigraph, where the weight on each (simple) edge tells you how many multi-edges are present between those vertices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.