Basics

• Regular: all nodes have same degrees
• Walk
• Path: Walk with no repeated vertices
• Cycle: a walk from u to u where the only repeated vertex is u
• Tree: connected; n-1 edges; acyclic
• Local Search guarantees to get $\ge \frac{m}{2}$
  • Each vertex has $\ge \frac{deg(v)}{2}$ edges cut because otherwise we can flip its color to get more cuts

Problem: Identify all nodes reachable from s.
BFS, DFS, AFS
AFS finds a spanning tree rooted at s (bag, mark)
Why does AFS halt?
If we put edge in the bag, get a spanning tree.
Full AFS finds all connected components
CFS: Cheapest First Search
MST: subset of edges of minimum total cost such that all vertices connected
Prim: put the cheapest edge in the bag. If use Priority Queue, $O(Elog(E))$ run-time.
MST Cut Property e is the cheapest edge from S to not S, then must be in the MST.
Kruskal: Go through edges, add as long as it does not make cycles
Boruvka: Add the cheapest edges out of each c.c.

Matching

Bipartite Graph: there is a bipartition X and Y such that each edge connects x and y.
Matching: a subset of edges that do not share an endpoint.
Maximum Matching: A matching with largest number of edges
Perfect Matching: A matching that covers all vertices
Stable matching: There is no unstable pair(u, v not matched to each other, but they prefer each other to their current partners)
GS-algorithm: While a man is unmatched: propose to w(highest in the list)

• $O(n^2)$ (because number of proposals are $n^2$).
• Perfect Matching
• Stable
  GS always finds the Best Valid Partner
  Prove: Man always finds the best. Woman always finds the worst.

Maximum Matching

Augmenting path(with respect to matching M): edges alternate between in M and not in M.
Prove: If there is an aug. path, M is not maximum
Find Maximum Matching: start with an edge, find augment path, …
To find aug. path: direct edges in M from left to right.