Recent questions tagged graph-theory

0 votes

1 answer

1

Made Easy algorithms
How many edge disjoint spanning trees are possible for a undirected complete connected graph of n vertices?

asked 5 days ago in Algorithms by Sambhrant Maurya Junior (609 points) | 26 views

0 votes

2 answers

2

Graph theory Modified
What is the maximum integer value m such that every simple connected graph with r vertices and r+2 edges contains at least m different spanning trees ? 1)1 2)4 3)8 4)m

asked 5 days ago in Graph Theory by srestha Veteran (92k points) | 125 views

0 votes

1 answer

3

Test Datasructures
Statement I : If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 Backedge Statement II : A graph G has a cycle if DFS finds at least 1 Backedge Which of the following option is correct ? ... option is correct(Statement 1 is false and Statement 2 is true but answer given is 1, please tell me where i am making mistake.

asked Aug 11 in Algorithms by Prince Sindhiya Active (1.9k points) | 12 views

0 votes

0 answers

4

Show that T is a maximum spanning tree for G

asked Jul 24 in Graph Theory by abram19000 (7 points) | 25 views

0 votes

1 answer

5

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

asked Jul 24 in Graph Theory by abhishek1995_cse (27 points) | 64 views

+1 vote

1 answer

6

ACE Bits And Bytes
Number of perfect matching in Wn (n>=4 and n is even) _________.

asked Jul 24 in Graph Theory by abhishek1995_cse (27 points) | 26 views

0 votes

1 answer

7

me test
A simple graph with n vertices is constructed by randomly and independently placing an edge between every two vertices with probability p. What is the expected no. of nodes with degree 2?

asked Jul 17 in Graph Theory by ronin_codex (7 points) | 31 views

0 votes

0 answers

8

graph theory
10.A graph G has any two vertices connected by exactly one path. Find the Number of ways we can properly colour G it we are provided with 10 colours.

asked Jul 14 in Graph Theory by poojasharma123 (81 points) | 75 views

0 votes

0 answers

9

Gate 2018 Qn. 43
Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2,…,100. There is an edge between vertices and if and only if the label of can be obtained by swapping two adjacent numbers in the label of . Let denote the degree of a vertex in G, and denote the number of connected components in G. Then, y + 10z = _____.

asked Jul 6 in Graph Theory by Optimus Prime (425 points) | 35 views

+1 vote

0 answers

10

Cormen 3rd edition chapter 22 question: 22.4.4

asked Jul 4 in Algorithms by Abhilash Mishra (85 points) | 73 views

0 votes

2 answers

11

self doubt
Is it necessary that euler graph should always be simple graph?

asked Jun 27 in Graph Theory by Vegeta (187 points) | 48 views

0 votes

0 answers

12

Kenneth rosen
How many non-isomorphic directed graphs are there with $n$ vertices when $n$ is $2$ $3$ $4$

asked Jun 18 in Graph Theory by swati96 (37 points) | 29 views

0 votes

0 answers

13

Kenneth rosen
How many non-isomorphic graphs are there with six vertices and four edges?

asked Jun 18 in Graph Theory by swati96 (37 points) | 12 views

0 votes

0 answers

14

Graphs, kenneth rosen
How many non-isomorphic simple graphs are there with five vertices and three edges?

asked Jun 18 in Graph Theory by swati96 (37 points) | 16 views

0 votes

0 answers

15

Graphs, kenneth rosen
How many non-isomorphic simple graphs are there with five vertices and three edges?

asked Jun 18 in Graph Theory by swati96 (37 points) | 12 views

0 votes

1 answer

16

spanning tree
How we get maximum no. of spanning tree for give $n$ node is $n^{(n-2)}$

asked Jun 18 in Graph Theory by piya (191 points) | 26 views

0 votes

1 answer

17

True/False
Which of the following statements related to graphs are True? Consider a graph with Positive distinct edges 1.If we add a Positive Integer to all edges, then there are chances to get more than one shortest paths between 2 vertices 2.If we add a Positive Integer ... 4.If we add a Negative Integer to all edges, then there are chances to get more than one longest paths between 2 vertices

asked Jun 9 in Graph Theory by Balaji Jegan Active (1.4k points) | 55 views

0 votes

0 answers

18

[4-14]Connectivity- Narsingh Deo
Show that a simple graph is nonseparable iff for any two given arbitrary edges a circuit can always be found that will include these two edges.

asked Jun 8 in Graph Theory by Ayush Upadhyaya Boss (11k points) | 32 views

0 votes

0 answers

19

[4-13]Connectivity-Narsingh Deo
Show that a graph G is non-separable iff every vertex pair can be placed in some circuit in G.

asked Jun 8 in Graph Theory by Ayush Upadhyaya Boss (11k points) | 15 views

0 votes

2 answers

20

Self-Doubt regarding Graph Coloring
This has reference to the below question https://gateoverflow.in/204092/gate2018-18?show=204092#q204092 My doubt is Suppose, I try to colour the vertices of this graph as follows First I colour vertex a and f with colour 1. Then I colour vertex e ... what points in mind do I need to remember so that I can colour any given graph with the minimum number of colours.

asked Jun 7 in Graph Theory by Ayush Upadhyaya Boss (11k points) | 78 views

0 votes

0 answers

21

Number of distinct cycles of length 4 in a complete graph of 6 labelled vertices.

asked Jun 6 in Graph Theory by Ayush Upadhyaya Boss (11k points) | 62 views

0 votes

2 answers

22

Number of Subgraphs of Kn?
I was searching for this question and found below link How many subgraphs does $K_5$ have? Here, in general, it is given to be $\displaystyle\sum_{r=0}^{n}\binom{n}{r}2^{\frac{r(r-1)}{2}}$ My doubt is that the case for $r=0$ is taken if we select none of the vertices of $K_n$? Why the case for $ r=0$ considered?

asked Jun 5 in Graph Theory by Ayush Upadhyaya Boss (11k points) | 41 views

0 votes

2 answers

23

Connectivity(4-20) Narsingh Deo
Is every regular graph of degree d(d$\geq$3) non-separable?If not, give a simple regular graph of degree 3 that is separable.

asked Jun 2 in Graph Theory by Ayush Upadhyaya Boss (11k points) | 71 views

0 votes

0 answers

24

Connectivity(4-10)-Narsingh Deo
Prove that in a connected graph G a vertex v is a cut-vertex if and only if there exist two(or more) edges x and y incident on v such that no circuit in G includes both x and y.

asked Jun 2 in Graph Theory by Ayush Upadhyaya Boss (11k points) | 38 views

0 votes

0 answers

25

Proper edge coloring
What is the minimal number K such that there exists a proper edge coloring of the complete graph on 8 vertices with K colors? A) 28 B) 8 C) 7 D) 15

