GRAPH THEORY - TUT

1 GRAPH THEORYK eijo Ruohonen(Translation by Janne Tamminen, Kung-Chung Lee and Robert Pich )2013 Contents1I DEFINITIONS AND FUNDAMENTAL , Trails, Paths, Circuits, Connectivity, Graphs and Isomorphism20II and (Fundamental) Circuits and (Fundamental) Cut Sets27 III 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.

2 The Ford Fulkerson Algorithmiii85VI DRAWING and Planar Davidson Harel Algorithm92 VII Circuit Matroid of a Basic General on Matroids106 References108 IndexForewordThese lecture notes were translated from the Finnish lecture notes for the TUT course on graphtheory. The laborious bulk translation was taken care of by the students Janne Tamminen (TUT)and Kung-Chung Lee (visiting from the University of BritishColumbia). Most of the materialwas then checked by professor Robert Pich . I want to thank the translation team for their notes form the base text for the course MAT-62756 GRAPH THEORY .

3 They containan introduction to basic concepts and results in GRAPH THEORY , with a special emphasis put onthe network-theoretic circuit-cut dualism. In many ways a model was the elegant and carefulpresentation of SWAMY& THULASIRAMAN, especially the older (and better) edition. There areof course many modern text-books with similar contents, the popular GROSS& of the usages of GRAPH THEORY is to give a unified formalismfor many very different-looking problems. It then suffices to present algorithms in this common formalism.

4 This haslead to the birth of a special class of algorithms, the so-calledgraph of thetext of these notes deals with GRAPH algorithms, again putting emphasis on network-theoreticmethods. Only basic algorithms, applicable to problems of moderate size, are treated classes of algorithms, such as those dealing with sparse large graphs, small-world graphs, or parallel algorithms will not be treated. In thesealgorithms, data structure issues havea large role, too (see SKIENA).The basis of GRAPH THEORY is in combinatorics, and the role of graphics is only in visual-izing things.

5 GRAPH -theoretic applications and models usually involve connections to the realworld on the one hand often expressed in vivid graphical terms and the definitional andcomputational methods given by the mathematical combinatoric and linear-algebraic machin-ery on the other. For many, this interplay is what makes graphtheory so interesting. There isa part of GRAPH THEORY which actually deals with graphical drawing and presentation of graphs,briefly touched in Chapter 6, where also simple algorithms are given for planarity testing anddrawing.

6 The presentation of the matter is quite superficial, a more profound treatment wouldrequire some rather deep results in topology and curve THEORY . Chapter 7 contains a brief intro-duction to matroids, a nice generalization and substitute for graphs in many of GRAPH -theoretic results and methods are usually not given in a completely rigorouscombinatoric form, but rather using the possibilities of visualization given by graphical presen-tations of graphs. This can lead to situations where the reader may not be completely convincedof the validity of proofs and derivations.

7 One of the goals ofa course in GRAPH THEORY must theniiibe to provide the student with the correct touch to such seemingly loose methods of is indeed necessary, as a completely rigoristic mathematical presentation is often almostunreadable, whereas an excessively slack and lacunar presentation is of course RuohonenChapter 1 Definitions and Fundamental DefinitionsConceptually, agraphis formed byverticesandedgesconnecting the , a GRAPH is a pair of sets(V, E), whereVis theset of verticesandEis theset ofedges, formed by pairs of amultiset, in other words, its elements can occur morethan once so that every element has amultiplicity.

8 Often, we label the vertices with letters (forexample:a, b, c, ..orv1, v2, ..) or numbers1,2, ..Throughout this lecture material, we willlabel the elements ofVin this (Continuing from the previous example) We label the vertices as follows:v2v3v1v4v5We haveV={v1, .. , v5}for the vertices andE={(v1, v2),(v2, v5),(v5, v5),(v5, v4),(v5, v4)}for the , we often label the edges with letters (for example:a, b, c, ..ore1, e2, ..) or num-bers1,2, ..for 1. DEFINITIONS AND FUNDAMENTAL two edges(u, v)and(v, u)are the same.

9 In other words, the pair is (Continuing from the previous example) We label the edges asfollows:v2v3v1v4v5e1e2e3e4e5 SoE={e1, .. , e5}.We have the following terminologies:1. The two verticesuandvareend verticesof the edge(u, v).2. Edges that have the same end vertices An edge of the form(v, v)is A GRAPH issimpleif it has no parallel edges or A GRAPH with no edges ( empty) A GRAPH with no vertices ( empty) is anull A GRAPH with only one vertex Edges areadjacentif they share a common end Two verticesuandvareadjacentif they are connected by an edge, in other words,(u, v)is an Thedegreeof the vertexv, written asd(v)

10 , is the number of edges withvas an end convention, we count a loop twice and parallel edges contribute Apendant vertexis a vertex whose degree An edge that has a pendant vertex as an end vertex is apendant Anisolated vertexis a vertex whose degree (Continuing from the previous example) v4andv5are end vertices ofe5. e4ande5are parallel. e3is a loop. The GRAPH is not simple. e1ande2are 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS3 v1andv2are adjacent. The degree ofv1is1so it is a pendant vertex.