A graph G is an ordered pair (V,E) where V is a set and E is a set of two element subsets of V.
E ⊆ { {x,y}: x,y in V, x≠y }
Typical data structure: { {A, B, C, D}, { {A,B}, {B,C}, {A,D} } }
Vertices Edges connecting nodesA graph can be directed or undirected. In a directed graph, an edge (v1, v2) is not the same as (v2, v1) since the edge is directed from 1->2.
Graphs are the most pervasive abstraction in CS. They model networks of transportation, the world wide web, PageRank.
A graph on n vertices where every pair of vertices is connected is called an n-clique, denoted by Kn. Kn = (V, E) where V = {1, 2, ..., n} and E = { {i,j}: 1 ≤ i ≤ j ≤ n}. The number of edges in Kn is nC2 (number of two vertex combinations).
Two endpoints with one linear path connecting all vertices. A path on n vertices, denoted by Pn, is the graph Pn = (V, E) where V={1,2...,n} and E = { {i,i+1}: 1 ≤ i ≤ n-1 }. The total number of edges is n-1.
A path with connected endpoints. A cycle on n ≥ 3 vertices the graph Cn = (V, E) where V = {1, 2, ..., n} and E = { {i,i+1}: 1 ≤ i ≤ n-1} ∪ { {1,n}}. The number of edges in Cn is n.
Formal concept for classifying graph types. Two graphs G = (V, E) and G' = (V', E') are said to be isomorphic if there exists a bijection f: V -> V' s.t.
{x,y} in E iff {f(x), f(y)} in E'
The number of edges in a graph. The size of an n-vertex graph is bounded by nC2 (the n-clique).
The degree or valency of a vertex v in a graph G = (V, E) denoted by dG(v) is the number of neighbors of v in G:
dG(v) = |{u in V: {v,u} in E}|
A graph where every vertex has degree k is a k-regular and a graph is regular if it is k-regular for some k.
The handshake lemma says the number of people at a cocktail party who shake hands with an odd number of others is even. Formally, the number of odd-degree vertices in a graph is even.
A distance between two vertices in a graph is the number of edges in the shortest path (also called the graph geodesic).
epsilon(v) of vertex v is the greatest geodesic distance between v and its furthest vertex in G.
A radius r of a graph is the minimum eccentricity of any vertex.
A diameter d of a graph is the maximum eccentricity of any vertex. Algorithm to compute: find shortest path for all vertices, take the max.
A simple, unweighted directed graph G is an ordered pair (V,E) where V is a set and E is a set of ordered pairs from V.
E is a subset of {(x,y):x,y in V, x ≠ y}A Directed graph does not have the notion of degree. Instead, indegree and outdegree of a vertex v in G, defined as |{u in V: (u,v) in E}| and |{u in V: (v,u) in E}| respectively.
Multiple edges between the same pair of vertices (this makes the collection of edges a multiset). A self-loop is an edge to and from a single vertex.
Numerical weights are associated to edges. Good for modeling physical networks.
A tour of G traces every edge exactly once: walk T = (v1,e1,v2,e2,...,vn,en,vn+1) s.t. ei ≠ ej for all e in T.
A tour is Eulerian if vn+1 = v1, V(T)=V and E(T)=E. An Eulerian tour traverses all edges and ends where it started.
A graph is Eulerian iff it has a Eulerian tour.
Theorem: A graph is Eulerian iff it is connected and each vertex has an even degree. (Every vertex must have an exiting edge for every entering edge)
Psudo-proof: if graph is eulerian, then every vertex must be entered and exited, therefore even number of edges. if even edges, then prove v1=vn+1 (ends where it starts) and n = |E|
Example: A network requires users that are close to have different wavelengths to prevent interference. Users can be modeled as vertices, connected by an edge if close. A colouring of this graph G is an assignment of colours to vertices s.t. no two adjacent vertices have the same colour.
The example is restated as, what is the minimum number of colours needed for a colouring of G.
A k-colouring of G is a function c:V->{1,2,...,k}, s.t. if {v,u} in E, then c(v) ≠ c(u). The smallest k in Naturals for which a k-colouring of G exists is called the chromatic number of G.
If k-colouring of G exists, the graph is k-colourable.
Proposition: If the degree of every vertex in a graph G is at most k, then the chromatic number of G is at most k+1.
Proof by induction on number of vertices. For one vertex, one colour is needed. Assume hypothesis. For a graph with n vertices, with chromatic number k. Add one vertex and you get chromatic number of at most k+1.
A bipartite graph can be partitioned into two parts s.t. edges of the graph only go between the two parts, but not inside a part (think domain to codomain or red-black tree).
A graph G is said to be bipartite iff there exists U ⊆ V s.t. E ⊆ { {u,u'}:u in U and u' in V \ U}
The sets U and V \ U are called the classes of G.
A complete bipartite graph Km,n is a graph with ALL possible edges between the two classes. Km,n = (V,E) s.t V={1,2,...,m+n} and E={ {i,j}: 1 ≤ i ≤ m, m+1 ≤ j ≤ m+n}
Another way to state the definition is a bipartite graph is 2-colourable.
Proposition: A graph is bipartite iff it contains no cycle of odd length. (cycle must end on same side)
Given a bipartite graph G=(V,E), a matching B in G is a set of disjoint edges.
Theorem: A bipartite graph W=(V,E) wtih classes B and G has a perfect matching iff |B|=|G| and