Graph Types


Undirected graph 
(no arrows)

One of the key distinctions people make between graphs is whether they are directed or undirected. I'll admit, when I talk about undirected graphs, I sometimes get a mental image of a subway system map just sitting there aimlessly on the couch while its parents just sigh and ask when it's going to take responsibility and do something with its life...

Directed graph 
(note the arrows)

...but that's just me. Really, all we're saying is whether the edges in a graph are bidirectional or not.

Most, but not all, graphs I've seen have only one kind of edge. There are a few cases where you might want to use both—for example, a street map might have undirected edges for two-way streets and directed edges for downtown—but that's the only example I can think of off the top of my head.

Weighted Graphs.

A weighted graph is an edge labeled graph where the labels can be operated on by the usual arithmetic operators, including comparisons like using less than and greater than. In Haskell we'd say the edge labels are i the Num class. Usually they are integers or floats. The idea is that some edges may be more (or less) expensive, and this cost is represented by the edge labels or weight. In the graph below, which is an undirected graph, the weights are drawn adjacent to the edges and appear in dark purple.


Here we have the following parts.

The underlying set for the the Vertices set is Integer. The underlying set for the weights is Integer. The Vertices set = {1,2,3,4,5} The Edge set = {(1,4,5) ,(4,5,58) ,(3,5,34) ,(2,4,5) ,(2,5,4) ,(3,2,14) ,(1,2,2)}