Graphs and Networks Learning Quizzes: Master Graph Theory Concepts

Question 1

In a graph, what is the degree of a vertex?

Accepted Answer

The number of edges connected to the vertex.

Answer

The number of vertices connected to the vertex.

Answer

The number of paths passing through the vertex.

Answer

The number of cycles containing the vertex.

Question 2

What is the minimum number of edges needed for a connected graph with n vertices?

Accepted Answer

n-1

Answer

n

Answer

n+1

Answer

2n-1

Question 3

Which type of graph has directed edges?

Accepted Answer

Directed graph

Answer

Undirected graph

Answer

Weighted graph

Answer

Complete graph

Question 4

In a complete graph with n vertices, the number of edges is given by:

Accepted Answer

n(n-1)/2

Answer

n

Answer

n(n-1)

Answer

n(n+1)

Question 5

In a minimal spanning tree:

Accepted Answer

Each edge connects two components

Answer

Each edge is the shortest edge in the graph

Answer

Each edge forms a cycle

Answer

Each edge has the largest weight

Question 6

For a graph to be Eulerian, which condition must be met?

Accepted Answer

All vertices have even degree

Answer

All vertices have odd degree

Answer

The graph contains a cycle

Answer

The graph is connected

Question 7

In a graph, a Hamiltonian path is:

Accepted Answer

A path that visits every vertex once

Answer

A path that starts and ends at the same vertex

Answer

A path that contains all edges in the graph

Answer

A path that forms a cycle

Question 8

What is the time complexity of Kruskal's algorithm for finding a minimum spanning tree?

Accepted Answer

O(E log V)

Answer

O(V)

Answer

O(V log V)

Answer

O(E^2)

Question 9

What is the chromatic number of a graph?

Accepted Answer

The minimum number of colors needed to color the vertices so that no two adjacent vertices have the same color

Answer

The maximum number of colors needed to color the vertices so that no two adjacent vertices have the same color

Answer

The number of colors in the graph

Answer

The degree of the most connected vertex in the graph

Question 10

Which of the following is a Hamiltonian cycle?

Accepted Answer

A cycle that visits every vertex in the graph exactly once

Answer

A cycle that visits every edge in the graph exactly once

Answer

A path that visits every vertex in the graph exactly once

Answer

A path that visits every edge in the graph exactly once

Question 11

What is the time complexity of Floyd-Warshall's algorithm for finding all-pairs shortest paths in a weighted graph?

Accepted Answer

O(V^2)

Answer

O(V)

Answer

O(V log V)

Answer

O(E log V)

Question 12

In a graph with n vertices, what is the maximum number of edges it can have?

Accepted Answer

n(n - 1)/2

Answer

n - 1

Answer

n^2 - n

Answer

2n - 2

Question 13

What is the maximum number of edges in a complete graph with n nodes?

Accepted Answer

n(n-1)/2

Answer

n(n+1)/2

Answer

n^2

Answer

(n-1)^2

Question 14

What is the difference between a directed and an undirected graph?

Accepted Answer

Directed graphs have edges with a specified direction, while undirected graphs have edges with no direction.

Answer

Directed graphs have edges with no direction, while undirected graphs have edges with a specified direction.

Answer

Directed graphs can have cycles, while undirected graphs cannot.

Answer

Directed graphs have more applications in computer science than undirected graphs.

Question 15

Which of the following is a planar graph?

Accepted Answer

A tree with 10 nodes

Answer

A complete graph with 5 nodes

Answer

A K4 graph

Answer

A graph with a cycle

Question 16

Which of the following is a Hamiltonian cycle in a graph?

Accepted Answer

A cycle that visits every node in the graph exactly once

Answer

A cycle that visits every edge in the graph exactly once

Answer

A cycle that has the maximum possible length

Answer

A cycle that starts and ends at the same node

Question 17

In a complete graph with n vertices, the chromatic number is equal to:

Accepted Answer

n

Answer

n-1

Answer

n+1

Answer

n^2

Question 18

For a tree with n vertices, what is the maximum possible degree of any of its vertices?

Accepted Answer

n-1

Answer

n

Answer

n+1

Answer

n^2

Question 19

In a graph, which path visits each vertex exactly once and returns to its starting point?

Accepted Answer

A---B---C---D---E---A

Answer

A---B---C---D---E

Answer

A---B---C---D---E---F

Question 20

In a network where edges represent distances, which algorithm can be used to find the shortest path between two vertices?

Accepted Answer

Dijkstra's algorithm

Answer

Depth-first search

Answer

Breadth-first search

Answer

Kruskal's algorithm

Question 21

A minimum spanning tree (MST) is a tree that connects all vertices in a graph:

Accepted Answer

With the minimum number of edges

Answer

With the maximum weight

Answer

With the minimum cost

Answer

With the maximum number of vertices

Question 22

In graph theory, the degree of a vertex refers to:

Accepted Answer

The number of edges connected to it

Answer

The number of vertices connected to it

Answer

The number of paths connected to it

Answer

The number of cycles connected to it

Question 23

A graph with 'n' vertices and 'e' edges such that e = n(n-1)/2 is known as a:

Accepted Answer

Complete graph

Answer

Tree

Answer

Bipartite graph

Answer

