Recent questions tagged graph-theory

+1 vote

1 answer

1

Which of the following condition is sufficient to detect cycle in a directed graph?

asked 2 days ago in Algorithms by Gangani_Son (145 points) | 30 views

0 votes

0 answers

2

#geeksfoegeeks #gate #2017 #mocktest
Let G be a simple graph with 20 vertices and 8 components. If we delete a vertex in G, then number of components in G should lie between ____. (A) 8 and 20 (B) 8 and 19 (C) 7 and 19 (D) 7 and 20 Answer is (C) but i think also possible (B). anyone explain?

asked Dec 4 in Programming by Gangani_Son (145 points) | 37 views

0 votes

1 answer

3

Self Doubt
If a graph with n vertices has more than $\left ( n-1 \right )\left ( n-2 \right ) / 2$ edges then it is connected. I am a bit confused about this question, since I can always prove that for a graph to connected you need more than $\geq n-1$ edges.

asked Dec 3 in DS by jatin khachane 1 Active (3.2k points) | 54 views

0 votes

1 answer

4

Planar Graph
Let G be a simple connected planar graph with 14 vertices and 20 edges. Number of closed regions in planar embedding of the graph is ?

asked Dec 2 in Graph Theory by Na462 Loyal (7.4k points) | 50 views

0 votes

1 answer

5

Undirected Graph - Hamiltonian Cycle - NP Complete?

asked Nov 30 in Algorithms by gmrishikumar (461 points) | 28 views

0 votes

0 answers

6

MIT fall 2011 algorithms
Given a directed graph G, consider forming a graph G0 as follows. Each vertex u0 ∈ G0 represents a strongly connected component (SCC) of G. There is an edge (u0 , v0 ) in G0 if there is an edge in G from the SCC corresponding to u0 to the SCC corresponding ... (u0 , v0 ) in G0 if there is an edge in G from the SCC corresponding to u0 to the SCC corresponding to v0 "

asked Nov 19 in Graph Theory by Sandy Sharma Active (1.1k points) | 46 views

0 votes

1 answer

7

Graph
If a graph requires k different colors for its proper coloring, then chromatic number of the graph is (a) 1 (b) k (c) k-1 (d) k/2

asked Nov 17 in Others by Sriya sarkar (7 points) | 23 views

0 votes

0 answers

8

Graph Theory(Eular walk)
$A)$ If a graph has closed Eularian walk, then it has an even number of edges $B)$ If $G$ be a simple graph on $9$ vertices and the sum of all degrees in $G$ is atleast $27$, then $G$ has a vertex of degree atleast $4$. Which Statement should be true? Is it possible B) to be true? And for A) I think "only if" is needed in place of "if" to be true

asked Nov 16 in Graph Theory by srestha Veteran (103k points) | 69 views

0 votes

0 answers

9

Connected Components

asked Nov 14 in Graph Theory by Na462 Loyal (7.4k points) | 92 views

0 votes

0 answers

10

Regular graph coloring
If G is a connected k-regular graph with chromatic number k+1, then find the number of edges in G?

asked Nov 6 in Graph Theory by dan31 (287 points) | 106 views

0 votes

1 answer

11

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?

asked Nov 6 in Graph Theory by dan31 (287 points) | 77 views

0 votes

0 answers

12

Regular Graph
If a 2-regular graph G has a perfect matching then which of the following is/are true? S1: G is a cycle of even length S2: Chromatic number of G is 2 S3: G is connected S4: Every component of G is an even cycle Options- A) S1,S2 B)S2,S4 C)S3,S4 D)S1,S4

asked Nov 6 in Graph Theory by dan31 (287 points) | 55 views

0 votes

0 answers

13

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?

asked Nov 6 in Graph Theory by dan31 (287 points) | 148 views

0 votes

1 answer

14

algo graph questions
AB min value 10 is answer wrong here??

asked Nov 6 in Algorithms by I_am_winner Junior (657 points) | 106 views

0 votes

1 answer

15

Test Series

asked Oct 29 in Graph Theory by Gupta731 Active (2.9k points) | 92 views

0 votes

0 answers

16

Gateforum Test Series

asked Oct 29 in Graph Theory by Gupta731 Active (2.9k points) | 49 views

0 votes

0 answers

17

Planar Graph
Can minimum degree of a planar graph be $5$? Give some example

