• Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

Card Range To Study

through

image

Play button

image

Play button

image

Progress

1/34

Click to flip

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