represent a graph by a string. One of the simplest and most convenient ways of
encoding graphs is by an adjacency matrix. For a directed graph with vertices υ 1 ,
υ 2 ,…, υ n and edge set E, an adjacency matrix is an n × n
Figure 14.2
array in which a (i, j), the entry in the ith row and jth column satisfies
An undirected edge can be considered two separate edges in opposite directions.
The array represents the graph in Figure 14.2.
A graph with n vertices then requires a string of length n 2 for its
representation. For an undirected graph the matrix is symmetric, so the storage
requirement can be reduced to (n + 1)n /2, but in any case, the input string will
have length O(n 2 ).
Next, we generate, nondeterministically, a permutation of the vertices. This
can be done in O(n 3 ) time. Finally, we check the permutation to see if it
constitutes a path. A time O(n 4 ) is sufficient for this. Therefore, HAMPATH ∈
NP.