Recent questions tagged graph-theory

+1 vote

1 answer

1

CMI2019-A-7
An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered timings, to ensure that spectators always have some match or other available to watch. Each match ... solve? Find a minimal colouring. Find a minimal spanning tree. Find a minimal cut. Find a minimal vertex cover.

asked Sep 13, 2019 in Graph Theory by gatecse Boss (17.5k points) | 68 views

+2 votes

2 answers

2

CMI2018-A-4
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$ $2$ $-1$ $0$ $1$

asked Sep 13, 2019 in Graph Theory by gatecse Boss (17.5k points) | 53 views

0 votes

1 answer

3

CMI2018-A-9
Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multi-talented ... : Find a maximum length simple cycle Find a maximum size independent set Find a maximum matching Find a maximal connected component

asked Sep 13, 2019 in Graph Theory by gatecse Boss (17.5k points) | 32 views

+1 vote

1 answer

4

CMI2018-B-3
Let $G$ be a simple graph on $n$ vertices. Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected. For every $n>2$, find a graph $G_{n}$ which has exactly $n$ vertices and $\binom{n-1}{2}$ edges, and is not connected.

asked Sep 13, 2019 in Graph Theory by gatecse Boss (17.5k points) | 43 views

+1 vote

0 answers

5

CMI2018-B-5
Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given to you by a $0-1$ matrix $A$ of size $n\times n$ as follows. For any $1\leq i,j\leq n,$ the entry $A[i,j]=1$ if and only if ... any two vertices are connected to each other by paths. Give a simple algorithm to find the number of connected components in $G.$ Analyze the time taken by your procedure.

asked Sep 13, 2019 in Graph Theory by gatecse Boss (17.5k points) | 26 views

+3 votes

2 answers

6

UGCNET-June-2019-II-5
For which values of $m$ and $n$ does the complete bipartite graph $k_{m,n}$ have a Hamiltonian circuit ? $m\neq n,\ \ m,n \geq 2$ $m\neq n,\ \ m,n \geq 3$ $m=n,\ \ m,n \geq 2$ $m= n,\ \ m,n \geq 3$

asked Jul 2, 2019 in Graph Theory by Arjun Veteran (431k points) | 302 views

0 votes

1 answer

7

Doubt on Bipartite Graph
What is T.C. to find maximum number of edges to be added to a tree so that it stays as a bipartite graph? Now my question is, why do we need to add edges to make a tree bipartite? A tree is already bipartite graph. Right?? Again how do we add edges in it?? Is BFS or DFS do any improvement in such a tree?? How to think such a question??

asked Jun 2, 2019 in Algorithms by srestha Veteran (119k points) | 87 views

+2 votes

1 answer

8

ACE ACADEMY BOOKLET
Which of the following is $\textbf{not}$ TRUE? (a) In a complete graph $K_n$ ($n$ $\geq$ $3$), Hamiltonian cycle exists for all n. (b) In a complete bipartite graph $K_{m,n}$ (m $\geq$ 2 and n $\geq$2), Hamiltonian cycle exists $\Leftrightarrow$ ... Hamiltonian cycle exits for all $n$ (d) In a wheel graph $W_n$ ($n \geq 4$), Hamiltonian cycle exits $\Leftrightarrow$ $n$ is even.

asked May 26, 2019 in Graph Theory by `JEET Boss (19.2k points) | 85 views

+1 vote

2 answers

9

#ACE_ACADEMY_DISCRETE_MATHS_BOOKLET.
Which of the following is not true? (a) Number of edge-disjoint Hamiltonian cycles in $K_7$ is $3$ (b) If $G$ is a simple graph with $6$ vertices and the degree of each vertex is at least $3$, then the Hamiltonian cycle exists in ... simple graph with $5$ vertices and $7$ edges, then the Hamiltonian cycle exists in $G$ Please help me understand all the options.

asked May 26, 2019 in Graph Theory by `JEET Boss (19.2k points) | 148 views

+1 vote

1 answer

10

Made easy Test Series:Graph Theory+Automata
Consider a graph $G$ with $2^{n}$ vertices where the level of each vertex is a $n$ bit binary string represented as $a_{0},a_{1},a_{2},.............,a_{n-1}$, where each $a_{i}$ is $0$ or $1$ ... and $y$ denote the degree of a vertex $G$ and number of connected component of $G$ for $n=8.$ The value of $x+10y$ is_____________