asked Jun 1 in Graph Theory by Lakshman Patel RJIT Loyal (8k points) | 50 views

+2 votes

2 answers

26

Graph Theory
The largest possible number of vertices in a graph $G$, with $35$ edges and all vertices are of degree at least $3$ is $24$ $25$ $23$ $26$

asked May 28 in Graph Theory by Mr khan 3 (127 points) | 117 views

0 votes

3 answers

27

Graph theory | Graph Theory
A simple non directed graph contains $21$ edges, $3$ vertices of degree $4$ and the other vertices are of degree $2$.Then the number of vertices in the graph is? $8$ $13$ $18$ $21$

asked May 28 in Study Resources by Mr khan 3 (127 points) | 46 views

+1 vote

1 answer

28

#Algorithms #DFS
Consider the tree arcs of a $DFS$ traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for computing the shortest path between every pair of vertices. the shortest path from $W$ ... in the graph. the shortest paths from $W$ to only those nodes that are leaves of $T$. the longest path in the graph.

asked May 28 in Algorithms by iarnav Loyal (7.9k points) | 61 views

0 votes

1 answer

29

Graph Theory DM
In this graph it is said that $a,e,b,c,b$ is a path. But according to definition- in a path vertices and edges can't repeat so why this is a path. confused please clarify.

asked May 28 in Graph Theory by mbisht (223 points) | 48 views

0 votes

3 answers

30

madeeasy work book
Q. State whether the following statements are FALSE. (a). if $e$ is the minimum edge weight in a connected weighted graph,it must be among the edges of at least one minimum spanning tree of the graph. (b). if $e$ is the minimum edge weight in ... weighted graph,it must be among the edges of each one minimum spanning tree of the graph. which one is correct above two option?

asked May 24 in Algorithms by abhicse (39 points) | 84 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