令 Theoren513:Forv∈T,P(v)=min{v), +WVKs v)I 令 Proof:Lets=su{v o Suppose that /'(v) is the length of a shortest path from vI to v containing only vertices in S o(1There are some paths from vi to v, but these paths don't contain the vertex v, and other vertices of t. Then l(v) is the length of the shortest path of these paths, i.e. (v)=(v) 4s(2)There are some paths from v, to v, these paths from vI to Vk don't contain other vertices of T, and the vertex Vk adjacent edge vkv. Then l(v+w(vk,v) is the length of the shortest path of these paths, viz l'(v=l(vR+w vkv)
❖ Theorem 5.13: For vT‘, l’(v)= min{l(v), l(vk )+w(vk , v)} ❖ Proof: Let S'=S∪{vk }. ❖ Suppose that l‘(v) is the length of a shortest path from v1 to v containing only vertices in S’. ❖ (1)There are some paths from v1 to v, but these paths don’t contain the vertex vk and other vertices of T'. Then l(v) is the length of the shortest path of these paths, i.e. l'(v)=l(v)。 ❖ (2)There are some paths from v1 to v, these paths from v1 to vk don’t contain other vertices of T', and the vertex vk adjacent edge {vk ,v}. Then l(vk )+w(vk ,v) is the length of the shortest path of these paths, viz l'(v)= l(vk )+w(vk ,v)
5.5 Trees 6%5.5.1 Trees and their properties . Definition 22: a tree is a connected undirected graph with no simple circuit, and is denoted by T. A vertex of T is a leaf if only if it has degree one. Vertices are called internal vertices if the degrees of the vertices are more than 1. A graph is called a forest if the graph is not connected and each of the graph's connected components is a tree
5.5 Trees ❖5.5.1 Trees and their properties ❖ Definition 22: A tree is a connected undirected graph with no simple circuit, and is denoted by T. A vertex of T is a leaf if only if it has degree one. Vertices are called internal vertices if the degrees of the vertices are more than 1. A graph is called a forest if the graph is not connected and each of the graph’s connected components is a tree
Ss Theorem 5.14: Let T be a graph with n vertices. The following assertions are equivalent &(1T is a connected graph with no simple circuit '(2) is a graph with no simple circuit and e=n-l where e is number of edges of t 63)T is a connected graph with e=n-l where e is number of edges of t. 4(4T is a graph with no simple circuit, and if x and y are nonadjacent vertices of T then T+x, y contains exactly a simple circuit. T+x, y is a new graph which is obtained from T by joining x to y. .(5T is connected and if x, yEE(T) then T-x, y is disconnected. Where T-ix, y is a new graph which is obtained from T by removing edge x, y .(6There is a unique simple path between any two of vertices ofT
❖ Theorem 5.14: Let T be a graph with n vertices. The following assertions are equivalent. ❖ (1)T is a connected graph with no simple circuit. ❖ (2)T is a graph with no simple circuit and e=n-1 where e is number of edges of T. ❖ (3)T is a connected graph with e=n-1 where e is number of edges of T. ❖ (4)T is a graph with no simple circuit, and if x and y are nonadjacent vertices of T then T+{{x,y}} contains exactly a simple circuit. T+{{x,y}} is a new graph which is obtained from T by joining x to y. ❖ (5)T is connected and if {x,y}E(T) then T-{x,y} is disconnected. Where T-{x,y} is a new graph which is obtained from T by removing edge {x,y}. ❖ (6)There is a unique simple path between any two of vertices of T
8 Proof:(1)(2): If T is a connected graph with no simple circuit, then T is a graph with no simple circuit and e=n-1. i.e prove e=n-1 Let us apply induction on the number of vertices of g When n=2, T is a connected graph with no simple circuit the result holds
❖ Proof：(1)→(2): If T is a connected graph with no simple circuit, then T is a graph with no simple circuit and e=n-1. i.e prove e=n-1 ❖ Let us apply induction on the number of vertices of T. ❖ When n=2, T is a connected graph with no simple circuit, the result holds