P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-02 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 16:38
48 Graph Essentialsmore that a given number of nodes, is NP-complete. In clique detection, the
goal is to solve similar clique problems efficiently or provide approximate
solutions. In graph isomorphism, given two graphsgandg′, our goal is
to find a mappingffrom nodes ofgtog′such that for any two nodes of
gthat are connected, their mapped nodes ing′are connected as well. In
topological sort algorithms, a linear ordering of nodes is found in a directed
graph such that for any directed edge (u,v) in the graph, nodeucomes
before nodevin the ordering. In the traveling salesman problem (TSP), we
are provided cities and pairwise distances between them. In graph theory
terms, we are given a weighted graph where nodes represent cities and
edge weights represent distances between cities. The problem is to find the
shortest walk that visits all cities and returns to the origin city.
Other noteworthy shortest path algorithms such as theA∗[Hart, Nilsson,
and Raphael, 2003], the Bellman-Ford [Bellman and Ford, 1956], and all-
pair shortest path algorithms such as Floyd-Warshall’s [Floyd, 1962]are
employed extensively in other literature.
In spanning tree computation, the Kruskal Algorithm [Kruskal, 1956]
or Boruvka [Motwani and Raghavan, 1995] are also well-established
algorithms.
General references for flow algorithms, other algorithms not discussed
in this chapter such as the Push-Relabel algorithm, and their optimality can
be found in [Cormen, 2009;Ahuja et al., 1993].2.9 ExercisesGraph Basics- Given a directed graphG=(V,E) and its adjacency matrixA,we
propose two methods to makeGundirected,
A′ij=min(1,Aij+Aji), (2.26)
A′ij=Aij×Aji, (2.27)whereA′i,jis the (i,j) entry of the undirected adjacency matrix. Discuss
the advantages and disadvantages of each method.Graph Representation- Is it possible to have the following degrees in a graph with 7 nodes?
{ 4 , 4 , 4 , 3 , 5 , 7 , 2 }. (2.28)