asked May 23, 2019 in Graph Theory by srestha Veteran (119k points) | 157 views

+5 votes

0 answers

11

IISc CSA - Research Interview Question
Prove that the rank of the Adjacency Matrix which is associated with a $k-$ regular graph is $k.$

asked May 22, 2019 in Graph Theory by ankitgupta.1729 Boss (17.1k points) | 106 views

+2 votes

2 answers

12

GateForum Question Bank :Graph Theory
What is the probability that there is an edge in an undirected random graph having 8 vertices? 1 1/8

asked May 19, 2019 in Graph Theory by Hirak Active (3.6k points) | 161 views

0 votes

2 answers

13

ACE Workbook:
ACE Workbook: Q) Let G be a simple graph(connected) with minimum number of edges. If G has n vertices with degree-1,2 vertices of degree 2, 4 vertices of degree 3 and 3 vertices of degree-4, then value of n is ? Can anyone give the answer and how to approach these problems. Thanks in advance.

asked May 12, 2019 in Graph Theory by chandan2teja (147 points) | 107 views

0 votes

1 answer

14

IIIT PGEE 2019
Which of the following gives O(1) complexity if we want to check whether an edge exists between two given nodes in a graph? Adjacency List Adjacency Matrix Incidence Matrix None of these

asked Apr 29, 2019 in DS by manikgupta123 (81 points) | 153 views

+1 vote

1 answer

15

Difference between DAG and Multi-stage graph
I have trouble understanding the difference between DAG and Multi-stage graph. I know what each of them is But I think that a multi-stage graph is also a DAG. Are multi-stage graphs a special kind of DAG?

asked Apr 28, 2019 in Graph Theory by gmrishikumar Active (2.2k points) | 91 views

0 votes

0 answers

16

ISI2017-PCB-CS-1(b)
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.

asked Apr 8, 2019 in Graph Theory by akash.dinkar12 Boss (42.5k points) | 62 views

0 votes

0 answers

17

Graph Decomposition
What is Graph Decomposition & is it in the syllabus? If it is then please can anyone share some online resources for it. Thank you.

asked Mar 17, 2019 in Graph Theory by noxevolution (101 points) | 38 views

0 votes

0 answers

18

Narsingh deo
What is meant by edge disjoint hamiltonian circuits in a graph

asked Mar 5, 2019 in Graph Theory by Winner (445 points) | 80 views

+1 vote

0 answers

19

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 Feb 18, 2019 in Graph Theory by Sayan Bose Loyal (7.4k points) | 108 views

+8 votes

9 answers

20

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, 2019 in Graph Theory by Arjun Veteran (431k points) | 4.1k views

+9 votes

5 answers

21

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, 2019 in Graph Theory by Arjun Veteran (431k points) | 4k views

+1 vote

0 answers

22

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, 2019 in Graph Theory by Ashish Goyal (433 points) | 143 views

0 votes

2 answers

23

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

asked Jan 29, 2019 in Graph Theory by amit166 Junior (775 points) | 114 views

0 votes

0 answers

24

Counting

asked Jan 25, 2019 in Graph Theory by screddy1313 (481 points) | 51 views

0 votes

0 answers

25

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

asked Jan 25, 2019 in DS by Nandkishor3939 Active (1.3k points) | 109 views

0 votes

1 answer

26

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, 2019 in Graph Theory by sudharshan (289 points) | 87 views

0 votes

0 answers

27

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, 2019 in Set Theory & Algebra by Nandkishor3939 Active (1.3k points) | 61 views

0 votes

1 answer

28

MadeEasy Test Series: Discrete Mathematics - Graph Thoery
The number of labelled subgraphs possible for the graph given below.

asked Jan 19, 2019 in Graph Theory by snaily16 (245 points) | 344 views

0 votes

0 answers

29

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, 2019 in Algorithms by Iamniks4 (31 points) | 34 views

0 votes

0 answers

30

Ace Test Series: Graph Theory - 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, 2019 in Graph Theory by Na462 Loyal (7k points) | 98 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