Can a simple graph have weighted edges?

466 Views Asked by At

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.

1

There are 1 best solutions below

0
On

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.