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: 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.

2 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 . 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.

3 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. 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.

4 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. 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.

5 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. 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)

6 , 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. 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.)

7 Or num-bers1,2, ..for 1. DEFINITIONS AND FUNDAMENTAL two edges(u, v)and(v, u)are the same. 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)

8 , 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. e1is a pendant edge. The degree ofv5is5. The degree ofv4is2. The degree ofv3is0so it is an isolated the future, we will label graphs with letters, for example:G= (V, E).

9 Theminimum degreeof the vertices in a graphGis denoted (G)(= 0if there is an isolatedvertex inG). Similarly, we write (G)as themaximum degreeof vertices (Continuing from the previous example) (G) = 0and (G) = this course, we only considerfinitegraphs, finite every edge has two end vertices, we getTheorem graphG= (V, E), whereV={v1, .. , vn}andE={e1, .. , em}, satisfiesn i=1d(vi) = GRAPH has an even number of vertices of odd the verticesv1, .. , vkhave odd degrees and the verticesvk+1, .. , vnhave even de-grees, then (Theorem )d(v1) + +d(vk) = 2m d(vk+1) d(vn)is even. Therefore,kis (Continuing from the previous example) Now the sum of the degrees is1 + 2 + 0 +2 + 5 = 10 = 2 5.

10 There are two vertices of odd degree, simple GRAPH that contains every possible edge between allthe vertices is called acompletegraph. A complete GRAPH withnvertices is denoted asKn. The first four complete graphs aregiven as examples:K1K2K3K4 The graphG1= (V1, E1)is asubgraphofG2= (V2, E2) V2and2. Every edge ofG1is also an edge 1. DEFINITIONS AND FUNDAMENTAL have the graphG2:e1v1v2e2e3v3e4v4e5v5e6and some of its subgraphs areG1:e1v1v2G1:e1v1v2e2v3e4v4e5v5e6G1:v1 v2v3e5v5e6 CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS5andG1:v5e6 Thesubgraph ofG= (V, E)induced by the edge setE1 Eis:G1= (V1, E1) = ,whereV1consists of every end vertex of the edges (Continuing from above) From the original graphG, the edgese2,e3ande5inducethe subgraph e2,e3,e5 :v1v2e2e3v3e5v5 Thesubgraph ofG= (V, E)induced by the vertex setV1 Vis:G1= (V1, E1) = ,whereE1consists of every edge between the vertices (Continuing from the previous example) From the original graphG, the verticesv1,v3andv5induce the subgraphv1e3v3e5v5e6 v1,v3,v5 :A complete subgraph ofGis called 1.