Recent questions tagged graph-theory

0 votes

0 answers

1

JEST 2019
A directed graph with n vertices, in which each vertex has exactly 3 outgoing edges. Which one is true? A) All the vertices have indegree = 3 . B) Some vertices will have indegree exactly 3. C)Some vertices have indegree atleast 3. D) Some of the vertices have indegree atmost 3

asked 4 days ago in Graph Theory by Sayan Bose Loyal (5.9k points) | 32 views

0 votes

1 answer

2

JEST Sample Question-4
A tournament is a directed graph in which there is exactly one directed edge between every pair of vertices. Let Tn be a tournament on n vertices. (a) Use induction to prove the following statement: Tn has a directed hamiltonian path (a directed ... or a simple description of the steps in the algorithm, will suffice. What is the worst case time complexity of your algorithm?

asked Feb 15 in Algorithms by sripo Active (1.5k points) | 38 views

0 votes

1 answer

3

JEST Sample Question-5
Describe two different data structures to represent a graph. For each such representation, specify a simple property about the graph that can be more efficiently checked in that representation than in the other representation. Indicate the worst case time required for verifying both of your properties in either representation.

asked Feb 15 in Algorithms by sripo Active (1.5k points) | 17 views

0 votes

4 answers

4

GATE2019-12
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to $n!$ $(n-1)!$ $1$ $\frac{(n-1)!}{2}$

asked Feb 7 in Graph Theory by Arjun Veteran (384k points) | 2.1k views

+1 vote

1 answer

5

GATE2019-38
Let $G$ be any connected, weighted, undirected graph. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimum-weight edge crossing the cut. Which of the following statements is/are TRUE? I only II only Both I and II Neither I nor II

asked Feb 7 in Graph Theory by Arjun Veteran (384k points) | 1.9k views

0 votes

1 answer

6

GATE 2019 8
Q.8 Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to 1. (n-1)!/2 2. 1 3.(n-1)! 4. n!

asked Feb 7 in Graph Theory by Ram Swaroop Active (2.2k points) | 211 views

0 votes

0 answers

7

GeeksforGeeks
Let G be a graph with no isolated vertices, and let M be a maximum matching of G. For each vertex v not saturated by M, choose an edge incident to v. Let T be the set of all the chosen edges, and let L = M ∪ T. Which of the following option is TRUE? A L is always ... G. B L is always a minimum edge cover of G. C Both (A) and (B) D Neither (A) nor (B) Can anyone pls help solving this?

asked Jan 30 in Graph Theory by Ashish Goyal (337 points) | 90 views

0 votes

1 answer

8

#GRAPH THEORY
A simple regular graph n vertices and 24 edges, find all possible values of n.

asked Jan 29 in Graph Theory by amit166 Junior (693 points) | 59 views

0 votes

0 answers

9

Counting

asked Jan 25 in Graph Theory by screddy1313 (401 points) | 29 views

0 votes

0 answers

10

Number of sub graphs possible
Number of labelled subgraphs possible for the graph given below______________

asked Jan 25 in DS by Nandkishor3939 Active (1.2k points) | 65 views

0 votes

1 answer

11

Virtual Gate
A complete graph on n vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let G be a complete graph on 10 vertices. Let u, v, w be three distinct vertices in G. How many simple paths are there from u to v going through w?

asked Jan 24 in Graph Theory by sudharshan (289 points) | 59 views

0 votes

0 answers

12

Homomorphic and Isomorphic graph
This a random question came into my mind… Are the below statements true: 1] If a graph is Homomorphic to our graph then it is also Isomorphic to that graph. 2]If a graph is Isomorphic to our graph then it is also Homomorphic graph.

asked Jan 21 in Set Theory & Algebra by Nandkishor3939 Active (1.2k points) | 31 views

0 votes

1 answer

13

made easy test
The number of labelled subgraphs possible for the graph given below.

asked Jan 19 in DS by snaily16 (255 points) | 214 views

0 votes

0 answers

14

Algorithm questions on graphs
let Gn be a complete graph on n vertices where n>2 such that each vertex is labeled by a distinct number 1,2, 3, 4, …, n , and each edge is labeled by the sum of its endpoint labels. Let f(Gn) be the minimum sum of edge labels in any path that touches every vertex in exactly once. How many values of satisfy f(Gn)2013 (mod n) ?___________

asked Jan 19 in Algorithms by Iamniks4 (63 points) | 14 views

