USC CS170 Final Exam

Kruskal's Algorithm

Builds a tree one edge at a time.

- Sort all edges by their weights

(Loop)

- Choose the minimum weight edge and join - corresponding vertices (subject to cycles)

- Go to the next edge

- Continue until all vertices are connected

Runtime of Kruskal's Algorithm

O(ElogE + V*E)

Minimum Spanning Tree (MST)

A spanning tree of a weighted undirected graph with the minimum total edge weight

Bipartite Graph

A graph is bipartite if the vertices can be partitioned into two disjoint (independent) sets X and Y such that all edges go only between X and Y (none from X to X or Y to Y)

T/F A graph is bipartite if and only if it is two-colorable

T

Matching (Def)

A subset of edges is matching if no two edges have a common vertex (mutually disjoint)

Maximum matching

A maximum matching is a matching with the largest possible number of edges

Walk

"A walk is a sequence of vertices in the graph that traverse edges in the graph"

Walk vs path

"A walk is a path if all vertices are distinct"

Equivalence relation.

a relation that is reflexive, symmetric, and transitive

p --> q

-P v q

-(p --> q)

P ^ -q

"If p, then q"

Converse

Contrapositive

Inverse

Converse: "If q, then p" (q --> p)

Contrapositive: "If not q, then not p) (-q --> -p)

Inverse" "If not p, then not q (-p --> -q)

CNF (Conjunctive Normal Form)

Separated with AND's

DNF (Disjunctive Normal Form)

Separated with OR's

Contrapositive of (p → q)

(-q → -p)

Permutations (ordered or not ordered)

Ordered

Permutation function

P(n,k) = n!/(n-k)!

Combination function

C(n,k) = n!/(k!(n-k)!) = (nk)

Combinations - does order matter?

No

Counting using bijection formula

total/bars!(total-bars)!

Handshaking lemma for directed graphs

The sum of the out-degrees of all vertices equals the sum of the in-degrees of all vertices and equals the number of edges

Circuit

A walk that ends where it begins

Cycle

A circuit that only repeats the first and last vertice

Handshaking lemma for undirected graphs

The degree of a vertex v in an undirected graph is the number of edges that are incident on v

The sum of the degrees of all the vertices of the graph equals twice the number of edges

net degree = 2E

Eulerian walk

A walk which traverses every edge of the graph exactly once

Degree's of vertices to make a Eulerian walk possible

Either 0 or 2 odd vertices

Eulerian cycle

A Eulerian walk that starts and ends at the same vertex

Hamiltonian path

A path that visits every vertex noce

Hamiltonian cycle

A Hamiltonian path that ends where it begins

3 equivalent statements for trees

1. G is a tree

2. Every two nodes of G are joined by a unique path

3. G is connected and V = E + 1

Euler's formula

If G is a connected planar graph with V vertices, E edges and F faces, then V - E + F = 2

Coloring planar graphs

Any simple planar graph can be colored with <= 4 colors