Chapter 4 Flashcards
Def/ A tree is:
A tree is a simple connected graph with no cycles
Def. A forest is:
A forest is: a graph with no cycles
Thm: If u,v in V(G), and G is a tree, there is only 1 path from u to v.
Proof. There exists a path P.1 (u,v1,v2,..v) from u to v because connected. BWOC, assume there is another path P.2 (u,w1,w2,..w) from u to v.
Since P.1 != P.2, there exists some smallest k s.t. v.k+1 != w.k+1. Let j be the smallest value such that v.j = w.j (AKA where they meet back up).
Construct cycle: v.k,v.k+1,…,v.j, w.j-1, w.j-2,… w.k+1, w.k (w.k=v.k). If any 2 vertices in here coincide, then you could have picked diff. k,j to match. Thus there forms a cycle, thus contradiction.
Thm: If G is a tree of order p, size 1, then q=p-1
Base case: p=1 is a single vertex. 0 = p-1 = 1-1 = 0.
Let all trees of order <=n have q=p-1. Let G be a tree with order n+1.
Pick edge e in G. Since not on cycle bc tree, it is a bridge. Thus G-e is disconnected, where each component is a tree, say G1 and G2. G1 and G2 both have that p<=n, so q=p-1 holds for both of them. and, n1+n2 = n+1.
q1 = n1-1, q2=n2-1.
q = n1-1 + n2-1 + 1 (each one plus the edge e).
=> q= n1+n2-1 = (n+1) -1
=> q=n, AKA q=p-1 for graphs of size n+1, thus recursive case done.
Thm: If G connected and q=p-1, then G is a tree.
Proof: BWOC, assume G is not a tree, so G contains a cycle C.
Let e be an edge in C s.t. e is not a bridge (on a cycle). Then, G-e is connected.
Repeat until there are no cycles, thus still connected and thus you have a tree, and by thm. that tree has q=p-1. But, G has at least p edges because we just took one away. This contradicts assumption that g has p-1 edges.
Def/ A subgraph T of a connected graph G is a spanning tree if:
A subgraph T of a connected graph G is a spanning tree if T is a tree of the same order as G. (NOTE: spanning trees are made from removing edges not vert.)
Def/ Let G be a network:
Let G be a network, with edge values f(e): E -> Reals, G connected. If H is a subgraph, f(H) = [e in E(H)] SUM(f(e))
Algorithm/ Kruskal’s algorithm finds a minimal spanning tree how?
Choose first edge e1 s.t. f(e.1) is minimized
Continue adding edges such that f(e.j) is as small as possible, without creating a cycle.
Quit when number of edges is p-1 (thus, it is a tree).
Thm: Kruskal’s algorithm (pick smallest edges until you have a spanning tree) creates a minimal spanning tree.
If alg. stops before a tree is constructed, then graph is disconnected, thus there must be an edge which connect components, thus the algorithm doesn’t stop.
Let T.0 be a minimal spanning tree. Want f(T) = f(T.0)
Order edges based on weights. Let e.i = uv be the first edge in T but not in T.0.
But there exists a uv path P in T.0 (bc connected), so P+ uv is a cycle in T.0.
Since T has no cycles, there is edge e.0 in C not in T (AKA, since there is a cycle with uv in T.0, since T has uv, it must be missing an edge along C).
Create new spanning tree T1 = T.0 +e.1 - e.0.
Since T.0 is a minimum, f(T.1) <= f(T.0)
e.i was an edge of smallest value to be added w/o making a cycle.
So, f(e.i) <= f(e.0) thus f(T.1) <= f(T.0).
Thus, f(T.0) = f(T.1). Thus, that holds for any differences between T and T.0.
Def/ Let (G,f) be a network, then the distance d(u,v) is:
the d(u,v) is the minimum f(p), where p is a uv path AKA it is the least cost path between two vertices.
A shortest path is:
A shortest path is a uv path s.t. d(u,v) = f(p)
Algorithm: Dijkstra’s Algorithm is used to find the shortest distance between two points how?
Start at vertex u, then add tentative distances to all adjacent vertices. Then, add the lowest distance vertex to “best” list of vertices. Then start at any tent. dist vertex and repeat, each time adding the closest vertex to the ‘best’ list
Thm: Dijkstra’s Algorithm works to find the shortest distance by adding vertices to a tentative distance and ‘best’ lists. When it terminates, the tent. dist l(v) for each v is the actual distance.
Induct on i: base i=0, d(u0,u0) = 0.
Thus assume some vertices in S.i have l(v) = d(u0,v).
Let P = v0v1v2,…,vk, v.0 = u.0, v.k = u.i+1 be a shortest path with subpath P.j = v0v1,…,v.j.
Let j be smallest s.t. v.j is not in set of completed vertices S.i. Since P.j is also a shortest path and v.j-1 in S.i, v.j has been assigned a tentative distance.
l(v.j) <= l(v.j-1) + f(v.j-1,v.j) because tent. dist only updated if smaller.
l(v.j) <= l(v.j-1) + f(v.j-1,v.j) = f(p.j) <= f(P) <= l(u.i+1) because f(P) = dist(u0,u.i+1).
But, l(u.i+1) <= l(v.j) by choice of u.i+1.
Thus, above inequality is all equal, thus f(P.j) = f(P) = d(u0,ui+1) = l(u.i+1) Thus tent. dist is real dist.
Lemma: If p=v0,v1,v2,…vn is a shortest path from v0 to vn, then pj = v0,v1,…,vj is also a shortest path from v0 to v.j.
Pf on homework; simple, will cover elsewhere
