All topics

Graph Theory

12 questions

Q1
A directed graph has vertices A, B, C, D, E and edges AB, BA, BC, CD, DC, DB, DE. How many distinct cycles does it contain?
Q2
A graph has vertices A, B, C, D, E with edges: A-B, A-C, B-C, B-D, C-D, D-E. How many edges does it have?
Q3
A connected graph has 7 vertices. How many edges does a spanning tree of this graph have?
Q4
An undirected graph has vertices A, B, C, D, E, F with edges AB, AC, BC, DE. How many connected components does it have?
Q5
A tree has 8 vertices. How many edges does it have?
Q6
A directed graph has edges AB, BC, CA, BD, DC. Which of these is a simple path from A to D?
Q7
A directed graph has vertices A, B, C, D and edges AB, BC, CA, BD. Is this graph a DAG (directed acyclic graph)?
Q8
A directed graph has vertices A, B, C and edges AB, BC, CA. How many paths of length exactly 3 go from vertex A back to A?
Q9
Given the adjacency matrix below, how many edges does the graph have?
     A  B  C  D
A  [ 0, 1, 1, 0 ]
B  [ 1, 0, 1, 1 ]
C  [ 1, 1, 0, 1 ]
D  [ 0, 1, 1, 0 ]
Q10
A directed graph has edges AB, AD, BC, DB. How many paths of length exactly 2 go from A to C?
Q11
A complete graph K5K_5 has 5 vertices where every pair is connected. How many edges does it have?
Q12
A directed graph has the adjacency matrix below. List all the edges as comma-separated pairs (e.g. AB, BC).
    A  B  C  D
A [ 0, 1, 0, 1 ]
B [ 0, 0, 1, 0 ]
C [ 0, 0, 0, 0 ]
D [ 0, 1, 0, 0 ]