Directed graph

Question 24

According to Euler's theorem, in a connected planar graph, the number of faces is given by:

Accepted Answer

V - E + F

Answer

V + E - F

Answer

V - E - F

Answer

V + E + F

Question 25

For a bipartite graph 'G' with vertex sets 'U' and 'V', if 'G' has a perfect matching, which of the following is true?

Accepted Answer

|U| = |V|

Answer

|U| < |V|

Answer

|U| > |V|

Answer

The graph is not necessarily connected.

Question 26

What is the degree of a vertex in a graph?

Accepted Answer

The number of edges connected to the vertex

Answer

The number of vertices adjacent to the vertex

Answer

The number of paths that pass through the vertex

Answer

The number of cycles that contain the vertex

Question 27

Define a minimum spanning tree (MST).

Accepted Answer

A subgraph of a connected graph that spans all vertices and has the minimum possible total weight

Answer

A tree that connects all vertices of a graph with the fewest possible edges

Answer

A path that visits all vertices of a graph with the shortest possible distance

Answer

A subgraph that contains all cycles of a graph

Question 28

What is the time complexity of Dijkstra's algorithm?

Accepted Answer

O(E log V)

Answer

O(V)

Answer

O(V^2)

Answer

O(E)

Question 29

Describe the key difference between directed and undirected graphs.

Accepted Answer

In directed graphs, edges have a direction, while in undirected graphs, they do not.

Answer

In undirected graphs, vertices have weights, while in directed graphs, edges have weights.

Answer

In directed graphs, cycles are not allowed, while in undirected graphs, they are

Answer

There is no difference between directed and undirected graphs.

Question 30

Explain the concept of a topological sort for a directed acyclic graph (DAG).

Accepted Answer

An ordering of vertices such that for every directed edge (u, v), u precedes v in the ordering.

Answer

An ordering of edges such that for every directed edge (u, v), u precedes v in the ordering.

Answer

A subgraph that contains all cycles of the DAG.

Answer

A spanning tree of the DAG.

Question 31

What is a Hamiltonian path?

Accepted Answer

Visits each vertex exactly once, forming a path

Answer

Visits each edge exactly once, forming a path

Answer

Visits each vertex exactly once, forming a cycle

Answer

Visits each edge exactly once, forming a cycle

Question 32

Which graph is planar?

Accepted Answer

Cycle graph with 6 vertices

Answer

Complete graph with 5 vertices

Answer

Bipartite graph with 10 vertices

Answer

Graph with 10 vertices and 30 edges

Question 33

Which of the following properties does NOT apply to a complete graph?

Accepted Answer

The graph is planar.

Answer

Every pair of vertices is connected by an edge.

Answer

The degree of each vertex is one less than the number of vertices in the graph.

Answer

The graph is connected.

Question 34

What is the chromatic number of a bipartite graph?

Accepted Answer

2

Answer

1

Answer

3

Answer

It can vary depending on the graph.

Question 35

Which of the following is a type of directed graph?

Accepted Answer

Digraph

Answer

Tree

Answer

Cycle

Answer

Graph

Question 36

What is the chromatic number of a graph that can be coloured using a maximum of 3 colours?

Accepted Answer

3

Answer

1

Answer

2

Answer

4

Question 37

Which algorithm is designed to find the shortest path between two vertices in a weighted graph?

Accepted Answer

Dijkstra's algorithm

Answer

Depth-first search

Answer

Breadth-first search

Answer

Kruskal's algorithm

Question 38

Determine the degree of a vertex that has three edges connected to it in a graph.

Accepted Answer

3

Answer

2

Answer

4

Answer

1

Question 39

Which algorithm is used to find the shortest path between two vertices in a weighted graph?

Accepted Answer

Dijkstra's algorithm

Answer

Depth-first search

Answer

Breadth-first search

Answer

Prim's algorithm

Question 40

What is the maximum number of edges possible in a complete graph with 'n' vertices?

Accepted Answer

n(n-1)/2

Answer

n^2

Answer

n

Answer

n log n

Question 41

Which condition is necessary for a graph to be considered Eulerian?

Accepted Answer

Every vertex has even degree

Answer

The graph does not contain any cycles

Answer

The graph is planar

Answer

The graph is connected

Question 42

Name the algorithm used to construct a minimum spanning tree for a connected, undirected graph.

Accepted Answer

Kruskal's algorithm or Prim's algorithm

Answer

Floyd-Warshall algorithm

Answer

Topological sort

Answer

Dijkstra's algorithm

Question 43

Which graph traversal technique ensures visiting all vertices in a connected graph?

Accepted Answer

Depth-first search or breadth-first search

Answer

Floyd-Warshall algorithm

Answer

Topological sort

Answer

Dijkstra's algorithm

Question 44

Define the chromatic number of a graph.

Accepted Answer

The minimum number of colors required to color the graph without any adjacent vertices sharing the same color

Answer

The number of edges in the graph

Answer

The maximum number of vertices in the graph

Question 45

In a network flow problem, which problem aims to determine the maximum possible flow from a source vertex to a sink vertex in a network?

Accepted Answer

Max-flow problem

Answer

Eulerian circuit problem

Answer

Shortest path problem

Answer

Minimum spanning tree problem