CHAPTER 1 TREES A tree is a connected acyclic undirected graph There is a unique path between every pair of vertices in G A tree with N number of vertices contains N 1 number of edges The vertices which is of 1 degree is called leaf node of the tree and the degree of an internal node Definition is at least 2 Example 1 2 4 3 5 6 Basic terminology in trees Node Node is an intersection point of a graph a Cycle graph Number of vertices connected in a closed chain is called cycle graph Cyclic graph and acyclic graph A cyclic graph is a graph containing atleast one graph cycle A graph that is not cyclic is If we remove any edge it disconnects the graph Hence the removed edge is cut edge said to be acyclic Example of a cyclic graph A B C D Cut edge Example of an cut edge 1 4 2 3 Here edge 1 2 is removed Hence edge 1 2 is an cut edge Connected graph If there is a path from any point to any other point in the graph then we call it as a complete graph A graph that is not connected is said to be disconnected Example of connected graph Directed graph Directed graph is a graph in which the edges have a direction If it is not directed graph then the graph is said to be undirected graph A B C Loops In graph theory a loop is an edge that connects a vertex to itself Parallel edges Two or more edges joining the same pair of vertices is called parallel edges 2 4 1 3 Example a and b are parallel edges a a b Internal nodes nodes 1 b The nodes which have one or more than a child are called internal nodes or non terminal Non terminal nodes 2 3 2 3 Internal nodes or 4 5 6 7 Properties of trees Every tree which has at least two vertices should have at least two leaves Trees have many characterizations Let T be a graph with n vertices then the following statements are equivalent T is a tree T contains no cycles and n 1 edges T is a connected graph and every edge is a cut edge Any two vertices of the graph T are connected by exactly one path T contains no cycle and for any new edge e The graph T e has exactly one cycle Every edge of a tree is a cut edge Adding one edge to a tree defines exactly one cycle Every connected graph contains a spanning tree Every tree has at least two vertices of degree two Prove that there is one and only one path between every pair of vertices Since tree T is a connected graph there exist at least one path between every pair of vertices in a tree T Now suppose between two vertices a and b of the tree T there exist two paths The union of these two paths will from circuit and T cannot be a tree Hence the Theorem 1 1 in a tree Proof above statement is proved a b b Prove that a tree with n vertices has n 1 edges Based on the induction on the number of vertices the theorem true for n 1 2 3 Theorem 1 2 Proof n 1 n 2 n 3 Assume that the theorem holds for all trees with fewer than n vertices Consider a tree T with n vertices In T let be an edge with end vertices and According to theorem there is one and only one path between every pair of vertices in a tree T There is no other path between excent Therefore deletion of from T will disconnect the graph Further T nsists of exactly two components and since there were no circuit in T to begin with each of these two components is a tree Both these tree have fewer than n vertices each and therefore by the induction hypothesis each contains one less edge than the number of vertices in it Thus T consists of n 2 edges and n vertices Hence T has exactly n 1 edges Theorem 1 3 A graph G is a tree if and only if it is minimally connected Let the graph G be minimally connected ie removal of one edge makes it disconnected Proof Therefore there is no circuit Hence graph G is a tree Conversely let the graph G be tree ie there exist one and only path between every pair of vertices We know that removal of one edge from the path makes the graph disconnected Hence graph G is minimally connected a b a b c d c d Let G be a graph A connected subgraph S of the graph G V E is said to be CHAPTER 2 SPANNING TREES Definition subgraph if 1 S should contain all vertices of G 2 S should contain V 1 edges V vertex of a graph E edge of a graph 1 3 2 4 1 3 2 4 G I II I Spanning tree of main graph II Not a spanning tree For example a c b d i ii iii iv i main graph ii iii iv are spanning tree of the main graph n no of vertices of main graph Number of edges n 1 a c a c b d b d g f g f i ii i Main graph ii Spanning tree of main graph Properties of spanning trees 1 Trees are graphs that have no circuits 2 A tree T is said to be a spanning tree of a connected graph G if T is a subgraph of G and T contains all vertices of G 3 Spanning tree is called as skeleton or scaffolding of G 4 Spanning tree is defined only for a connected graph 5 We can never have any cycle in a spanning tree 6 All spanning tree have the same number of edges 7 A graph may have many spanning trees 8 A connected and undirected graph has atleast one spanning tree 9 Spanning tree is minimally connected and maximally acyclic 10 The spanning tree has all the same properties of other trees 1 An edge in a spanning tree T is called a branch of T 2 An edge of main graph G that is not in a given spanning tree T is called a chord In electrical engineering a chord is sometimes referred to as a tie or a Note link i ii iii a b a c d b d c d c i main graph ii spanning tree iii chord Weight of an edge of a graph In many applications each edge of a graph has an associated numericals value called weight Usually the edge weights W E are non negative integers Weighted graphs may be either directed or undirected The weight of an edge is often referred to as the cost of the edge Weight of spanning tree Weight of spanning tree W T is the sum of weights of all edges in …