Graphs MCQ Quiz in বাংলা - Objective Question with Answer for Graphs - বিনামূল্যে ডাউনলোড করুন [PDF]

Concept:

• A group of trees is nothing but forest.

Explanation:

Example:

• In above graph G there are 3 tress, k=3 and total 6 nodes, n=6 so if we subtract k from n then we will get number of edges equal to 3.
• General formula to get total number of edges will be n – k

Hence option 2 is the correct answer.

Concept:

Using Havel-Hakimi algorithm we can find out simple graph exits or not for a given degree sequence.

Havel-Hakimi algorithm:

Step 1: Sort the sequence in non increasing order.

Step 2: Delete the first degree or element ( Say x )then subtract 1 from the next x elements.

Step 3: Repeat step 1 and step 2 until all the elements remaining are equal to 0 then only simple graph exits. If negative degree encounter after subtraction then No simple graph exists. If not enough elements remaining for subtraction then No simple graph exists.

Calculation:

Option 1: (1, 1, 1, 1, 1 ,1)

Step 1 and 2: remove 1 we get ( 0 , 1 , 1 , 1 , 1) reorder : ( 1, 1 , 1 , 1 ,0 )

 Step 1 and 2 : remove 1 we get ( 0 , 1 , 1 , 0) reorder :  ( 1 , 1 , 0 , 0)

Step 1 and 2: remove 1 we get (0, 0, 0) so simple graph exists

Option 2: (2, 2, 2, 2, 2, 2)

Step 1 and Step 2 : Remove 2 we get  ( 1,1,2,2,2) Reorder : ( 2,2,2,1,1)

Step 1 and Step 2: Remove 2 we get (1,1,1,1)

Step 1 and Step 2 : Remove 1 we get ( 0,1,1) Reorder : (1,1,0)

Step 1 and Step 2 : Remove 1 we get ( 0,0), so simple graph exists.

Option 3: (3, 3, 3, 1, 0, 0)

Step 1 and Step 2: Remove 3 we get (2,2,0,0,0)

Step 1 and Step 2: Remove 2 we get (1,-1,0,0)

Since negative value is present so simple graph does not exist.

Option 4: (3, 2, 1, 1, 1, 0)

Step 1 and Step 2: Remove 3 we get (1,0,0,1,0) Reorder (1,1,0,0,0)

Step 1 and Step 2: Remove 1 we get (0,0,0,0) so simple graph exists.

Havel Hakimi procedure:

Sequence I: 4 7 1 6 3 4 6 2

Sequence II: 3 3 3 3 3 3

Sequence III: 5 4 6 7 6 3 6 5

Concept:

The maximum number of edges in an n node undirected graph G (n, e) without self-loops is present in a complete graph (Kn):

Data:

In complete graph, every node has (n - 1) degree

Number of edges = e_max

Formula:

∑di = 2 × emax

Since there are n node and every node has n - 1 degree

n × (n-1) = 2 × emax

\(e_{max} = \frac{n(n – 1)}{2}\)

Example of the complete graph with n = 5

Tips and Tricks:

\(^nC_2 = \frac{n(n-1)}{2}\)

Concept :

   A graph is said to be disconnected if it is not connected, i.e., if there exist two nodes such that no path in has those nodes as endpoints. The numbers of disconnected simple unlabeled graphs on.

Analysis:

 The maximum number of edges in a simple graph \({(n-K)(n-K+1)} \over 2\) where k is the number of connected components.

If the graph is connected then k=1.

If the graph is disconnected so we have to take k=2 for the maximum number of edges \({(n-2)(n-2+1)} \over 2\)

We assume K_n-1 complete graph and another one vertex so, Maximum number of edges in the disconnected graph is \({(n-1)\times(n-2)}\over 2\)

Formula:

For a simple graph using the formula, a standard formula is \({(n-1)\times(n-2)}\over 2\) 

Explanation:

Here, n=100

n-1=99, n-2=98

\({(n-1)\times(n-2)}\over 2\) =\({(99)\times(98)}\over 2\)=4851

Note: The simple graph won't have parallel edges and self-loops.

Hence the correct answer is 4851.

The correct answer is “option 3”.

CONCEPT:

A graph that contains an edge between every pair of vertices is known as a complete graph.

