Graphs: Theory and Algorithms
This adaptation of an earlier work by the authors is a graduate text and professional reference on the fundamentals of graph theory. It covers the theory of graphs, its applications to computer networks and the theory of graph algorithms. Also includes exercises and an updated bibliography.
TREES CUTSETS AND CIRCUITS
EULERIAN AND HAMILTONIAN GRAPHS
GRAPHS AND VECTOR SPACES
MATRICES OF A GRAPH
PLANARITY AND DUALITY
acyclic adjacent algorithm augmenting path back edge bipartite graph circuit of G circuit subspace cocircuit coloring computing connected graph Consider construct contains Corollary corresponding defined denote directed circuits directed graph directed path directed s-t path dual edge set edge-disjoint edge-induced subgraph edges incident edges of G electrical network elements end vertices equal Eulerian graph exists following theorem fundamental circuit fundamental cutset graph G graph of Fig graph theory Hence in-degree incidence matrix independent set induced subgraph labeling layered network Lemma length Let G matroid maximal maximum flow maximum matching n-vertex nonzero number of edges number of vertices paths in G planar graph problem Proof prove push result ring sum saturated self-loops shortest paths shown in Fig simple graph spanning tree strongly connected strongly connected component subgraph of G submatrix subset Suppose transitive closure transport network tree of G undirected vector space vertex set vertices of G weight spanning tree