DOC PREVIEW
Graph Definitions

This preview shows page 1-2-3-4 out of 13 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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


Graph Definitions

Download Graph Definitions
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Graph Definitions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Graph Definitions 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?