0 votes

0 answers

15

Number of Cut edges
If G is a connected simple graph with 10 vertices in which degree of every vertex is 2 then number of cut edges in G is ?

asked Jan 19 in Graph Theory by Na462 Loyal (8.6k points) | 44 views

0 votes

1 answer

16

ME test series question on graph theory

asked Jan 17 in Graph Theory by Shankar Kakde (369 points) | 55 views

0 votes

2 answers

17

Applied Course 2019 Mock1-36
Naveen invited seven of his friends to a party. At the party, several pairs of people shook hands, although no one shook hands with themselves or shook hands with the same person more than once. After the party, Naveen asked each of his seven friends ... distinct positive integers. Given that his friends were truthful, how many hands did Naveen shake? $4$ $5$ $6$ $7$

asked Jan 16 in Graph Theory by Applied Course Junior (757 points) | 82 views

0 votes

0 answers

18

Made Easy
What are all the conditions for the degree sequence to be graphic?

asked Jan 16 in Algorithms by gate_dreams (309 points) | 29 views

+1 vote

2 answers

19

Tripartite Graph
The number of vertices,edges and colors required for proper coloring in Tripartite graph K<3,2,5> will be : 10 , 31 , 3 10 , 30 , 3 10 , 30 , 2 None

asked Jan 16 in Graph Theory by Na462 Loyal (8.6k points) | 59 views

+1 vote

1 answer

20

Vertex Connectivity
The Vertex Connectivity of Graph is : 1 2 3 None

asked Jan 16 in Graph Theory by Na462 Loyal (8.6k points) | 49 views

+2 votes

1 answer

21

How many Binary Search Trees are possible for a labelled nodes?
Let us there are n nodes which are labelled. Then the number of trees possible is given by the Catalan Number i.e $\binom{2n}{n} / (n+1)$ Then the binary search trees possible is just 1?

asked Jan 16 in DS by sripo Active (1.5k points) | 83 views

0 votes

1 answer

22

CUT VERTEX
plz solve this problem..

asked Jan 9 in Mathematical Logic by Vikas123 (359 points) | 53 views

0 votes

0 answers

23

VirtualGATE
Let G be a graph on n vertices with 4n-16 edges. Consider the following: 1. There is a vertex of degree smaller than 8 in G. 2. There is a vertex such that there are less than 16 vertices at distance exactly 2 from it. Which of the following is TRUE: a) 1 only b) 2 only c) Both 1 and 2 d) neither.

asked Jan 9 in Algorithms by pps121 Active (1.5k points) | 56 views

0 votes

0 answers

24

Made_easy_test_series
The number of totally ordered sets compatible to the given POSET are ________.

asked Jan 7 in Graph Theory by Shivam Kasat Active (1.9k points) | 141 views

0 votes

0 answers

25

simple graph formula
why in this planar graph this theorem ,”sum of degrees of faces or regions is twice the number of edges” is not true as it should hold for all planar graphs?? Note: numbers denote region or face

asked Jan 5 in Graph Theory by BHASHKAR (21 points) | 34 views

0 votes

0 answers

26

The maximum value of ‘n’ so that overflow cannot occur. Algorithms MeadEasy.

asked Jan 3 in Algorithms by susgir2 Active (1.4k points) | 51 views

0 votes

0 answers

27

Eulerian Graph has to be connected?
A disconnected graph having even degree vertices can it be a euler graph?

asked Jan 1 in Graph Theory by sripo Active (1.5k points) | 67 views

0 votes

0 answers

28

What to study & from where to study - Graph Theory for GATE 2019.
Are the following topics necessary/ apt to study for gate.(Bold items are explicitly mentioned in gate syllabus document) Connectivity Matching Coloring Cuts Covering Independent Sets Planar Graphs Isomorphism Walks, Trails, Paths, ... taking a lot of time. Can anyone please recommend a reliable and simple resource to go with.

asked Dec 29, 2018 in Graph Theory by Krishna Sai Vootla (25 points) | 87 views

0 votes

0 answers

29

#graph
why DFS cannot find shortest path but BFS can?

asked Dec 29, 2018 in Algorithms by Deepesh Pai (499 points) | 25 views

0 votes

1 answer

30

In a 3-array tree if internal nodes have exactly 3 children,the number of leaf nodes will be __ ?

asked Dec 25, 2018 in DS by sripo Active (1.5k points) | 99 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