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

2 votes

3 answers

91

Zeal Test Series 2019: Graph Theory - Graph Connectivity

Prince Sindhiya

923 views

Prince Sindhiya asked Dec 21, 2018

6 votes

1 answer

92

TIFR CSE 2019 | Part B | Question: 12
Let $G=(V,E)$ be a directed graph with $n(\geq 2)$ vertices, including a special vertex $r$. Each edge $e \in E$ has a strictly positive edge weight $w(e)$. An arborescence in $G$ rooted at $r$ is a subgraph $H$ of $G$ ... is acyclic $w^*$ is less than the weight of the minimum weight directed Hamiltonian cycle in $G$, when $G$ has a directed Hamiltonian cycle

Let $G=(V,E)$ be a directed graph with $n(\geq 2)$ vertices, including a special vertex $r$. Each edge $e \in E$ has a strictly positive edge weight $w(e)$. An arborescen...

Arjun

2.4k views

Arjun asked Dec 18, 2018

7 votes

2 answers

93

TIFR CSE 2019 | Part B | Question: 15
Consider directed graphs on $n$ labelled vertices $\{1,2, \dots ,n\}$, where each vertex has exactly one edge coming in and exactly one edge going out. We allow self-loops. How many graphs have exactly two cycles ? $\displaystyle \sum_{k=1}^{n-1} k!(n-k)!$ ... $n!\bigg[\displaystyle \sum_{k=1}^{n-1} \frac{1}{k}\bigg]$ $\frac{n!(n-1)}{2}$ None of the above

Consider directed graphs on $n$ labelled vertices $\{1,2, \dots ,n\}$, where each vertex has exactly one edge coming in and exactly one edge going out. We allow self-loo...

Arjun

2.2k views

Arjun asked Dec 18, 2018

1 votes

1 answer

94

EET IITD

Churchill Khangar

618 views

Churchill Khangar asked Nov 23, 2018

3 votes

0 answers

95

Zeal Test Series 2019: Graph Theory - Graph Connectivity
i didn't read the concept related to strongly connected components please it describe it for this question

i didn't read the concept related to strongly connected components please it describe it for this question

Prince Sindhiya

849 views

Prince Sindhiya asked Nov 11, 2018

2 votes

2 answers

96

Graph Connectivity
Consider the given statements S1: In a simple graph G with 6 vertices, if degree of each vertex is 2, then Euler circuit exists in G. S2:In a simple graph G, if degree of each vertex is 3 then the graph G is connected. Which of the following is/are true?

Consider the given statementsS1: In a simple graph G with 6 vertices, if degree of each vertex is 2, then Euler circuit exists in G.S2:In a simple graph G, if degree of e...

dan31

2.4k views

dan31 asked Nov 6, 2018

1 votes

0 answers

97

Graph connectivity
Let G be a connected graph with 7 connected components and each component is a tree. If G has 26 edge then number of vertices in G is?

Let G be a connected graph with 7 connected components and each component is a tree. If G has 26 edge then number of vertices in G is?

dan31

1.4k views

dan31 asked Nov 6, 2018

0 votes

1 answer

98

Gateforum Test Series: Graph Theory - Graph connectivity

Gupta731

805 views

Gupta731 asked Oct 29, 2018

5 votes

2 answers

99

Graph theory
Stmt 1: A simple graph is necessarily connected if |E| > (n-1)*(n-2)/2. Stmt2: A simple graph with n vertices and k components has at least n-k edges. Can you please explain how are these results derived?

Stmt 1: A simple graph is necessarily connected if |E| (n-1)*(n-2)/2.Stmt2: A simple graph with n vertices and k components has at least n-k edges.Can you please explain...

Nidhi Budhraja

2.4k views

Nidhi Budhraja asked Aug 26, 2018

1 votes

1 answer

100

Kenneth Rosen Edition 6th Exercise 8.4 Question 6 (Page No. 574)
how many connected components does the following graph has ?find its connected component ?

