Definitions/Propositions Flashcards
What is a graph?
A graph G(V,E) is finite, with a non-empty set V (the vertex set) along with a second set E (edge set) whose elements e ∈ E are pairs (a,b) with a,b ∈ V
What is an undirected graph?
A graph G(V,E) whose edges are not ordered pairs
What is a diagraph?
A diagraph or directed graph G(V,E) is a graph whose edge set consists of ordered pairs
What are adjacent vertices?
Two vertices a,b ∈ V in an undirected graph G(V,E) are said to be adjacent or neighbours IFF (a,b) ∈ E
Predecessor/Successor of a vertex?
If the directed edge e(u,v) appears in a diagraph then u is a predecessor to v and v is a successor to u. u is the tail vertex of e and v is the tip vertex of e.
Properties of the adjacency matrix?
- A is not unique, depends on the numbering scheme for the vertices. If renumbered, rows & columns will change accordingly
- If G(V,E) is undirected then A is symmetric
- If the graph has no loops then A_jj = 0
What is an adjacency list?
In an undirected graph G(V,E) the adjacency list associated with a vertex v is the set A_v = { u | u ∈ V and (u,v) ∈ E}
What is the predecessor list?
In a directed graph G(V,E), the predecessor list of vertex v is the set P_v = { u | u ∈ V and (u,v) ∈ E}
What is the successor list?
In a directed graph G(V,E), the successor list of vertex v is the set P_v = { u | u ∈ V and (v,u) ∈ E}
What is it to say two graphs are isomorphic?
G1 and G2 are isomorphic if there exists a bijection a: V1 –> V2 such that (a(x),a(y)) ∈ E2 if (x,y) ∈ E1
Two graphs isomorphic implies what about cardinality?
If G1 and G2 are isomorphic then |V1| = |V2| and |E1| = |E2|
If G1 and G2 are isomorphic then what does this imply about their degree?
deg(v) = deg(a(v)) for all v ∈ V1 and deg(u) = deg(a^-1(u)) for all u ∈ V2
What is the degree sequence of undirected graph?
A list of the degrees of the vertices (arranged in ascending order)
What is the degree of a vertex?
The number of edges that include the vertex
If G1 and G2 are isomorphic then this implies what about their degree sequence?
They have the same degree sequence
What is a a subgraph of a graph G(V,E)?
A graph G’(V’,E’) where V’⊆V and E’⊆E
Given a graph G(V,E) and a subset V’⊆V, what is the subgraph induced by V’?
Subgraph G’(V’,E’) where E’ = { (u,v) | u,v ∈ V’ and (u,v) ∈ E}
What is a k-colouring?
Map phi: V –> {1,2,…,K} with the property that adjacent vertices are assigned distinct “colours”. i.e. (u,v) ∈ E implies phi(u) does not equal phi(v)
What is the chromatic number?
chi(G) is the smallest k for which G has a K-colouring
A graph G is bipartite IFF?
chi(G) = 2
If H is a subgraph of G then? (chromatic number)
chi(H) ≤ chi(G)
If H is a subgraph of G and G is k-colourable then?
so is H
“Floor of x”?
max{k ∈ integers | k ≤ x}
“Ceiling of x”?
min{k ∈ integers | k ≥ x}