asked Oct 23 in Graph Theory by srestha Veteran (103k points) | 79 views

0 votes

1 answer

18

Strongly connected component
How to find Strongly connected components and weakly connected components in the given graph?

asked Oct 21 in Graph Theory by Lakshman Patel RJIT Boss (20k points) | 80 views

0 votes

0 answers

19

Eulerian circuit
How many Eulerian graphs are possible?

asked Oct 21 in Graph Theory by Lakshman Patel RJIT Boss (20k points) | 75 views

0 votes

1 answer

20

Graph theory
How many numbers of Articulation Points (or Cut Vertices) in a Graph are possible?

asked Oct 21 in Graph Theory by Lakshman Patel RJIT Boss (20k points) | 41 views

0 votes

0 answers

21

GATEBOOK-2019-DS2-1
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? $7, 5, 5, 3, 3, 2, 2, 2$ $6, 6, 6, 6, 3, 3, 2, 2, 1, 1$ $8, 7, 6, 4, 4, 3, 2, 2, 2$ $8, 7, 6, 6, 4, 4, 2, 2, 2$ II and III III and IV IV only I and IV

asked Oct 16 in Programming by GATEBOOK Loyal (6k points) | 66 views

0 votes

2 answers

22

GATEBOOK-2019-DS2-3
A quinpartite graph is a graph whose vertices can be partitioned into five groups such that no two vertices in same group are connected via some edge. The maximum number of edges in a quinpartite graph with $10$ vertices, where cardinalities of those five sets are given as $\{2,3,2,1,2\},$ is: $16$ $20$ $26$ $39$

asked Oct 16 in Programming by GATEBOOK Loyal (6k points) | 109 views

0 votes

0 answers

23

virtual gate graph theory
i am getting 6 as answer

asked Oct 15 in Graph Theory by Prince Sindhiya Active (5.2k points) | 74 views

0 votes

1 answer

24

Complete Matching
Consider the Bipartite graph shown. If four edges are chosen at random, what is the probability that they form a complete matching from V1 to V2 ? A. 0.039 B. 0.052 C. 0.071 D. 0.083

asked Oct 13 in Mathematical Logic by Na462 Loyal (7.4k points) | 65 views

+2 votes

2 answers

25

Degree of vertices
Consider an undirected graph with $n$ vertices, vertex $1$ has degree $1$,while each vertex $2,3,.............,n-1$ has degree $4$.The degree of vertex $n$ is unknown. Which of the following statement must be true? $A)$ Vertex $n$ has degree $1$ ... $C)$ There is a path from vertex $1$ to vertex $n$ $D)$ Spanning tree will include edge connecting vertex $1$ and vertex $n$

asked Oct 10 in Graph Theory by Lakshman Patel RJIT Boss (20k points) | 69 views

0 votes

1 answer

26

Bipartite graph
The number of ways to properly color (using just sufficient colors) a connected graph without any cycle using five colors, such a way that no two adjacent nodes have the same color?

asked Oct 10 in Graph Theory by Lakshman Patel RJIT Boss (20k points) | 74 views

0 votes

1 answer

27

Complete Graph
Consider the following graph: Number of the Hamiltonian cycles starting and ending point at $ A$ is _______

asked Oct 10 in Graph Theory by Lakshman Patel RJIT Boss (20k points) | 89 views

0 votes

0 answers

28

Mathematics

asked Oct 4 in Set Theory & Algebra by jatinkumar (241 points) | 28 views

0 votes

0 answers

29

Made easy,graphs
let G be an undirected graph. consider a depth-first traversal of G, and let T be the resulting depth-first search tree. let you be a vertex in G and let V be the first new (unvisited) vortex visited after visiting you in the traversal. which of the following statement is always true?

asked Oct 1 in DS by KrishY (7 points) | 45 views

+1 vote

0 answers

30

UGC-NET CS 2017
An undirected graph G (V, E) contains n (n > 2) nodes named v1 , v2 ,...,vn. Two nodes vi and vj are connected if and only if 0 < │ i − j│ ≤2. Each edge (vi , vj ) is assigned a weight i+j. The cost of the minimum spanning tree of such a graph with 10 nodes is: A) 88 B)91 C)49 D)21

asked Sep 28 in Graph Theory by aditi19 Active (2.1k points) | 58 views

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

Recent questions tagged graph-theory

Recent Posts

Recent Blog Comments