CMPSC 130A Chapter Notes - Chapter 9: Adjacency List, Adjacency Matrix, Complete Graph
Document Summary
Graph = (, ) consists of a set of vertices, , and a set of edges, Each edge is a pair (, ) where , . If the pair is ordered, then the graph is directed. Vertex is adjacent to if and only if (, ) . In an undirected graph with edge (, ), and hence (, ), is adjacent to and is adjacent to. Sometimes an edge has a third component: a weight or a cost. Path = a sequence of vertices ,, -, . , , 0 such that (1, 12,) for. Length of a path = the number of edges on the path, which is equal to 1. Loop = a path in which the graph contains an edge (, ) from a vertex to itself. Simple path = a path such that all vertices are distinct, except that the first and last could be the same.
