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}
If n is composite it has a factor of b then?
b ≤ sqrt(n)
What is a walk?
A sequence of edges (e1e2e3….el) is a walk if there exists a sequence of vertices (v0v1….vl) such that e_j = (e(j-1),e(j))
What is a closed walk?
A walk in which vo=vl
What is a trail?
A walk in which all edges are distinct
What is a path?
A trail in which all vertices are distinct
What is a cycle?
A cycle is a subgraph isomorphic to one of the cycle graphs
What is the length of the walk?
The number of edges in the sequence
What is it to say that two vertices are connected?
a & b are said to be connected if there is a walk such that v0 = a and vl = b
What is a connected graph?
A graph in which each pair of vertices is connected is a connected graph
What are the equivalence classes of G called?
Connected components of G
What is it to say a vertex in a diagraph G is accessible or reachable?
A vertex b is accessible/reachable from a vertex a if there exists a walk from a to b (not the other way round necessarily)
Strongly connected vertices?
If u is reachable from v and v is reachable from u in a diagraph
Weakly connected diagraph?
A diagraph G(V,E) is weakly connected when it becomes a connected graph when you ignore the directions of the edges
In a graph G(V,E), if there is a walk from u to v then?
There is also a path
