Recent questions tagged graph-theory / GATE Overflow for GATE CSE

0 votes

1 answer

91

graph theory ,discrete math
how many subgraph with atleast 1 vertex does k2 have? (graph theory question)

how many subgraph with atleast 1 vertex does k2 have? (graph theory question)

shuham kumar

421 views

shuham kumar asked Nov 18, 2022

0 votes

2 answers

92

mde esy test series
Which of the following statements is/are true? A. In a labelled undirected connected simple graph G, all the depth-first search from same node form same tree. B. In a labelled undirected connected simple graph, G, all the breadth first search from same node form same ... is descendent of u in all possible depth-first search forest of G. (u.d is discover time of node u in DFS).

Which of the following statements is/are true?A. In a labelled undirected connected simple graph G, all the depth-first search from same node form same tree.B. In a label...

Himanshu555

623 views

Himanshu555 asked Nov 8, 2022

–4 votes

2 answers

93

Data Structure- Tree & Graphs
*MSQ* The following figure depicts a a. A tree and only tree b. A tree with 3 nodes c. A graph (Since every tree is a graph) d. A graph and only graph

*MSQ*The following figure depicts a a. A tree and only treeb. A tree with 3 nodesc. A graph (Since every tree is a graph)d. A graph and only graph

Souvik33

637 views

Souvik33 asked Oct 27, 2022

4 votes

2 answers

94

TIFR CSE 2022 | Part B | Question: 2
Let $G=(V, E)$ be an undirected simple graph. A subset $M \subseteq E$ is a matching in $G$ if distinct edges in $M$ do not share a vertex. A matching is maximal if no strict superset of $M$ is a matching. How many maximal matchings does the following graph have? $1$ $2$ $3$ $4$ $5$

Let $G=(V, E)$ be an undirected simple graph. A subset $M \subseteq E$ is a matching in $G$ if distinct edges in $M$ do not share a vertex. A matching is maximal if no st...

admin

964 views

admin asked Sep 1, 2022

3 votes

1 answer

95

TIFR CSE 2022 | Part B | Question: 6
We are given a graph $G$ along with a matching $M$ and a vertex cover $C$ in it such that $|M|=|C|$. Consider the following statements: $M$ is a maximum matching in $G$. $C$ is a minimum vertex cover in $G$. $G$ is a bipartite graph. Which of ... $(1)$ and $(2)$ are correct All the three statements $(1), (2),$ and $(3)$ are correct

We are given a graph $G$ along with a matching $M$ and a vertex cover $C$ in it such that $|M|=|C|$. Consider the following statements:$M$ is a maximum matching in $G$.$C...

admin

931 views

admin asked Sep 1, 2022

1 votes

0 answers

96

TIFR CSE 2022 | Part B | Question: 12
Given an undirected graph $G$, an ordering $\sigma$ of its vertices is called a perfect ordering if for every vertex $v$, the neighbours of $v$ which precede $v$ in $\sigma$ form a clique in $G$. Recall that given an undirected ... SPECIAL-COLOURING are in $\mathrm{P}$ Neither of SPECIAL-CLiQUE and SPECIAL-COLOURING is in $\mathrm{P},$ but both are decidable

Given an undirected graph $G$, an ordering $\sigma$ of its vertices is called a perfect ordering if for every vertex $v$, the neighbours of $v$ which precede $v$ in $\sig...

admin

369 views

admin asked Sep 1, 2022

1 votes

1 answer

97

TIFR CSE 2022 | Part B | Question: 14
Let $G$ be a directed graph (with no self-loops or parallel edges) with $n \geq 2$ vertices and $m$ edges. Consider the $n \times m$ incidence matrix $M$ of $G$, whose rows are indexed by the vertices of $G$ and the columns by the edges of $G$ ... . Then, what is the rank of $M?$ $m-1$ $m-n+1$ $\lceil m / 2\rceil$ $n-1$ $\lceil n / 2\rceil$

Let $G$ be a directed graph (with no self-loops or parallel edges) with $n \geq 2$ vertices and $m$ edges. Consider the $n \times m$ incidence matrix $M$ of $G$, whose ro...

admin

464 views

admin asked Sep 1, 2022

0 votes

0 answers

98

Best Open Video Playlist for Graphs Topic | Data structures
Please list out the best free available video playlist for Graphs from Data structures as an answer here (only one playlist per answer). We'll then select the best playlist and add to GO classroom video lists. You can add ... but standard ones are more likely to be selected as best. For the full list of selected videos please see here

Please list out the best free available video playlist for Graphs from Data structures as an answer here (only one playlist per answer). We'll then select the best playli...

makhdoom ghaya

274 views

makhdoom ghaya asked Aug 16, 2022

0 votes

0 answers

99

Best Open Video Playlist for Graph Theory: Coloring Topic | Discrete Mathematics
Please list out the best free available video playlist for Graph Theory: Coloring Topic from Discrete Mathematics as an answer here (only one playlist per answer). We'll then select the best playlist and add to GO ... ones are more likely to be selected as best. For the full list of selected videos please see here

Please list out the best free available video playlist for Graph Theory: Coloring Topic from Discrete Mathematics as an answer here (only one playlist per answer). We'll ...

makhdoom ghaya

203 views

makhdoom ghaya asked Aug 14, 2022

0 votes

