31. Which of these adjacency matrices represents a simple graph?
32. Which of the following is not a topological sorting of the given graph?
33. Which of the following graphs are isomorphic to each other?
34. If a connected Graph (G) contains n vertices what would be the rank of its incidence matrix?
35. Given the following program, what will be the 3rd number that'd get printed in the output sequence for the given input?
#include <bits/stdc++.h>
using namespace std;
int cur=0;
int G[10][10];
bool visited[10];
deque <int> q;
void fun(int n);
int main()
{
int num=0;
int n;
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>G[i][j];
for(int i=0;i<n;i++)
visited[i]=false;
fun(n);
return 0;
}
void fun(int n)
{
cout<<cur<<" ";
visited[cur]=true;
q.push_back(cur);
do
{
for(int j=0;j<n;j++)
{
if(G[cur][j]==1 && !visited[j])
{
q.push_back(j);
cout<<j<<" ";
visited[j]=true;
}
}
q.pop_front();
if(!q.empty())
cur=q.front();
}while(!q.empty());
}
Input Sequence:-
9
0 1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 1
0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0
0 0 1 0 0 0 1 0 0
0 0 0 0 0 1 0 1 1
0 0 0 0 1 0 1 0 0
1 0 1 0 0 0 1 0 0
#include <bits/stdc++.h>
using namespace std;
int cur=0;
int G[10][10];
bool visited[10];
deque <int> q;
void fun(int n);
int main()
{
int num=0;
int n;
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>G[i][j];
for(int i=0;i<n;i++)
visited[i]=false;
fun(n);
return 0;
}
void fun(int n)
{
cout<<cur<<" ";
visited[cur]=true;
q.push_back(cur);
do
{
for(int j=0;j<n;j++)
{
if(G[cur][j]==1 && !visited[j])
{
q.push_back(j);
cout<<j<<" ";
visited[j]=true;
}
}
q.pop_front();
if(!q.empty())
cur=q.front();
}while(!q.empty());
}9
0 1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 1
0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0
0 0 1 0 0 0 1 0 0
0 0 0 0 0 1 0 1 1
0 0 0 0 1 0 1 0 0
1 0 1 0 0 0 1 0 036. What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with n vertices?
37. A connected planar graph having 6 vertices, 7 edges contains . . . . . . . . regions.
38. Which of the following symbols represent nodes having exactly one child?
i. Δ
ii. ◊
iii. ∇
iv. T
v. ⊥
i. Δ ii. ◊ iii. ∇ iv. T v. ⊥
39. On which of the following statements does the time complexity of checking if an edge exists between two particular vertices is not, depends?
40. Determine the longest string which is described by the given Directed Acyclic Word Graph.
Read More Section(Graphs)
Each Section contains maximum 100 MCQs question on Graphs. To get more questions visit other sections.