Discrete Definitons Flashcards
Given a graph G(V, E), define a walk in a graph
A sequence of edges (e1, e2,…,eL) is a walk if there exists a corresponding sequence of vertices (v0, v1,…,vL) such that ej = (vj-1, vj ). Note that the vertices don’t have to be distinct. If v0 = vL, it is a closed walk
Given a graph G(V, E), define a trail in a graph
A trail is a walk in which all the edges ej are distinct
Given a graph G(V, E), define a path in a graph
A path is a trail in which all the vertices are distinct
Given a graph G(V, E), what is meant by saying G is a connected graph?
Two vertices are said to be connected if there is a walk between them, and a graph in which each pair of vertices is connected is a connected graph.
Given a graph G(V, E), what is meant by the degree of a vertex v?
The degree of a vertex v is the number of edges that include the vertex
Explain what is meant by the degree sequence of a graph
The degree sequence of graph is a list of the degrees of the vertices, arranged in ascending order.
Explain what is meant by saying a graph is a tree
A tree is a connected, acyclic graph
Explain what is meant by saying a vertex v in a graph is a leaf
A vertex v in a tree is called a leaf if deg(v)=1
Explain what is meant by saying two graphs G1(V1,E1) and G2(V2,E2) are isomorphic
Two graphs G1(V1, E1) and G2(V2, E2) are said to be isomorphic if there exists a bijection α : V1 → V2 such that the edge (α(a), α(b)) ∈ E2 iff (a, b) ∈ E1.
Explain what is meant by saying a graph is bipartite
A graph G(V,E) is said to be a bipartite graph if
• it has a non empty edge set E ≠ ∅; and
• its vertex set V can be decomposed into two non empty, disjoint subsets
V = V1 U V2 with V1 ∩ V2 = ∅; and V1 ≠ ∅ ; and V2 ≠ ∅ ;
in such a way that all the edges in E connect a member of V1 with a member of V2
(u, v) ∈ E ⇒{ u ∈ V1 and v ∈ V2
{ or u ∈ V2 and v ∈ V1.
What is a k colouring of a graph G?
A k-colouring of G is a function Φ : V → {1,…,k} that assigns distinct values (called colours) to adjacent vertices
What is the chromatic number, χ(G), of G?
The chromatic number χ(G) is the smallest number k such that G is k-colourable
What is the adjacency matrix of a graph G?
First numbering the vertices, so that the vertex set becomes V = {1, 2,…,n} for a graph on n vertices. The adjacency matrix A is an nxn matrix whose entries are given by:
Aij = {1 if (i, j) ∈ E
{0 otherwise
Given a connected graph G(V, E) explain what is meant by saying G is Hamiltonian?
A graph that contains a Hamiltonian tour (a cycle that contains every vertex) is said to be a Hamiltonian graph
Given a connected graph G(V, E) explain what is meant by saying G has an Eulerian Tour?
An Eulerian tour in a multigraph G(V,E) is a trail that includes each of the graph’s edges exactly once and starts and finishes at the same vertex.
Given a connected graph G(V, E) explain what is meant by saying G is planar?
A graph G is said to be planar if it is possible to draw it in such a way that the edges intersect only at their vertices
Given a connected graph G(V, E) explain what is meant by saying G has girth g?
If a graph G(V, E) contains one or more cycles then the girth of G is the length of a shortest cycle.
What is meant by saying a graph is acyclic?
A graph is acyclic if it doesn’t include any cycles
Explain what is meant by saying 2 vertices in a directed graph are strongly connected
Two vertices a and b in a directed graph are strongly connected if b is accessible from a and a is accessible from b. Additionally, we regard a vertex as strongly connected to itself.
Explain what is meant by a relation ~ on a vertex set V is an equivalence relation
A relation ~ on a set S is an equivalence relation if it is:
reflexive: a ~ a for all a ∈ S;
symmetric: a ~ b ⇒ b ~ a for all a, b ∈ S;
transitive: a ~ b and b ~ c ⇒ a ~ c for all a, b, c ∈ S.
What does it mean for two graphs to be homeomorphic?
Two graphs G(V, E) and G’(V’, E’) are said to be homeomorphic if they are isomorphic to subdivisions of the same graph.
What is a spanning tree in an undirected graph G(V,E)?
A subgraph of G(V,E) is a spanning tree if it is a tree that contains every vertex in V
What is a spanning arborescence rooted at v in a digraph G(V,E)?
A subgraph T(V,E’) of a digraph G(V,E) is a spanning arborescence if T is an arborescence that contains all the vertices of G.
What is a a single predecessor graph (spreg) rooted at v in a digraph G(V,E)?
A spreg with distinguished vertex v is a directed graph G(V,E) in which each vertex other than the distinguished
vertex v has exactly one predecessor while v itself has no predecessors
