A. Notes
A path between two vertices in a graph is a list of vertices, in which successive vertices are connected by edges in the graph.
The length of a path is the number of edges on the path.
A simple path is a path with no vertex repeated.
A graph is connected if if there is a path from every vertex to every other vertex in the graph.
A graph is traversable if you can draw a path between all the vertices without retracing the same path. Obviously, a traversable graph is connected.
B. HW
1. In the graph below, how many paths can you find from A to D? Is this graph connected?
How many simple paths from A to F are there? Is this graph traversable?
2. In the graph below, what is the longest simple path? Is this graph traversable? If you can add an edge, can you make the graph traversable?
10, no, 5, no
v u w z x y, no, no
10, no, 5, no
vuwzxy, no, no