Graphs

⏱️

15 questions · 24 marks · 40 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.

Q1NAT1 markHandshake

A simple graph has 9 vertices of degree 2 and 6 vertices of degree 3. How many edges?

Numerical answer: ________

Q2NAT2 marksComponents

Maximum edges in a simple graph with 12 vertices and 4 components?

Numerical answer: ________

Q3MCQ1 markDAG

A DAG is a directed graph with:

• (A) no vertex of in-degree 0
• (B) all edges in both directions
• (C) exactly one source
• (D) no directed cycle

Q4MSQ2 marksDegrees

Which degree sequences belong to some simple graph?

• (A) 3, 3, 2, 2, 2
• (B) 3, 3, 3, 1
• (C) 1, 1, 1, 1
• (D) 4, 4, 4, 4, 4

Q5NAT1 markGraphs

Number of simple undirected graphs on 3 labelled vertices?

Numerical answer: ________

Q6MCQ1 markSpace

A sparse graph with n = 10⁵ and e = 3·10⁵ is best stored as:

• (A) adjacency lists
• (B) an adjacency matrix
• (C) an incidence matrix
• (D) any; all use Θ(n + e)

Q7NAT2 marksOnes

A directed simple graph has 25 edges. How many 1s are in its adjacency matrix?

Numerical answer: ________

Q8MCQ2 marksOutput

What is the line printed for vertex 5?

#define N 8
struct node {
    int v;
    struct node *next;
};
struct node *adj[N];                      /* adjacency lists, all NULL at start */

void addEdge(int a, int b)                /* insert b at the head of a's list */
{
    struct node *p = malloc(sizeof(struct node));
    p->v = b;
    p->next = adj[a];
    adj[a] = p;
}

int main(void)
{
    int e[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {4, 5}, {6, 7}};
    int i;
    struct node *p;
    for (i = 0; i < 8; i++) {
        addEdge(e[i][0], e[i][1]);
        addEdge(e[i][1], e[i][0]);
    }
    for (i = 0; i < 6; i++) {
        printf("%d:", i);
        for (p = adj[i]; p != NULL; p = p->next) printf(" %d", p->v);
        printf("\n");
    }
    return 0;
}

• (A) 5: 4
• (B) 5: 3 4 5
• (C) 5: 3 4
• (D) 5: 4 3

Q9NAT2 marksA²

In the running example, what is (A²)[0][0]?

Numerical answer: ________

Q10MCQ2 marksValid BFS

Which is NOT a valid BFS order of the running example from 0?

• (A) 0 1 2 4 3 5
• (B) 0 2 1 3 4 5
• (C) 0 1 2 3 4 5
• (D) 0 2 1 4 3 5

Q11MCQ2 marksOutput

What does this print?

#define N 8
int g[N][N];

void build(void)
{
    int e[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {4, 5}, {6, 7}};
    int i;
    for (i = 0; i < 8; i++) g[e[i][0]][e[i][1]] = g[e[i][1]][e[i][0]] = 1;
}

int seen[N];

void dfs(int v)
{
    int w;
    seen[v] = 1;
    printf("%d ", v);
    for (w = 0; w < N; w++)
        if (g[v][w] && !seen[w]) dfs(w);
}

int main(void)
{
    int v, c = 0;
    build();
    for (v = 0; v < N; v++)
        if (!seen[v]) {                   /* a new component starts here */
            printf("{ ");
            dfs(v);
            printf("} ");
            c++;
        }
    printf("\n%d\n", c);
    return 0;
}

• (A) { 0 2 4 5 3 1 } { 6 7 } then 2
• (B) { 0 1 3 5 4 2 } { 6 7 } then 2
• (C) { 0 1 3 5 4 2 6 7 } then 1
• (D) { 0 1 2 3 4 5 } { 6 7 } then 2

Q12MCQ1 markCost

DFS on adjacency lists runs in:

• (A) Θ(n²)
• (B) Θ(n + e)
• (C) Θ(e²)
• (D) Θ(n log n)

Q13NAT2 marksLevels

BFS from 0 in the running example: how many vertices are at distance exactly 1?

Numerical answer: ________

Q14MSQ1 markFacts

Which are true?

• (A) DFS needs a queue.
• (B) BFS gives fewest-edge paths from the start.
• (C) Counting components restarts a traversal at unseen vertices.
• (D) A traversal visits only the start’s component.

Q15MCQ2 marksDirected BFS

BFS from 1 in 1→2, 1→3, 2→4, 3→4, 4→5, 5→2 (smaller first) visits:

• (A) 1 2 4 5 3
• (B) 1 3 2 4 5
• (C) 1 2 3 4 5
• (D) 1 2 3 5 4

0: 2 1
1: 4 3 0
2: 4 0
3: 5 1
4: 5 2 1
5: 4 3

{ 0 1 3 5 4 2 } { 6 7 } 
2