GRAPH THEORY - TUT

← Back to document page

GRAPH THEORYKeijo Ruohonen(Translation by Janne Tamminen, Kung-Chung Lee and Robert Pich )2013Contents1I DEFINITIONS AND FUNDAMENTAL , Trails, Paths, Circuits, Connectivity, Graphs and Isomorphism20II and (Fundamental) Circuits and (Fundamental) Cut Sets27III DIRECTED Directed Graphs34IV MATRICES AND VECTOR SPACES OF Representation of Application: Stationary Linear overGF(2)and Vector Spaces of Graphs50V GRAPH Complexity of : Warshall s and Breadth-First Lightest Path: Dijkstra s Lightest Path: Floyd s Lightest Spanning Tree: Kruskal s and Prim s Lightest Hamiltonian Circuit (Travelling Salesman s Problem): The AnnealingAlgorithm and the Karp Held Matching in Bipartite Graphs: The Hungarian Flow in a Transport Network: The Ford Fulkerson Algorithmiii85VI DRAWING and Planar Davidson Harel Algorithm92VII Circuit Matroid of a Basic General on Matroids106References108IndexForewordThe se lecture notes were translated from the Finnish lecture notes for the TUT course on graphtheory.

ii 85 VI DRAWING GRAPHS 85 6.1 Planarity and Planar Embedding 90 6.2 The Davidson–Harel Algorithm 92 VII MATROIDS 92 7.1 Hereditary Systems 93 7.2 The Circuit Matroid of a Graph

  Theory, Graph, Graph theory