A complete graph with 6 vertices is:

EXPLANATION:

To get a cycle to length 4, edges of length 4 can be selected to form a cycle.

To get the cycle of length 4, select any 4 vertices.

The number of selection of 4 vertices out of 6 vertices is: ⁶C₄ i.e. 15

Example:

Consider 4 vertices {a, b, c, d}, total cycles using 4 vertices are:

a-b-c-d, a-b-d-c, a-c-b-d, a-c-d-b, a-d-b-c, a-d-c-b

Therefore, number of cycle using n vertices is (n-1)!

But number of distinct cycles of length 4 with vertices (a,b,c,d) is 3.

{Since abcd and adcb are same, in different directions}

So, the total number of distinct cycles of length 4 is:

= 15 × 3

= 45

Hence, the correct answer is "option 3".

The correct answer is option 1

EXPLANATION:

A cycle length 3 requires 3 vertices

Total number of ways choosing 3 vertices from 8 vertices = \({{\rm{\;}}^8}{{\rm{C}}_3} = 56\)

The probability that three vertices form a cycle = probability of an edge between vertices 1 and 2 + probability of an edge between vertices 2 and 3 + probability of an edge between vertices 1 and 3

The probability that three vertices form a cycle = \(\frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} = \frac{1}{8}\)

So, the expected number of unordered cycles of length 3 = \(56\times{1\over8}=7\)

Data:

d_min = 3

edges = |E| = 25

Formula:

\({{\rm{d}}_{{\rm{min}}}}{\rm{\;}} \le \frac{{2\left| {\rm{E}} \right|}}{{\left| {\rm{n}} \right|}} \le {\rm{\;}}{{\rm{d}}_{{\rm{max}}}}\)

Calculation

\(3{\rm{\;}} \le \frac{{2 \times 25}}{{\rm{n}}}\)

\({\rm{n\;}} \le \frac{{2 \times 25}}{3} \le 16.66\)

∴ n_max = 16

So, maximum possible value of n is 16.

Concepts:

The complementary graph G' of a simple graph G has the same vertex set as G, and two vertices are adjacent in G' if and only if they are not adjacent in G.

An n-vertex self-complementary graph has exactly half number of edges of the complete graph.

∴ e = e’ = 39

Sum of edges in G and G’ is equal to edges in complete graph with n vertices

Formula:

\(^{n}{{C}_{2}}=e+e'\)

Calculation:

\(\frac{\text{n}\left( \text{n}-1 \right)}{2}=39+39\)

n² - n - 156 = 0

(n - 13) (n + 12) = 0

Since n > 0

∴ n = 13.

Important Points:

n is the number of vertices in G or G’

The correct answer is (A) and (B) Only

Key Points

• Tree:
  • A tree is a type of graph that is acyclic, meaning there are no cycles or loops. It consists of nodes connected by edges in a hierarchical structure. Each node, except the root, has exactly one parent, forming a parent-child relationship. 
  • There are no loops or cycles in a tree structure.
  • A tree is a connected graph, meaning there is a unique path between any pair of nodes.
  • Each node in a tree (except the root) has exactly one parent.
  • There is a unique topmost node called the root from which all other nodes are descendants.
  • Trees are usually directed, meaning edges have a specific direction (from parent to child).
  • Trees are commonly used for hierarchical data representation, such as file systems, organizational charts, and expression trees. Binary Search Trees (BSTs) are a specific type of tree used for efficient searching and sorting.
  •     
• Graph:
  • A graph is a more general structure that can be cyclic or acyclic. It consists of nodes (vertices) and edges connecting these nodes. There are no strict hierarchical relationships between nodes in a graph.
  • A graph may or may not be connected. There can be isolated components within a graph.
  • Nodes in a graph can have multiple incoming edges, meaning they can have multiple parents.
  • There is no concept of a root node in a general graph.
  • Graphs can be directed or undirected. In directed graphs, edges have a direction, while in undirected graphs, edges have no direction.
  • Graphs are more general-purpose and can represent a wide range of relationships between entities. They are used in applications like social networks, road networks, dependency graphs, and more.
  • 
  • Option D is disconnected graph so it is not tree
  • 

Only option A and B are acyclic graph so correct answer is option 1.