how many connected components does the following graph has ?find its connected component ?

saurab

975 views

saurab asked Aug 4, 2018

1 votes

1 answer

101

Zeal Workbook: Graph Theory - Graph Connectivity
Prove that every graph with n vertices and k components has atleast n-k edges.

Prove that every graph with n vertices and k components has atleast n-k edges.

Prince Sindhiya

417 views

Prince Sindhiya asked Jul 29, 2018

0 votes

1 answer

102

ACE Bits and bYtes
Minimum no of edges necessary in a simple graph with 10 vertices to ensure connectivity is_______.

Minimum no of edges necessary in a simple graph with 10 vertices to ensure connectivity is_______.

abhishek1995_cse

1.3k views

abhishek1995_cse asked Jul 23, 2018

0 votes

2 answers

103

Connected Components
My Doubt is :- 1. If n vertices are there and p are the connected components then total n-p edges will be there. 2. In a simple graph with n vertices and p connected components there are atmost (n-p)(n-p+1)/2 number of edges Now which to ... the answer. Solution of made easy:- (Please tell how did they approached the question and which way is the best way to do such questions)

My Doubt is :- 1. If n vertices are there and p are the connected components then total n-p edges will be there.2. In a simple graph with n vertices and p connected compo...

Na462

7.0k views

Na462 asked May 2, 2018

0 votes

1 answer

104

SELF_DOUBT(MST)
What important point we keep in mind while finding the #(number) of spanning tree ?? from the given graph

What important point we keep in mind while finding the #(number) of spanning tree ?? from the given graph

air1ankit

491 views

air1ankit asked Apr 29, 2018

7 votes

3 answers

105

ISRO2018-38
The number of edges in a regular graph of degree: $d$ and $n$ vertices is: maximum of $n$ and $d$ $n +d$ $nd$ $nd/2$

The number of edges in a regular graph of degree: $d$ and $n$ vertices is:maximum of $n$ and $d$ $n +d$$nd$$nd/2$

Arjun

14.0k views

Arjun asked Apr 22, 2018

1 votes

1 answer

106

Graph Book
The maximum number of edges in a n-node undirected graph WITH self-loops is?

The maximum number of edges in a n-node undirected graph WITH self-loops is?

targate2018

1.2k views

targate2018 asked Apr 7, 2018

1 votes

1 answer

107

Graph Theory
Consider the following undirected graph with some edge costs missing. Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequalities NEED NOT hold? $cost(a,b)\geq 6$. $cost(b,e)\geq 5$. $cost(e,f)\geq 5$. $cost(a,d)\geq 4$. $cost(b,c)\geq 4$. Please someone solve and explain :)

Consider the following undirected graph with some edge costs missing.Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequa...

gauravkc

634 views

gauravkc asked Apr 6, 2018

1 votes

2 answers

108

Graph Theory
Can someone solve this? Also please attempt this question on Algorithms time complexity if interested :) https://gateoverflow.in/210836/algorithms-time-complexity

Can someone solve this?Also please attempt this question on Algorithms time complexity if interested :)https://gateoverflow.in/210836/algorithms-time-complexity

gauravkc

1.2k views

gauravkc asked Apr 5, 2018

0 votes

1 answer

109

Kenneth Rosen Edition 6th Exercise 8.4 Question 70 (Page No. 565 )
How much storage is needed to represent a simple graph with n vertices and m edges using. a) adjacency lists? b) an adjacency matrix? c) an incidence matrix?

How much storage is needed to represent a simple graph with n vertices and m edges using.a) adjacency lists?b) an adjacency matrix?c) an incidence matrix?

Mk Utkarsh

2.5k views

Mk Utkarsh asked Mar 1, 2018

1 votes

3 answers

110

CMI2017-B-5
An undirected graph is $\text{connected}$ if, for any two vertices $\{u, v\}$ of the graph, there is a path in the graph starting at $u$ and ending at $v$. A tree is a connected, undirected graph that contains no cycle. A $\text{leaf}$ in a tree is a vertex that ... $ \in V_2$ or vice versa. Prove that if $G$ is a tree with at least two vertices, then $G$ is bipartite.

