DOC PREVIEW
UT Dallas CS 6363 - notes-6363-001-2015s-20(1)

This preview shows page 1 out of 3 pages.

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

Unformatted text preview:

c� Balaji Raghavachari 121 Algorithm Design and Analysis✬✫✩✪Graphs: concepts• G = (V, E), V is vertex set, and E ⊆ V × V is edge set.• Undirected or directed. Weighted or unweighted.Simple or Multi (a multigraph allows several edgesbetween same two nodes and self loops)• Representation: Adjacency list (efficient), Adjacencymatrix, Edge incidence matrix• For a n edge (u, v) ∈ E, we say v is adjacent to u, or v isneighb or of u. If directed, the edge goes from u to v• Degree of a vertex u is the number of its neighbors ithas in G. In directed graphs, we have out-degree(number of outgoing edges from u), in-degree (numberof edges coming into u), and degree (sum of in-degreeand out-degree) of a vertex uc� Balaji Raghavachari 122 Algorithm Design and Analysis✬✫✩✪Paths and cycles• A path P = �v0, v1, . . . , vk� is a path of length k from uto v, if v0= u, vk= v, and (vj−1, vj) ∈ E for j = 1, 2, . . . , k• Path is simple if all its nodes are distinct• A cycle is a path in which v0= vk• A simple cycle is one in which v1. . . vkare distinctnodes• When we say cycle/path, we usually mean only simplecycle/path• Subpath of above path is �vi, . . . , vj�, where0 ≤ i ≤ j ≤ kc� Balaji Raghavachari 123 Algorithm Design and Analysis✬✫✩✪Acyclic graphs• An acyclic, undirected graph is called a forest• A connected forest is called a tree• A tree that connects all nodes of a graph is called aspanning tree• A DAG is a directed, acyclic graph• Directed (or rooted) tree: a root node, and directededges that ta ke you away from the root (outgoing tree)or toward the root (incoming tree)c� Balaji Raghavachari 124 Algorithm Design and Analysis✬✫✩✪Components• Nodes u and v are connected, if there is a path from uto v (in undirected graphs)• Connected components of a graph are the equivalenceclasses of the “connected” relation between vertices• In directed graphs, u and v are strongly connected ifthere is a path from u to v, and a path from v to u• Strongly connected components of a directed graph arethe equivalence classes of “strongly connected” relationbetween verticesc� Balaji Raghavachari 125 Algorithm Design and Analysis✬✫✩✪Subgraphs and morphisms• Given G = (V, E), we say G′= (V′, E′) is a subgraph ofG if V′⊆ V and E′⊆ E• Given G = (V, E) and a vertex set V′⊆ V , the graphG′= (V′, E′) is an induced subgraph of G is E′has allthose edges of E that connected ve rtices of V′• G and G′are isomorphic if there is a bijectionf : V �→ V′, such that (u, v) ∈ E ⇔ (f(u), f(v)) ∈ E′c� Balaji Raghavachari 128 Algorithm Design and Analysis✬✫✩✪Depth-first search (DFS)DFS (G)for each vertex u ∈ V (G) dou.Color ← W hite // unvisitedu.P arent ← N il// Initializations: add more if neededtime ← 0for each vertex u ∈ V (G) doif u.Color = W hite thenDFS-Visit (u)c� Balaji Raghavachari 129 Algorithm Design and Analysis✬✫✩✪DFS-VisitDFS-Visit (u)u.Color ← Gray // Being processedu.dis ← ++time // Discovery time of u// Add other intializations as neededfor each v ∈ Adj[u] doif v.Color = W hite thenv.P arent ← uDFS-Visit (v)u.Color ← Black // Done processing uu.fin ← ++time // Finish time of uc� Balaji Raghavachari 130 Algorithm Design and Analysis✬✫✩✪Properties of DFS• Running time = O(|E| + |V |).• Active time period of a vertex: [u.dis, u.fin].• Parenthesis theorem: for any two vertices u and v, theiractive time periods are either disjoint or one iscontained in the other.• If v is a descendant of u, u.dis < v.dis < v.fin < u.f in.We say nodes x and y are unrelated if neither is adescendant of the other.• White path theorem: At tim e u.dis, if v is reachablefrom u through a path of white nodes, then v will be adescendant of u in the DFS tree.c� Balaji Raghavachari 131 Algorithm Design and Analysis✬✫✩✪Classification of edges by DF S• Undirected graphs: Tree edges and Back edges. Thereare no cross edges (connecting two unrelated nodes).• Directed graphs:– Tree edges (from parent to child),– Back edges (from descendant to ancestor),– Forward edges (non-parent ancestor to descendant),– Cross edges (from node u to unrelated node v onlyif v.f in < u.dis).c� Balaji Raghavachari 132 Algorithm De sign and Analysis✬✫✩✪Applications of DFS: Topological sort• Given a DAG (directed, acyclic graph) G = (V, E), atopological ordering is a linear ordering of its verticessuch that all edges of G go from left to ri ght.• Each vertex v is given a number top[v] such thatwhenever there is an edge (u, v), then top[u] < top[v].• Observe that if G has a cycle, then it can not have atopological ordering.• Applications of topological sorting: single processorscheduling of tasks with precedence constraints,detecting deadlocks in operating syst and databases,finding shortest paths in DAGs in linear time.• DFS based algorithm: order the vertices in the order ofdecreasing finish times.c� Balaji Raghavachari 133 Algorithm De sign and Analysis✬✫✩✪Topological orderDFS-Visit (u)// topnum is a global variable initialized to |V |u.Color ← Gray // Being processedfor each v ∈ Adj[u] doif v.Color = W hite thenv.P arent ← uDFS-Visit (v)toporder[topnum] ← uu.top ← topnum--u.Color ← Black // Done processing uc� Balaji Raghavachari 134 Algorithm De sign and Analysis✬✫✩✪Correctness of algorithm• If (u, v) ∈ E, then top[u] < top[v].• Proof: Edge (u, v) is one of the following:– Tree edge: v.P arent = u. Therefore u finishes after v(parenthesis theorem), and hence u.f in > v.fin.Therefore top[ u] < top[v ], since topnum is amonotonically decreasing variable.– Forward edge: follows by using induction onprevious case.– Back edge: impossible, since back edge impliescycle, andG is acyclic .– Cross edge: possible only if u.dis > v.fin, whichimplies that u.f in > v.fin, and thereforetop[u] <


View Full Document

UT Dallas CS 6363 - notes-6363-001-2015s-20(1)

Documents in this Course
Exam #1

Exam #1

5 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

greedy

greedy

4 pages

siphon

siphon

18 pages

hwk5

hwk5

3 pages

Load more
Download notes-6363-001-2015s-20(1)
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 notes-6363-001-2015s-20(1) 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 notes-6363-001-2015s-20(1) 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?