Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Amira Cormier on Monday November 2, 2015. The Class Notes belongs to CS4245 at California State University - East Bay taught by IstvanSimon in Fall. Since its upload, it has received 40 views. For similar materials see /class/234373/cs4245-california-state-university-east-bay in ComputerScienence at California State University - East Bay.
Reviews for AnalysisofAlgorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/02/15
CS 4245 Fundamental concepts 010803 These classnotes were prepared by Saruney Elebiary and revised by Professor Simon 1 f 2 tA 3 t A WA bA eA 39 4 lgtO lgtN NgtN NgtN f X An algorithm can be viewed as computing a function that maps inputs to corresponding outputs tA X number of operations algorithm A takes on input X to termination Though the function tA is useful and important conceptually in practice it would be more useful to define a function that measured the performance of the algorithm as a function of the size ofthe input n rather than the input X itself In general however there are many inputs ofthe same size and the algorithm may take different amounts of time on these inputs There are three common ways to deal with this difficulty wA n maX tA X size X n worst case performance bA n min tA X size X n best case performance eA n 2 p X tA X eXpected time often pX lXsizeXn ifthere eXists a constant cgt0 and an no 6 N such that forall n 2 no we havefn g cg n Examples fn n 100n2 22nlogn2 Vn fnOg1n true fr1 Ogzn true ifthere eXists a constant cgt0 and an no 6 N such that forall n 2 no we havefn 2 cg n CS 4245 011003 Chapter 1 Graph Theom G V E V set of veltices E set of edges each edge is an unordered pair of vertices If xy 6 E we say that xy 39oins velteX X to velteX y Veltices X and y are ad39acent if xy 6 E The edge xy is incident to veltices X and y and viceversa If xy 6 E X and y are called the end vertices of the edge xy Kquot is the complete graph on n veltices in which every pair of vertices isjoined by an edge Equot is the m graph on n veltices in which there are no edges at all So E1 K1 is called the trivial graph The degree of a vertex X is the number of edges incident to X Handshaking Lemma The sum of the degrees of all the veltices of a graph is twice the number of edges Corollary The sum of the degrees is always even If G V E is a graph G1 V1 E1 is a subgragh ofG ifG1 is a graph and V1g V and E g E G1 is a Qrogersubgraph ofG if G1 g G but G1 15 G EX G1V1E1 V1aE1 a E1K1 G2V2E2 V2ab E2 a b E2 G3V3E3 V3a b E3ab a b K2 64 v4 E4 v4 a b c d e E3 ab bc cd de ea A fivecycle 05 A V E Let V1 g V GV1 the subgraph of G induced by V1 V1 E1 E1Xye EXer1 A subgraph G1 V1 E1 of G V E is induced ifG1 GV1 A subgraph G1 V1 E1 of G V E is spanning ifV1 V If G V E is a graph A walk in G is a sequence of vertices X0 X1 X2 X Such thatXiXm e E for i 01 M The walk is said to be from X0 to X and is of length l A trai is a walk in which all the edges are distinct A path is a walk in which all vertices are distinct l is the length ofthe walk A graph G V E is connected if 3 a walk from any vertex X to any verteX y We use the term maximal to refer to some set or Graph with some property which is contained in no other set or Graph A set with some property is maximum if it is a set of largest cardinality with the given property If a set is maXimum with respect to some property then it is clearly also maXimal but in general a set may be maXimal without being maXimum We use these concepts in the definition below G V E A connected component of G is a maXimal connected subgraph of G Matching Set of edges which are verteX disjoint Theorem 1 Every graph is the disjoint union of its connected components CS 4245 011503 1 Edison Genius is 1 inspiration and 99 perspiration 2 Einstein A theory should be as simple as possible but not simpler 3 Mozart Learn with the masters 4 Richard Feynman Quantum Electrodynamics Physicist Theorem 1 Every graph G V E is the disjoint union of its connected components Proof To prove 1 Every vertex X is in w connected component of G V1ye V3anX ywalkinG 61 GV1 Claim G1 is a connected component of G which contains X X 6 V1 since 3 a walk the trivial walk from X to X G1 is connected because let y1y2 6 V1 walkfrom X y also 3 walk from X to y2 in G Every verteX of the X y walk is in V1 because for every vertex 2 3 X 2 walk in G Similarly every verteX in X y2 walk is n V1 Since G1 is induced every edge of these walks is also in G1 So hence the X y walk and X y2 walk is in G1 So 3 y1 y2 walk in G1 So G1 is connected Claim 61 is maximal connected Suppose by contradiction 61 is not connected So 3 62 such that 61 g 62 and 62 is connected Hence X is a vertex of 62 Let y be the vertex of 62 Since 62 is connected 3 X y walk in 62 So this walk is a walk in 6 So y 6 V1 So 61 and 62 have the same vertices Every edge of 62 is also an edge of 61 because it joins 2 vertices of V1 and also it is in 61 because 61 is induced So 61 62 Hence 61 is maximal connected To grove Two connected components of 6 have no vertex in common Let 61 62 be 2 connected components of 6 61 it 62 By contradiction If not so then Letx be a common vertex 61 V1 E1 G2 V21E2 Let63 V1u V2E1u E2 61g63 63 is connected because ify1 y2 6 V3 Then if y1y2 are both in V1 Then 3 y1 y2 walk in G1 hence in G3 lfy1y2 are both in V2 Then 3 y1 y2 walk in G2 Hence in Ge Otherwise ify1 6 V1 and y2 6 V2 Then 3 y1 X walk in G1 hence in 63 and an X y2 walk in G2 hence in G3 3 y1 y2 walk in G3 Since G1 is a connected component so maximal connected and G1 g G3 it follows that G1 63 Similarly for G2 Hence G2 63 So G1 G2 Contradiction Since two connected component have no vertices in common it follows they have no edges in common either Every edge xy 6 E is in some connected component Prove this as an exercise CS 4245 012403 Awalkfromxtoy iswifxy A cycle x0 x1 X is a closed walk of length at least 3 such that xox1xi1 is a path Agrath V E rammva V2 gv VV1GV2V1mV2 such that every edge joins a vertex in V1 to a vertex in V2 Theorem 2 A graph is bipartite it contains no odd cycles Length of a cycle is number of edges of cycle The distance from X to y in G dGx y is the length of a shortest path from X to y if one exists 7 or otherwise Proof gt Suppose G contains an odd cycle say x0 x1 x2 x And is odd If G were bipartite with vertex sets V1 V2 wog without loss of generality let x0 6 V1 So every even end vertex is in V1 and every odd end vertex is in V2 So x2 6V2 impossible since x0 X and V1 0 V2 6 lt wog assume G is connected Let x be a vertex V1 u e V dax u is even V2u e Vdax u is odd Suppose claim is not true So 3 uv such that uv 6 V1 or uv 6 V2 and UV 6 E Since G is connected clearly V V1 u V2 V1 V2 In the 15 case dX u and dX v are both even Otherwise dX u and dX v are both odd In both cases we have a closed walk of odd length Claim This partition ofthe vertices works In other words every edge joins a vertex in V1 to a vertex in V2 Let a shortest path from X to u be X0 X1 X2 Xr U Let a shortest path from X to v be yo y1 y2 yS v We have X0 yo X Since both paths are shortest iin yj then i j Let X be the verteX on path X0 X1 Xi u While is also on path yoy1yS v with large indeX X Xi yj then XiXr u v ysys1yi is an odd cycle CS 4245 012703 A graph that is acyclic ie has no cycles is a forest A graph that is connected and acyclic is a tree Theorem Proof A graph G is a tr iff i G is maximal m G is acyclic and for all xy e E Xy e V G xy has a cycle ii G is minimal connected G is connected and for all xy 6 E GXy is not connected GVE XgV G XGVX XX GX G Xy V E xy G xy V E u xy To prove 1 G is a tree gt G is maximal acyclic G is connected and acyclic so it is m So it remains to prove that for all xy e E G xy has a cycle Pick xy e E an arbitrary nonedge Then to prove G xy has a cycle Since G is connected 3 an Xy path in G This path has length at least 2 since xy e E XX0X1Xy SOXX0X1Xy X is a closed walk in G xy of length at least 3 Since X0X1 X is a path it follows this is a cycle 2 If G is maximal acyclic then G is a tree So G is acyclic so it only remains to show that G is connected Pick Xy two arbitrary vertices To show 3 Xy path in G If xy 6 E we are done Otherwise G xy has a cycle Since G has no cycles this cycle must include xy Let cycle be X X0X1X2X y X X0 SOXX0X1X2X yisa path inG Xyand l 22 So none ofthe edges of X0 X1 X is xy So this path is in G and we are done 3 G is tree gt G is minimal connected Since G is a tree it is connected So it remains to prove that G is minimal connected ie V xy 6 E G Xy is not connected Pick an arbitrary edge xy and consider G xy Suppose G xy is connected So 3 a path fromxtoyinG Xy X X0 X1X2X y has length at least 2 So X X0X1X2X y X is a closed walk of length 3 in G Theorem 4 Proof Furthermore since xox1 x is a path it is a cycle Contradiction since G is acyclic If G is minimal connected then G is a tree G is connected So it remains to show that G is acyclic Suppose not Then G has a cycle Say X xox1x2xxo l2 2 So x x0 6 E Hence G xxo is not connected Butxox1x2x is a path in G xxo Contradiction Every nontrivial tree contains a vertex of degree 1 Suppose not Then 3 G nontrivial tree such that it has no vertex of degree 1 Exercise Then the minimum degree of G cannot be 0 because G is Connected so it can have no isolated vertices So minimum degree is at least 2 So G contains a cycle Contradiction V nontrivial tree has at least 2 vertices of degree 1 CS 4245 Theorem Proof 012903 EM tree with n vertices has n 1 edges By induction on n For n gt 1 then it is the trivial tree which has 0 edges Inductive step Pick an arbitrary tree G with n 1 vertices G is nontrivial n 1 2 2 hence G has a vertex of degree 1 say X So G X has n vertices G X is acyclic since G X lt G amp G is acyclic G X is connected because let u v be 2 vertices in G X Then 3 u v path in G since G is connected So none ofthe vertices of this path is X since u v are in G X And every other verteX must have degree at least 2 So this path is also in G X Hence G X is connected So G X is a tree with n vertices So G X has n 1 edges by the reduction hypothesis Since G has exactly 1 more edge than G X does The theorem follows Given a directed graph G VE with positive realvalued capacity function cE gt R we define a flow in G as a nonnegative realvalued function Such that 1 0 g fu v g cu v for all edges uv 2 V u a st flow into u flow out of u EvueE fV U E uvaE fU V Max Flow Min Cut Theorem maximum flow value minimum cut capacity separating s and t To prove i fis maximum flow iff ii there is no augmenting path in the residual network iff iii value of flow f capacity of some cut separating s and t CS 4245 012903 G V E directed seV source cEgtR teV sihk fEgtR 1 XY 6 E fXv S 0 XY 2 VUEV S t EWEEfvuEWEEfUV maximize the flow from s tot value of flow f 2st E f 8V Ev e E fVS Easy to prove exercise Value of flow E E E f vt Ewe E f tv A cut that separates s fromt X g V s e X t e X Cut X X set of edges thatjoih a vertex in Xto a vertex hot in X or viceversa The capacity of a cut cXX is defined to be Exye EX Ex and quotOWE x c xy that is it is the sum of the capacities of all the edges that join a vertex in X to a vertex outside of X Value offcXX GrVEr xyeE Ergtlty E0XyfXygt0UyXXy Eampfgtltygt0 CrXY 0 XY f XV Cr W f XV FordFulkerson Theorem A directed path form s tot in G is called an augmenting path If we have an augmenting path then we can increase the value of flow by min cf xy xy is an edge of augmenting path FordFulkerson The following are equivalent i f is a maximum flow ii 3 no augmenting path in G iii 3 cut X g V value of few f c X X Proof i gt ii obvious since if 3 augmenting path then we can increase flow ii gt iii X X e V 3 s X directed path in G s e X t er because there is no augmenting path claim value of flow f capacity of this cut Now every edge xy 6 E such that X e X y e X must be saturated for xy e E Further every edge yX where y e X X e X has zero flow otherwise xy e E Since there can be no edge leaving X in Gf we conclude these two facts But then value of flow f capacity ofthis cut ll iii gt ii On the one hand every flow f value of f g capacity ofm cut So in particular value of maXimum flow g min capacity of a cut So if we have equality we must have max flow FordFulkerson Algorithm 1 Start with a flow f for example zero flow 2 Compute residual network Gr 3 Search for an augmenting path by breadth first search If we find it increase flow and repeat Otherwise halt we have maximum flow Every iteration will cost 0 n m So 0 k n m k number of iterations
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'