CS Free MCQ Bank

[ Option B ]

The chromatic number of a graph is the minimum number of colors required to color the vertices so that no two adjacent vertices have the same color.
In the given graph, vertices such as e, f, g, and h form a structure where each is connected in a way that three colors are not sufficient to avoid conflicts between adjacent vertices. When we attempt coloring with 3 colors, at least two adjacent vertices will end up with the same color.
However, using 4 colors, we can assign colors to all vertices so that no adjacent vertices share the same color. Therefore, the minimum number of colors required is 4.

[ Option A ]

Different Shortest-Path Algorithms are designed for different types of path problems in graphs. The key is to identify how many sources and destinations are involved and what type of path computation is required.
(P)  A person wants to visit from one place to another place in the shortest period.

• This represents a situation where we want to find the shortest path from a starting point to a destination through stages.
• This is modeled using a Multi-stage Graph.

A Multi-Stage Graph Algorithm divides the graph into stages and computes the shortest path from the source to the destination using dynamic programming. It is commonly used when the movement must follow a stage-wise structure.
(Q)  A person wants to visit M places in shortest period.

• Here, a single person starts from one source and we want the shortest paths to multiple destinations.
• This is exactly the problem solved by Dijkstra’s Algorithm.

Dijkstra’s Algorithm computes the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edges.
(R)  All N persons want to visit all M places in shortest.

• This implies we need the shortest distance between every pair of locations.
• This type of problem is solved by Floyd’s Algorithm (Floyd–Warshall Algorithm).

Floyd’s Algorithm computes the shortest paths between every pair of vertices in a graph using dynamic programming and an adjacency matrix.

IMPORTANT ALGORITHMS:

[ Option B ]

We use the Handshaking Theorem, which states that the sum of the degrees of all vertices in an undirected graph equals twice the number of edges:
Sum of degrees of all vertices=2×Number of edges
Here, E=31. So,
Sum of degrees = Sum of degrees=2×31=62
The given condition is that each vertex has degree at least 3. Now, let the number of vertices be n. Then, Sum of degrees ≥ 3n. We already know the exact sum is 62, so, 3n ≤ 62.
Finally solve for n, n ≤ 62/3 = 20.66. Since the number of vertices must be an integer, the maximum possible number of vertices is 20.

[ Option D ]

A Spanning Tree of a graph is a subgraph that includes all the vertices of the graph and is connected without forming any cycles. For any connected graph with V vertices, a tree structure must have exactly V-1 edges to remain connected and acyclic.

[ Option C ]

[ Option B ]

In graph theory, a graph is made up of a set of nodes, which are technically called vertices, and a set of line segments that connect pairs of these nodes, which are called edges.
Vertices represent the objects or points in the graph, while edges represent the connections or relationships between them.

[ Option D ]

A Simple Graph is a type of graph that does not contain any parallel edges (multiple edges) or self-loops (an edge from a vertex to itself). Each edge in a simple graph connects two distinct vertices, and there can be at most one edge between any pair of vertices.

[ Option C ]

In an adjacency matrix, we represent a graph using a two-dimensional array of size n×n, where n is the number of vertices. Each row and column correspond to a vertex, and the value stored in a cell tells us whether an edge exists between two vertices.

If the graph is weighted, the cell stores the weight instead of just 0 or 1. Since the matrix always needs space for n² entries, the space complexity is O(n²). This representation can be used for directed or undirected graphs as well as weighted or unweighted graphs.

The only drawback is that it uses more memory for sparse graphs, but it provides quick access to check if an edge exists between two vertices.

[ Option B ]

Breadth First Search (BFS) explores a graph level by level, meaning it visits all the neighboring vertices of a node before moving to the next level. To achieve this order, BFS uses a Queue, which follows the First In First Out (FIFO) principle. 
Depth First Search (DFS), on the other hand, explores a graph by going as deep as possible along one path before backtracking. This behavior is naturally supported by a Stack, which follows the Last In First Out (LIFO) principle.

