General

Question 1

What is a Graph?

Answer 1

A finite, nonempty set V, the vertex set along with set E, the edge set, whose elements e in E are pairs (a,b) with a,b in V

Question 2

What is an Undirected Graph?

Answer 2

An undirected graph is a graph which the edge set consists of unordered pairs

Question 3

What is a Directed Graph?

Answer 3

A Digraph/Directed graph is a graph in which pairs are ordered

Question 4

A bipartile graph?

Answer 4

A graph is bipartile if it is a non empty edge set, and it’s vertex set can be decomposed into two disjoint nonempty subsets

Question 5

Define the degree of a vertex in an undirected graph

Answer 5

The degree of a vertex is the no of edges that include the vertex

Question 6

Define a neighbour of vertex v

Answer 6

In a graph a vertex u is a neighbour of a vertex v if (u,v)eE

Question 7

Define a successor of a vertex V

Answer 7

In a directed graph a successor of a vertex v is a vertex u such that (v,u)eE

Question 8

Define a predecessor for vertex v

Answer 8

In a directed graph a predecessor of a vertex v is a vertex u such that (u,v)eE

Question 9

What does it mean for two graphs to be isomorphic?

Answer 9

Two graphs are said to be isomorphic if there exists a bijection a(v)-> v_2 such that (u,v)eE if and only if (a(u),a(v))eE

Question 10

What is a Chromatic number?

Answer 10

The smallest K which G has been a K colouring

Question 11

Define the floor and ceiling of X

Answer 11

Floor is the largest integer that is equal or smaller than X

The ceiling is the largest integer that is equal or larger than X

Question 12

Define a walk and it’s length?

Answer 12

A set of edges is a walk if there exists a corresponding sequence of vertices

Its length is the number of edges in the sequence

Question 13

Define a trail

Answer 13

A trail is a walk where all the edges are distinct

Question 14

Define a path

Answer 14

A path is a trail in which all the vertices are distinct

Question 15

Define a cycle

Answer 15

A cycle is a path that includes 3 or more edges

Question 16

Define what it means for two verticies to be connected

Answer 16

In a graph two vertices are said to be connected if there is a walk between them

Question 17

Define what it means for a graph to be connected

Answer 17

A graph is connected in which every pair of vertices is connected

Question 18

Define what it means for a to be strongly connected to b

Answer 18

A and b in a digraph are strongly connected if there is a walk from a to b AND a walk from b to a

Question 19

Define what it means for a to be accessible from b

Answer 19

In a discredited graph a vertex b is accessible from a vertex a if there is a walk a to b

Question 20

Define what it means for a graph to be strongly connected

Answer 20

A directed graph is said to be strongly connected if all pairs of vertices are strongly connected

Question 21

Define what it means for a graph to be weakly connected

Answer 21

A directed graph is weakly connected when one vertex ignore the directedness of the edges it becomes a connected undirected graph

Question 22

Define what it means for vertex b to be accessible from vertex a

Answer 22

In a Digraph a vertex b is accessible from a if there is a walk from a to b

Question 23

Define what it means for graph to be acyclic?

Answer 23

A graph is acyclic if it has no cycles

Question 24

What is a Tree?

Answer 24

A tree is a connected acyclic graph

Question 25

What is a Forest?

Answer 25

A forest is a graph who’s connected components are trees

Question 26

What is a leaf?

Answer 26

A vertex is a leaf in a tree if it has degree 1

Question 27

What does it mean for a vertex to be isolated

Answer 27

if the vertex has a degree zero

Question 28

what is a Spanning Tree

Answer 28

A subgraph of a graph is a spanning tree if it is a tree containing every vertex in v

Question 29

What is a root?

Answer 29

A vertex in a digraph is a root of every other vertex if it is accessible to all

Question 30

What is an arborescence/ Directed Tree?

Answer 30

A digraph is a DT/arborescence if it contains a root and if you ignore the directness it becomes a connected tree

Question 31

What is a Spanning arborescence?

Answer 31

A subgraph of a Digraph is a SA if its an arborescence that contains all vertices in G

Question 32

What is a permutation?

Answer 32

A permutation of n objects is a bijection from set {1,…,n}

Question 33

Define the fix(sigma)

Answer 33

fix(sigma)={j | sigma(j)=j}

Question 34

Define the sign(sigma)?

Answer 34

identity sigma =+1
If sigma is of a singular cycle length L then sign is (-1)^L-1
if sigma can be decomposed into k disjoint cycles then the sign ,L=sum(all cycles) (-1)^L-k

Question 35

What is a Spreg?

Answer 35

A single predecessor graph is a directed graph in which each vertex other than the distinguished vertex V has exactly on predecessor while V has none

Question 36

What is an Eulerian Trail?

Answer 36

It is a trail which includes all edges once only

Question 37

What is an Eulerian tour/cycle?

Answer 37

It is a closed eulerian trail

Question 38

What does it mean for a Graph to be eulerian?

Answer 38

A multigraph is eulerian if it contains a eulerian tour

Question 39

What is an Hamiltonian Trail?

Answer 39

A hamiltonian trail is a trail which includes every vertex in V (once?)

Question 40

What is an Hamiltonian tour/cycle?

Answer 40

Is a closed hamiltonian trail

Question 41

What does it mean for a graph to be Hamiltonian

Answer 41

A graph is Hamiltonian if it contains a hamiltonian tour

Question 42

What is an bridge

Answer 42

An edge is a bridge iff it G\e has more than one connected component

Question 43

What is a Planar Diagram ?

Answer 43

A planar diagram for a graph G with Edge set E is a collection of simple curves that represent edges and have property g_i and g_j iff edges e_i and e_j iff the edges meet at their corresponding vertex

Question 44

Girth?

Answer 44

If a graph contains at least one cycle then the girth is the length of the shortest cycle

Question 45

What is a subdivision of a graph?

Answer 45

A subdisvion of a graph is a graph from by removing an edge and replacing it with a path, with each new vertex having a degree of 2

Question 46

What does it mean for two graphs to be homeomorphic?

Answer 46

two graphs are said to be homoeopmorphic if they are isomorphic subdivisions of the same graph.