An undirected graph is $\text{connected}$ if, for any two vertices $\{u, v\}$ of the graph, there is a path in the graph starting at $u$ and ending at $v$. A tree is a co...

Tesla!

1.3k views

Tesla! asked Feb 5, 2018

2 votes

2 answers

111

CMI2017-A-05
Let $G$ be an arbitrary graph on $n$ vertices with $4n − 16$ edges. Consider the following statements: There is a vertex of degree smaller than $8$ in $G$. There is a vertex such that there are less than $16$ vertices at a distance exactly $2$ from it. Which of the following is true: I Only II Only Both I and II Neither I nor II

Let $G$ be an arbitrary graph on $n$ vertices with $4n − 16$ edges. Consider the following statements:There is a vertex of degree smaller than $8$ in $G$.There is a ver...

Tesla!

1.2k views

Tesla! asked Feb 4, 2018

0 votes

2 answers

112

CMI2017-A-04
City authorities are concerned about traffic accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of any accident along these roads. To minimize response time, ambulances are to be located at ... number of edges. Find a spanning tree with minimum cost. Find a minimal coloring. Find a minimum size vertex cover.

City authorities are concerned about traffic accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of an...

Tesla!

1.0k views

Tesla! asked Feb 4, 2018

4 votes

1 answer

113

DFS- depth first search

budhu

736 views

budhu asked Jan 25, 2018

2 votes

0 answers

114

graph
Is there any algorithm to find number of different minimum spanning trees for a graph?

Is there any algorithm to find number of different minimum spanning trees for a graph?

raviyogi

437 views

raviyogi asked Jan 18, 2018

9 votes

1 answer

115

Graph Colouring
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is

Mk Utkarsh

1.1k views

Mk Utkarsh asked Jan 10, 2018

2 votes

1 answer

116

Ace Test series: Graph Theory - Graph Connectivity
Please can anyone tell whether my answer is wrong or solution provided by them is correct??

Please can anyone tell whether my answer is wrong or solution provided by them is correct??

Asim Abbas

503 views

Asim Abbas asked Jan 8, 2018

3 votes

0 answers

117

Hamiltonian cycle
How many number of Hamiltonian cycles possible for a complete graph in all the case (i.e. ordered, unordered, edge-disjoint ...)??

How many number of Hamiltonian cycles possible for a complete graph in all the case (i.e. ordered, unordered, edge-disjoint ...)??

thepeeyoosh

454 views

thepeeyoosh asked Dec 29, 2017

0 votes

0 answers

118

Graph Theory Doubt
Let G be a planar graph with 7 vertices, 10 edges and 3 components then the number of regions are : a)24 b)37 c)7 d)10 Answer given : 7 How to solve this ? Is there any formulae for number of regions calculation? The only one I know is r=e-n+2 for any planar graph.

Let G be a planar graph with 7 vertices, 10 edges and 3 components then the number of regions are :a)24b)37c)7d)10Answer given : 7How to solve this ? Is there any formula...

Sourajit25

597 views

Sourajit25 asked Dec 25, 2017

2 votes

2 answers

119

graph theory
Maximum no of edges in a triangle-free, simple planar graph with 10 vertices

Maximum no of edges in a triangle-free, simple planar graph with 10 vertices

Parshu gate

822 views

Parshu gate asked Dec 23, 2017

2 votes

0 answers

120

Maths: Graph Theory
Let G be a 3-regular graph and S be a minimum vertex cut of G with |S| = 5 The the size of smallest edge cut of G is _______ (A)4 (B) 5 (C) 6 (D) None of the above

Let G be a 3-regular graph and S be a minimum vertex cut of G with |S| = 5The the size of smallest edge cut of G is _______(A)4(B) 5(C) 6(D) None of the above

Manu Thakur

1.2k views

Manu Thakur asked Dec 3, 2017

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