Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
34 Cards in this Set
- Front
- Back
Network |
4-tuple N = (G,s,t,c), G = (V,E), s = source, t = sink, c = capacity function: Maps edges to R# |
|
Legal flow |
Function that Maps edges to R#, where 1. f(e) <= c(e) (capacity constraint), and 2. sum (f(in-degree)) <= sum (f(out-degree)) (conservation of flow) |
|
Capacity conservation |
f(e) <= c(e) legal flow function returned at most capacity function |
|
conservation of flow |
sum (f(in-degree)) <= sum (f(out-degree)) |
|
Value of legal flow |
Net flow, I.E. sum (f(in-degree)) - sum (f(out-degree)) |
|
Walk |
Finite alternating sequence of vertices and edges |
|
Trail |
A walk with no repeated edges |
|
Circuit |
Closed trail (same start and end vertex) |
|
Eccentricity |
If v is the maximum distance between v and any other vertex |
|
Diameter |
Maximum eccentricity of G |
|
Radius |
Minimum eccentricity of G |
|
Center |
Vertex whose eccentricity = rad(G) |
|
Peripheral vertices |
Distance (v,u) = Diameter (G) |
|
Vertex connectivity |
Minimum number of vertices whose removal will disconnect G or reduced it to K1 |
|
Edge connectivity |
Minimum number of edges whose removal will disconnect G or reduced it to K1 |
|
Height of tree |
Max distance (level) from root |
|
Adjacency matrix |
A[I,j] = number of edges from I to j in G |
|
Children |
Vertices at level k+1 adjacent to some vertex at level k are it's children |
|
Pendant vertex |
Leaf, degree 1 |
|
Connected |
Path between any two vertices |
|
Non identical digraphs |
2^p(p-1) |
|
Non identical graphs |
2^p(p-1)/2 |
|
Isomorphism |
Bijection f: V(G) -> V(H) |
|
N-ary Tree vertices |
P <= n^0 + n^1 ... + n^k = (n^(k+1) - 1)/n-1 |
|
Source-separating set of vertices |
U subset of V(G) where s exists in U but t doesn't exist in U |
|
Number of walks length n is (AG)^n[i,j] |
Base case: n = 1 (AG)^1[i,j] = number of edges from i to j and that's the number of walks of length 1 from i to j. Assuming it is true for all i and j, then we know that sumFromK=OneToP((AG)^n[i,k]•(AG)^1[k,j]) = (AG)^n+1[i,j] by definition of matrix multiplication |
|
Distances from i to j in weighted digraph |
The sum of weights of the edges in the shortest path from i to j, or +inf if no path from i to j |
|
Prove that if G is disconnected Gc is connected |
Let u and v be verified in Gc. there is a path from u to v, two cases: 1) uv is not in G, then it's in Gc for sure 2) uv is in G then there are at least 2 disconnected components in G, and thus there must be some vertex w such that wu and wv does not exist in G, other wise w would beer on the same component but does exist in Gc, thus v--w--u will be the path in Gc, thus Gc is connected |
|
Sum(deg(T)) |
2|E(T)| |
|
|E(T)| |
p-1 |
|
|E(T)| proof |
=p-1. strong induction. base case: p=1 |E(T)|= 1. inductive step: result true for all trees with <= p vertices. take a tree T - {e}, which will divide into two trees T1 and T2. so |E(T)| = |E(T1)| + |E(T2)| +|{e}| = |V(T1)| - 1 + |V(T2)| - 1 + 1 = |V(T)| - 1 |
|
if G is disconnected |E(G)| <= (p-1)(p-2)/2 |
m |
|
ores theorem |
G has p >= 3 and deg(x) + deg(y) >= p, this G had a Hamilton cycle. Find maximal path in G say P1 (v1, v2,v3 ...vk, v1). P1 can be arranged as a cycle, if vk not adjacent to v1 it's OK bc there must be some vertex vi such that v1vi and vi-1vk exist in G. if this was not so every time v1 is adjacent to a vi vk cannot be adjacent to vi-1, and thus deg(vk) + deg(v1) <= k - 1 which contradicts the premise. so we can make P1 into a cycle C1. if E(C1) = E(P1) then we have a Hamilton cycle if not choose a vertex not in C1 say x to extend it into P2 and we can again make it into a cycle, until we have a Hamilton cycle |
|
Eulers theorem |
has Euler circuit iff deg(v) is even for all v. => suppose has Euler circuit, then if we traverse C and delete each edge as we visit it, then the degrees of each vertex will reduce by 2 on every visit vo will reduce by 1 initially and then at the end too, thus all v have even degree. <= suppose all vertices of even degree base case: q = 0 then trivial walk, it contains Euler circuit. inductive step: suppose true for all <= q then for G a graph with q + 1 edges and all even degree, then find a cycle and if all the edges of G are in the cycle then it's an Euler circuit, otherwise, for each connected components not in C we can find a cycle with <=q of all even degree so by inductive hypothesis each component has a Euler circuit, so if you travel down C and into each Euler circuit, in the end you will have traveled down a huge Euler circuit |