menu
search
Log In

GO Book for GATECSE 2022GATE Overflow Book for GATE CSE 2022

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects


GATE Overflow
Recent questions tagged graph-theory

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts
Webpage for Graph Theory:

Recent questions tagged graph-theory

1 vote
2 answers
1
GATE CSE 2021 Set 1 | Question: 16
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.
asked Feb 18 in Graph Theory Arjun 506 views
3 votes
2 answers
2
GATE CSE 2021 Set 1 | Question: 36
Let $G=(V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as: $\text{diam}(G)=\displaystyle \max_{u,v\in V} \{\text{the length of shortest path between $u$ and $v$}\}$ Let $M$ be the adjacency matrix of $G$. Define graph $G_2$ ... $\text{diam}(G_2) = \text{diam}(G)$ $\text{diam}(G)< \text{diam}(G_2)\leq 2\; \text{diam}(G)$
Let $G=(V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as: $\text{diam}(G)=\displaystyle \max_{u,v\in V} \{\text{the length of shortest path between $u$ and $v$}\}$ Let $M$ be the adjacency matrix of $G$. Define graph $G_2$ on the same set of ... $\text{diam}(G_2) = \text{diam}(G)$ $\text{diam}(G)< \text{diam}(G_2)\leq 2\; \text{diam}(G)$
asked Feb 18 in Graph Theory Arjun 584 views
0 votes
1 answer
3
NIELIT Scientific Assistant A 2020 November: 96
In an undirected graph, if we add the degrees of all vertices, it is: odd even cannot be determined always $n+1,$ where $n$ is number of nodes
In an undirected graph, if we add the degrees of all vertices, it is: odd even cannot be determined always $n+1,$ where $n$ is number of nodes
asked Dec 9, 2020 in Unknown Category gatecse 32 views
0 votes
1 answer
4
UGCNET-Oct2020-II: 26
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ if and only if either $j=i+1$ or $j=3i$. The minimum number of edges in a path in $G$ from vertex $1$ to vertex $100$ is ______ $23$ $99$ $4$ $7$
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ if and only if either $j=i+1$ or $j=3i$. The minimum number of edges in a path in $G$ from vertex $1$ to vertex $100$ is ______ $23$ $99$ $4$ $7$
asked Nov 20, 2020 in Discrete Mathematics jothee 175 views
0 votes
1 answer
5
UGCNET-Oct2020-II: 53
Consider the following statements: Any tree is $2$-colorable A graph $G$ has no cycles of even length if it is bipartite A graph $G$ is $2$-colorable if is bipartite A graph $G$ can be colored with $d+1$ colors if $d$ is the maximum degree of any vertex in the graph ... $(b)$ and $(c)$ are incorrect $(b)$ and $(e)$ are incorrect $(a)$ and $(d)$ are incorrect
Consider the following statements: Any tree is $2$-colorable A graph $G$ has no cycles of even length if it is bipartite A graph $G$ is $2$-colorable if is bipartite A graph $G$ can be colored with $d+1$ colors if $d$ is the maximum degree of any vertex in the graph $G$ ... and $(e)$ are incorrect $(b)$ and $(c)$ are incorrect $(b)$ and $(e)$ are incorrect $(a)$ and $(d)$ are incorrect
asked Nov 20, 2020 in Discrete Mathematics jothee 221 views
0 votes
0 answers
6
UGCNET-Oct2020-II: 86
Let $G$ be a simple undirected graph, $T_D$ be a DFS tree on $G$, and $T_B$ be the BFS tree on $G$. Consider the following statements. Statement $I$: No edge of $G$ is a cross with respect to $T_D$ Statement $II$ ... $I$ and Statement $II$ are false Statement $I$ is correct but Statement $II$ is false Statement $I$ is incorrect but Statement $II$ is true
Let $G$ be a simple undirected graph, $T_D$ be a DFS tree on $G$, and $T_B$ be the BFS tree on $G$. Consider the following statements. Statement $I$: No edge of $G$ is a cross with respect to $T_D$ Statement $II$: For every edge $(u,v)$ of $G$ ... Statement $I$ and Statement $II$ are false Statement $I$ is correct but Statement $II$ is false Statement $I$ is incorrect but Statement $II$ is true
asked Nov 20, 2020 in Discrete Mathematics jothee 92 views
3 votes
3 answers
9
NIELIT 2017 DEC Scientific Assistant A - Section B: 20
Total number of simple graphs that can be drawn using six vertices are: $2^{15}$ $2^{14}$ $2^{13}$ $2^{12}$
Total number of simple graphs that can be drawn using six vertices are: $2^{15}$ $2^{14}$ $2^{13}$ $2^{12}$
asked Mar 31, 2020 in Graph Theory Lakshman Patel RJIT 650 views
1 vote
1 answer
10
NIELIT 2017 DEC Scientific Assistant A - Section B: 38
If a planner graph, having $25$ vertices divides the plane into $17$ different regions. Then how many edges are used to connect the vertices in this graph. $20$ $30$ $40$ $50$
If a planner graph, having $25$ vertices divides the plane into $17$ different regions. Then how many edges are used to connect the vertices in this graph. $20$ $30$ $40$ $50$
asked Mar 31, 2020 in Graph Theory Lakshman Patel RJIT 371 views
0 votes
2 answers
11
NIELIT 2016 MAR Scientist B - Section B: 1
The number of ways to cut a six sided convex polygon whose vertices are labeled into four triangles using diagonal lines that do not cross is $13$ $14$ $12$ $11$
The number of ways to cut a six sided convex polygon whose vertices are labeled into four triangles using diagonal lines that do not cross is $13$ $14$ $12$ $11$
asked Mar 31, 2020 in Graph Theory Lakshman Patel RJIT 544 views
1 vote
1 answer
13
NIELIT 2016 DEC Scientist B (CS) - Section B: 5
Let $G$ be a simple undirected planar graph on $10$ vertices with $15$ edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the plane is equal to: $3$ $4$ $5$ $6$
Let $G$ be a simple undirected planar graph on $10$ vertices with $15$ edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the plane is equal to: $3$ $4$ $5$ $6$
asked Mar 31, 2020 in Graph Theory Lakshman Patel RJIT 281 views
0 votes
1 answer
14
NIELIT 2017 July Scientist B (IT) - Section B: 1
Given an undirected graph $G$ with $V$ vertices and $E$ edges, the sum of the degrees of all vertices is $E$ $2E$ $V$ $2V$
Given an undirected graph $G$ with $V$ vertices and $E$ edges, the sum of the degrees of all vertices is $E$ $2E$ $V$ $2V$
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 3.1k views
0 votes
2 answers
15
NIELIT 2017 July Scientist B (IT) - Section B: 2
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph? In adjacency list representation, space is saved for sparse graphs. Deleting a vertex in adjacency list ... Adding a vertex in adjacency list representation is easier than adjacency matrix representation. All of the option.
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph? In adjacency list representation, space is saved for sparse graphs. Deleting a vertex in adjacency list representation is easier than ... matrix representation. Adding a vertex in adjacency list representation is easier than adjacency matrix representation. All of the option.
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 3.1k views
0 votes
1 answer
16
NIELIT 2017 July Scientist B (IT) - Section B: 3
A path in graph $G$, which contains every vertex of $G$ and only once? Euler circuit Hamiltonian path Euler Path Hamiltonian Circuit
A path in graph $G$, which contains every vertex of $G$ and only once? Euler circuit Hamiltonian path Euler Path Hamiltonian Circuit
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 482 views
0 votes
1 answer
17
NIELIT 2017 July Scientist B (IT) - Section B: 5
In a given following graph among the following sequences: abeghf abfehg abfhge afghbe Which are depth first traversals of the above graph? I,II and IV only I and IV only II,III and IV only I,III and IV only
In a given following graph among the following sequences: abeghf abfehg abfhge afghbe Which are depth first traversals of the above graph? I,II and IV only I and IV only II,III and IV only I,III and IV only
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 246 views
0 votes
1 answer
18
NIELIT 2017 July Scientist B (IT) - Section B: 6
Considering the following graph, which one of the following set of edged represents all the bridges of the given graph? $(a,b), (e,f)$ $(a,b), (a,c)$ $(c,d), (d,h)$ $(a,b)$
Considering the following graph, which one of the following set of edged represents all the bridges of the given graph? $(a,b), (e,f)$ $(a,b), (a,c)$ $(c,d), (d,h)$ $(a,b)$
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 183 views
0 votes
1 answer
19
NIELIT 2017 July Scientist B (IT) - Section B: 7
Which of the following statements is/are TRUE? $S1$:The existence of an Euler circuit implies that an Euler path exists. $S2$:The existence of an Euler path implies that an Euler circuit exists. $S1$ is true. $S2$ is true. $S1$ and $S2$ both are true. $S1$ and $S2$ both are false.
Which of the following statements is/are TRUE? $S1$:The existence of an Euler circuit implies that an Euler path exists. $S2$:The existence of an Euler path implies that an Euler circuit exists. $S1$ is true. $S2$ is true. $S1$ and $S2$ both are true. $S1$ and $S2$ both are false.
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 324 views
0 votes
1 answer
20
NIELIT 2017 July Scientist B (IT) - Section B: 8
A connected planar graph divides the plane into a number of regions. If the graph has eight vertices and these are linked by $13$ edges, then the number of regions is: $5$ $6$ $7$ $8$
A connected planar graph divides the plane into a number of regions. If the graph has eight vertices and these are linked by $13$ edges, then the number of regions is: $5$ $6$ $7$ $8$
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 721 views
0 votes
1 answer
21
NIELIT 2017 July Scientist B (IT) - Section B: 12
Let $G$ be a simple connected planar graph with $13$ vertices and $19$ edges. Then, the number of faces in the planar embedding of the graph is $6$ $8$ $9$ $13$
Let $G$ be a simple connected planar graph with $13$ vertices and $19$ edges. Then, the number of faces in the planar embedding of the graph is $6$ $8$ $9$ $13$
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 147 views
0 votes
1 answer
22
NIELIT 2017 July Scientist B (IT) - Section B: 15
The number of diagonals that can be drawn by joining the vertices of an octagon is $28$ $48$ $20$ None of the option
The number of diagonals that can be drawn by joining the vertices of an octagon is $28$ $48$ $20$ None of the option
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 153 views
0 votes
1 answer
23
NIELIT 2017 July Scientist B (CS) - Section B: 2
Which of the following statements is/are TRUE for an undirected graph? Number of odd degree vertices is even Sum of degrees of all vertices is even P only Q only Both P and Q Neither P nor Q
Which of the following statements is/are TRUE for an undirected graph? Number of odd degree vertices is even Sum of degrees of all vertices is even P only Q only Both P and Q Neither P nor Q
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 508 views
0 votes
4 answers
24
NIELIT 2017 July Scientist B (CS) - Section B: 11
Consider the following graph $L$ and find the bridges,if any. No bridge $\{d,e\}$ $\{c,d\}$ $\{c,d\}$ and $\{c,f\}$
Consider the following graph $L$ and find the bridges,if any. No bridge $\{d,e\}$ $\{c,d\}$ $\{c,d\}$ and $\{c,f\}$
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 424 views
0 votes
3 answers
25
NIELIT 2017 July Scientist B (CS) - Section B: 12
The following graph has no Euler circuit because It has $7$ vertices. It is even-valent (all vertices have even valence). It is not connected. It does not have a Euler circuit.
The following graph has no Euler circuit because It has $7$ vertices. It is even-valent (all vertices have even valence). It is not connected. It does not have a Euler circuit.
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 716 views
0 votes
7 answers
26
NIELIT 2017 July Scientist B (CS) - Section B: 13
For the graph shown, which of the following paths is a Hamilton circuit? $ABCDCFDEFAEA$ $AEDCBAF$ $AEFDCBA$ $AFCDEBA$
For the graph shown, which of the following paths is a Hamilton circuit? $ABCDCFDEFAEA$ $AEDCBAF$ $AEFDCBA$ $AFCDEBA$
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 743 views
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...