October 16

Earlier we noted that a path from $v_1$ to itself is called a circuit (sometimes simple circuit) if it repeats no edges, and a cycle (sometimes simple cycle) if it repeats no vertices except $v_1$. A graph is acyclic if it contains no cycles with 2 or more edges. A connected, acyclic graph with a distinguished vertex (a vertex that we choose and keep track of) is called a tree (the distinguished node is the root).

One sort of information that can be added to a graph is edge weight: with each edge $(v_i, v_j)$, associate a number. Various applications might use weighted graph to represent properties, for example inter-city distances, average packet time between internet hosts, etc.

Our two graph representations can be coerced into adding this information: an adjacency matrix can store the edge weight for edge $(v_i, v_j)$ in matrix[i][j]. In this scheme, matrix[i][i] would be 0, and matrix[i][j] could contain some special value (say $\infty$) if there is no edge $(v_i, v_j)$. Similarly, an adjacency list could add a member to each list element to record the edge weight.