15 251 Great Theoretical Ideas in Computer Science Notes on Graph Theory draft 1 15251 Staff January 29 2012 Notation A graph is a set of vertices or nodes V and a set of edges E where each edge is a pair of vertices In an undirected graph an edge is just a set of two vertices u v order does not matter whereas in a directed graph an edge is an ordered pair u v with the edge pointing from u to v In this course we will mostly deal with undirected graphs The graph G is thus the tuple V E Some jargon alert You should get used to the phrase Let G V E be a graph We use nodes and vertex completely interchangeably Sometimes we will even just say Let G be a graph and you should imagine G V E in there As an example the graph G V E with V u v w x y z and E u x u v v w x y x z y z u z is drawn below We also allow E to be a multiset of edges the graph can have multiple edges connecting the same two nodes These are called parallel edges We also allow an edge to be a multiset of two copies of the same vertex u u such an edge is called a self loop But these are exceptional cases A graph is simple if it does not have any self loops and no parallel edges An important note We assume our graphs are simple unless otherwise stated So if you see a problem saying Given a graph G imagine the word simple in there The edge e u v is said to be incident to its two nodes u and v these are also called its endpoints A vertex u is adjacent to v is there is an edge u v connecting them The degree of a node v is the number of edges incident on v and is written as deg v One exception a self loop u u contributes 2 to the degree of u Since each edge is incident on two nodes it contributes to the degree of two nodes and X deg v 2 E v V 1 A path in G is a sequence of vertices v1 v2 vk such that each consecutive pair vi vi 1 is an edge in G The path is simple if all the vertices are distinct A cycle is a path where the start vertex v1 is the same as the end vertex vk but all other vertices are distinct For example in the graph above x y z x u v u is a path but is not simple whereas x y z u v is a simple path And both x y z x and x y z u x are cycles A graph G V E is connected if every pair of nodes in G has a path between them If the graph is not connected each maximal connected piece is called a component 2 Trees A tree is a connected graph without any cycles it is acyclic The following two graphs are trees whereas the following two are not But there are many equivalent definitions of trees Theorem 2 1 Let G be a graph on n nodes and e edges The following statements are equivalent 1 G is a tree connected acyclic 2 Every two nodes in G are connected by a unique path 3 G is connected and n e 1 4 G is acyclic and n e 1 Proofs like this often proceed by showing 1 2 3 4 1 and in this case we will do exactly this Proof 1 2 Clearly each pair u v is connected by at least one path since G is connected Now suppose u and v have two different paths P u v0 v1 vk vk 1 v and Q u w0 w1 wl wl 1 v Let i be the smallest value such that vi 6 wi hence i 1 Let j be the smallest value j i such that vp also lies on Q say it is 2 the same as wq Then the paths wi 1 wi wq and vi 1 vi vp are disjoint apart from the start and end and form a cycle This contradicts the acyclic property of G 2 3 By induction The base case is when n 2 then the unique path implies a single edge hence n 2 e 1 Suppose the implication is true for all graphs with n nodes Now suppose G has n nodes let x y be adjacent Since there is a unique path between x y there cannot be another path connecting x y If we delete the edge x y the graph falls apart into two pieces G1 and G2 By induction n1 e1 1 and n2 e2 1 and so n n1 n2 e1 e2 2 e 1 since e e1 e2 1 to account for the edge x y 3 4 By assumption G is connected with n e 1 Suppose G has a cycle with k vertices Then this cycle also has k edges Let S be this cycle Since G is connected there must be some vertex with an edge to S Add this vertex to S along with this edge connecting it to S Repeat until all nodes in G have been added to S Since we add one edge for each vertex we will end up with n vertices and n edges in S which contradicts the fact that G has n 1 edges 4 1 Let G be acyclic and n e 1 and suppose G is not connected Suppose there are k components Each component is acyclic and connected soPif it has ni nodes it P must have ni 1 edges from part 1 2 Hence e i ei i ni k So k 1 which means the graph is connected These multiple definitions allow us to prove many facts about trees For example the following Fact 2 2 A leaf is a vertex in a tree with degree 1 Any tree has at least two leaves Proof Suppose not Then at least n 1 nodes have degree P at least 2 Also since the graph is connected the last node has degree at least one So v deg v 2 n 1 1 2n 1 and hence E is at least n 1 2 But it is an integer so E dn 1 2e n But this is impossible for a tree Exercise Give an example of a tree with only two leaves Exercise For a tree T let S be the set of nodes with degree 1 or 2 Show that S n 2 2 1 Counting Labeled Trees on n Nodes In this section we will count the number of labeled trees on n nodes where the nodes are numbered 1 2 n There is only one tree on the two nodes 1 2 a single edge On three nodes each tree looks like a path with two edges …
View Full Document
Unlocking...