[ Option C ]

Depth First Search (DFS) is a graph traversal algorithm that visits all vertices and edges of a graph.
The time complexity of DFS depends on how the graph is represented:
Adjacency Matrix:
In an adjacency matrix, we use an n×n matrix to represent edges. For each vertex, we must check all n possible vertices to see if an edge exists.
For n vertices, we check n entries for each vertex, so the total time complexity becomes O(n²).
Adjacency List:
In an adjacency list, each vertex stores only its connected neighbors, so during DFS each vertex is visited once taking O(n) time and each edge is traversed once taking O(e) time, resulting in a total time complexity of O(n+e).

• Both DFS and BFS have the same time complexity, it only depends on the graph representation.

[ Option C ]

In an undirected graph, each edge connects two vertices and contributes 1 degree to each of its end vertices. Therefore, every edge adds a total of 2 to the sum of degrees of all vertices. 
If the graph has e edges, the total sum of the degrees of all n vertices becomes 2e. This result is known as the Handshaking Theorem in graph theory.

[ Option A ]

An Isolated Vertex in a graph is a vertex that has no edges connected to it. The degree of a vertex is defined as the number of edges connected to that vertex. Since an isolated vertex has no connecting edges, its degree is 0.

[ Option D ]

In graph theory, when a network of roads and intersections is drawn on a plane without crossing edges, it forms a planar graph. For planar graphs, the relationship between the number of vertices (V), edges (E), and regions or faces (F) is given by Euler’s Formula: V-E+F=2
Here, faces (regions) represent the areas enclosed by the roads.
There are 20 shopping malls, so V=20. Each mall is connected by 3 roads, so the total number of edges is:
E=(20*3)/2 = 30
Because, each road connects two malls, so we divide by 2.
Using Euler’s formula:
20-30+F=2
F=12
These 12 regions include one outer region. Since parks can only be built in enclosed regions, the outer region is excluded.
Maximum number of parks = 12-1 = 11

[ Option B ]

In graph theory, a Complete Graph is a simple graph in which every pair of distinct vertices is connected by an edge.

• A complete graph is highly connected and contains cycles.
• Every vertex is connected to all other n−1 vertices, so its degree is n−1.
• The total number of edges in a simple complete graph is given by (n(n−1))/2.

[ Option D ]

In an Adjacency List representation of an undirected graph, each vertex stores a list of its adjacent vertices. 
To determine the total number of edges, we need to traverse all vertices, which takes O(n) time, and also traverse all adjacency lists, which takes O(e) time. Therefore, the total time required is O(n+e).

[ Option A ]

In any graph, the sum of the degrees of all vertices is always even because each edge contributes 2 to the total degree count. As a result, vertices with odd degree must occur in pairs so that their total contribution is even.

[ Option A ]

In a Regular Graph, every vertex has the same degree d, meaning each of the n vertices is connected to d edges. If we add the degrees of all vertices, the total becomes n*d.
However, each edge is counted twice in this total. Therefore, to get the actual number of edges, we divide by 2. 
Hence, the number of edges in a regular graph with n vertices and degree d is nd/2.

[ Option D ]

Graph traversal algorithms are specifically methods used to visit all nodes of a graph, such as:

• DFS (Depth First Search) Using Stack.
• BFS (Breadth First Search) Using Queue.

[ Option B ]

A Walk in a graph is a sequence of vertices and edges where each edge connects the previous vertex to the next one. It can repeat vertices or edges, there is no restriction.

• Open Walk, a walk is said to be open if it starts and ends at different vertices.
• Closed Walk, a walk is closed if it starts and ends at the same vertex.

In graph theory, a Cycle is a closed walk, meaning it starts and ends at the same vertex, and no other vertices or edges are repeated except the first and last vertex being the same.
A Circuit is indeed a closed walk (starts and ends at the same vertex) where no edge is repeated. Vertices may repeat, but edges do not.