Graph DefinitionsDefinition 1. An undirected graph G is a pair(V,E) where• V is the set of vertices,• E ⊆ V2is the set of edges (unordered pairs)E = {(u, v) | u, v ∈ V }.In a directed graph the edges have directions (orderedpairs).A weighted graph includes a weight functionw : E → Rattaching a value (weight) to each edge.– Typeset by FoilTEX –1Definition 2. A path in a graph G =(V,E) is asequence of vertices v1,v2, ...., vksuch that for 1 ≤i ≤ k − 1, (vi,vi+1) ∈ E.Definition 3. A cycle in a graph G =(V,E) is apath v1,v2, ...., vksuch that (vk,v1) ∈ E.Definition 4. A tree is a graph with no cycles.Definition 5. A graph H =(V0,E0) is a subgraphof G =(V,E) iff V0⊆ V and E0⊆ E.Aspanningsubgraph if V0= V .– Typeset by FoilTEX –2Graph RepresentationAdjacency List: A link list for each vertex. Thelist contains a pointer to each neighbor of the vertex.(and a weight for weighted graph.)Total space O(V + E).Sequential (linear) access.Adjacency Matrix: A |V |×|V | array, A[i, j]=1iff (i, j) is an edge in the graph, otherwise A[i, j]=0.(A[i, j]=wi,jfor weighted graph.)Total space O(V2).Random access.– Typeset by FoilTEX –3Spanning TreeGiven a graph G =(V,E) a spanning tree T inG is a subgraph of G that• is connected;• includes all the vertices of G;• hasnocycles;– Typeset by FoilTEX –4Spanning Tree CharacterizationTheorem 1. A spanning tree T in a connectedgraph G =(V,E) is a maximal subgraph of G that isa tree (i.e. any edge added to T closes a cycle).Proof. Proof by contradiction:Assume that T is a spanning tree in G, and addingedge (v, u) to T does not close a cycle.There are paths from w to v,andfromw to uusing only edges of T (since it’s a spanning tree).Thus, the path w to v,theedge(v, u) and thepath u to w must include a cycle. 2– Typeset by FoilTEX –5The Size of a Spanning TreeLemma 1. A spanning tree of a connected graphG =(V,E) has |V |−1 edges.Proof.Let T be a spanning tree of G. Fix a vertex w inT . There is a unique path from w to any other vertexin T .For all u ∈ V If an edge (u, v) was the last edgeon the path from w to u direct the edge to u.This process gives a unique direction to each edge.Associate an edge with the vertex it is pointing to.We have a 1 − 1 correspondence between the edgesof T and the set V −{w}. 2– Typeset by FoilTEX –6Spanning Tree AlgorithmSpanning Tree(G)1. VT ←∅;2. ET ←∅;3. For i =1to |E| do3.1 If {ei}∪ET has no cycles then3.1.1. VT ← VT ∪ ei;3.1.2. ET ← ET ∪{ei};– Typeset by FoilTEX –7CorrectnessTheorem 2. The algorithm computes a spanningtree in G.Proof. The algorithm generates a maximal treesubgraph of G. 2– Typeset by FoilTEX –8Minimum Weighted Spanning TreeGiven a graph G =(V,E) and a weight functionw : E → R (on the edges), a weight of a spanningtree T =(V,E(T )) isw(T )=Xe∈E(T )w(e).A minimum spanning tree of G with weight functionw, is a spanning tree of G with minimum weight.– Typeset by FoilTEX –9Theorem 3. Let T =(V (T ),E(T )) be a minimumspanning tree of G.LetS =(V (S),E(S)) be asubgraph of T .Lete be an edge of minimum weightamong all edges that do not close a cycle with edges inE(S), then E(S) ∪{e}) is a subgraph of a minimumspanning tree of G.Proof. If e ∈ E(T ) we are done.Assume that e/∈ E(T ). Add the edge e to T ,weget a cycle with at least one edge e06∈ E(S), thusw(e0) ≥ w(e).Let T0=(V,E(T )+{e}−{e0}).T0is a spanning tree, and w(T0) ≤ w(T ), thereforeit is also a minimum spanning tree.2– Typeset by FoilTEX –10Minimum Spanning Tree AlgorithmMinimum Spanning Tree (G, w)1. Q ← E;2. E(T ) ←∅;3. V (T ) ←∅;4. For i =1to V − 1 do4.1 e ← Min(Q);4.2 E(T ) ← E(T ) ∪{e};4.3 V (T ) ← V (T )∪ vertices of e.;4.4 Q ← Q −{e};4.5 For all e ∈ Q4.5.1. If e ∪ E(T ) close a cycle then Q ← Q −{e};– Typeset by FoilTEX –11Greedy AlgorithmA greedy algorithm makes a sequence of localoptimal choices.Under various conditions greedy construction isoptimal, i.e. local optimal choices lead to globaloptimal solution, and there is no need for backtracking- but not always!– Typeset by FoilTEX –12AnalysisTheorem 4. The algorithm constructs a minimumspanning tree.Proof. We prove by induction on the size of the setE(T ), that E(T ) is always a subset of a minimumspanning tree.The induction hypothesis holds for E(T )=∅.Assume that it holds for |E(T )| = i − 1, then bythe above theorem and the choice of the algorithm theclaim holds for |E(T )| = i.Thus, also holds for |E(T )| = |V |−1. 2– Typeset by FoilTEX
or
We will never post anything without your permission.
Don't have an account? Sign up