4 ms·

It's interesting that it's apparently the problem that laid the foundation for modern graph theory, but the problem can't actually be specified as a graph under

It's interesting that it's apparently the problem that laid the foundation for modern graph theory, but the problem can't actually be specified as a graph under its usual modern definition... can it? At least not without some shenanigans that would make it more complicated than "node = landmass, edge = bridge", as it's depicted in the standard diagram shown on Wikipedia. A graph is usually defined as a set of nodes and a set of edges, where an edge is a pair of nodes (an ordered pair if it's a directed graph). The "set" of edges (bridges) of the "graph" in this case contains duplicates -- there are two edges with the same pair of vertices, two bridges crossing between the same pairs of landmasses. And the two pairs of duplicated bridges are essential to the problem setup. So AFAICT it can't be fully specified as a set of edges; it would have to be a multiset. (I've seen this problem before but only just noticed this when reading Wikipedia now -- let me know if I'm missing something.)

ColinWright 6y ago
A "graph" can sometimes implicitly mean a "Simple Graph" which has neither loops nor multiple edges between pairs of vertices, but in some contexts can mean "Multi-Graph", which does allow multiple edges and loops. So the usual conversion of the bridges problem to a network gives us a "Multi-Graph" ... the distinction is often left to be inferred, because it's usually obvious (to the skilled practitioner). One way around this to end up with a simple graph is to include a vertex in the middle of each bridge. Then each edge has one end in the landmass and the other end in the middle of the bridge. That equivalence/conversion shows that the distinction, in this case, is effectively unimportant.
saagarjha 6y ago
Yes, the image shown is a multigraph: https://en.wikipedia.org/wiki/Multigraph https://en.wikipedia.org/wiki/Multigraph

ColinWright 6y ago

A "graph" can sometimes implicitly mean a "Simple Graph" which has neither loops nor multiple edges between pairs of vertices, but in some contexts can mean "Multi-Graph", which does allow multiple edges and loops. So the usual conversion of the bridges problem to a network gives us a "Multi-Graph" ... the distinction is often left to be inferred, because it's usually obvious (to the skilled practitioner). One way around this to end up with a simple graph is to include a vertex in the middle of each bridge. Then each edge has one end in the landmass and the other end in the middle of the bridge. That equivalence/conversion shows that the distinction, in this case, is effectively unimportant.

saagarjha 6y ago

Yes, the image shown is a multigraph: https://en.wikipedia.org/wiki/Multigraph https://en.wikipedia.org/wiki/Multigraph