0 answers

100

Best Open Video Playlist for Graph Theory: Matching Topic | Discrete Mathematics
Please list out the best free available video playlist for Graph Theory: Matching Topic from Discrete Mathematics as an answer here (only one playlist per answer). We'll then select the best playlist and add to GO ... ones are more likely to be selected as best. For the full list of selected videos please see here

Please list out the best free available video playlist for Graph Theory: Matching Topic from Discrete Mathematics as an answer here (only one playlist per answer). We'll ...

makhdoom ghaya

194 views

makhdoom ghaya asked Aug 14, 2022

0 votes

0 answers

101

Best Open Video Playlist for Graph Theory: Connectivity Topic | Discrete Mathematics
Please list out the best free available video playlist for Graph Theory: Connectivity Topic from Discrete Mathematics as an answer here (only one playlist per answer). We'll then select the best playlist and add ... are more likely to be selected as best. For the full list of selected videos please see here

Please list out the best free available video playlist for Graph Theory: Connectivity Topic from Discrete Mathematics as an answer here (only one playlist per answer). We...

makhdoom ghaya

217 views

makhdoom ghaya asked Aug 14, 2022

4 votes

1 answer

102

GO Classes Scholarship 2023 | Test | Question: 8
In a directed graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$, two nodes $u$ and $v$ are strongly connected if and only if they are mutually reachable i.e. there is a path from u to $v$ and a path from $v$ to $u$. ... connected components $\dots?$ can not increase can not decrease by more than $1$ can not decrease by more than $2$ may remain unchanged

In a directed graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$, two nodes $u$ and $v$ are strongly connected if and only if they are mutually reachable i.e. there is a path fr...

GO Classes

1.0k views

GO Classes asked Aug 6, 2022

5 votes

2 answers

103

GO Classes Scholarship 2023 | Test | Question: 9
Consider the following graph $\text{G:}$ Let $\text{M, C, I, S, B, E}$ be the Matching number, chromatic number, independence number, Clique number, Vertex cover number, and edge cover number, respectively of $\text{G}.$ What is $\text{M+C+I+S+B+E}?$

Consider the following graph $\text{G:}$Let $\text{M, C, I, S, B, E}$ be the Matching number, chromatic number, independence number, Clique number, Vertex cover number, a...

GO Classes

718 views

GO Classes asked Aug 6, 2022

3 votes

1 answer

104

GO Classes Scholarship 2023 | Test | Question: 10
For which of the following does there exist a graph satisfying the specified conditions? A tree with six vertices and six edges. A tree with three or more vertices, two vertices of degree one, and all the other vertices with degree three or ... with $10$ vertices and $8$ edges. A disconnected graph with $12$ vertices and $11$ edges and no cycle.

For which of the following does there exist a graph satisfying the specified conditions?A tree with six vertices and six edges.A tree with three or more vertices, two ver...

GO Classes

521 views

GO Classes asked Aug 6, 2022

4 votes

1 answer

105

GO Classes Scholarship 2023 | Test | Question: 12
How many non-isomorphic simple undirected graphs are there, each with four vertices and without a cycle?

How many non-isomorphic simple undirected graphs are there, each with four vertices and without a cycle?

GO Classes

749 views

GO Classes asked Aug 6, 2022

0 votes

1 answer

106

Self Doubt - Planarity of Complete Bipartite Graph
How to determine for which m, n the complete bipartite graph $Km,n$ is planar? I am getting two answers from two sources:- A complete bipartite graph $Kmn$ is planar if and only if m<3 or n>3. Source: https://www.javatpoint.com/ ... m ≤ 2 or n ≤ 2. Source: http://www.matthewkahle.org/download/file/fid/573 Need a proper proof of the solution.

How to determine for which m, n the complete bipartite graph $Km,n$ is planar?I am getting two answers from two sources:-A complete bipartite graph $Kmn$ is planar if and...

Abhrajyoti00

1.1k views

Abhrajyoti00 asked Jul 21, 2022

0 votes

2 answers

107

MadeEasy Test Series
There are 15 vertices and 15 edges in some graph. Now, these edges are arranged in such a way that maximum number of connected components are created in the graph. Find the connected components created. (A) 8 (B) 9 (C) 10 (D) 11 Please explain your answer.

There are 15 vertices and 15 edges in some graph. Now, these edges are arranged in such a way that maximum number of connected components are created in the graph. Find t...

anupamsworld

908 views

anupamsworld asked Jul 8, 2022

0 votes

0 answers

108

Introduction to Graph Theory Exercises
This is the problem snapshot

This is the problem snapshot

AngshukN

405 views

AngshukN asked May 22, 2022

5 votes

1 answer

109

GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 2
Let $\text{G}$ be the following set of undirected connected graphs $:$ $\text{G} = \{ g \mid g \;\text{is a complete graph on}\; n\; \text{vertices where}\; 1\leq n \leq 10 \;\text{OR} \;g$ is a cycle graph on ... $a$ is isomorphic to $b.$ How many equivalence classes will be there for $\text{R}?$

Let $\text{G}$ be the following set of undirected connected graphs $:$$\text{G} = \{ g \mid g \;\text{is a complete graph on}\; n\; \text{vertices where}\; 1\leq n \leq 1...

GO Classes

472 views

GO Classes asked May 11, 2022

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