Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Webpage for Graph Theory:
Recent questions tagged graph-theory
1
votes
1
answer
481
Strongly Connected, Unilaterally connected and weakly Connected
Hi Guys, Is there any quick way of verifying Graph is Strongly Connected, Unilaterally connected and weakly Connected ? For Example - If 1 dead point then graph is Unilaterally Connected and If 2 dead points then graph is Weakly Connected.
Hi Guys,Is there any quick way of verifying Graph is Strongly Connected, Unilaterally connected and weakly Connected ?For Example - If 1 dead point then graph is Unilate...
Chhotu
7.7k
views
Chhotu
asked
Nov 10, 2017
Graph Theory
graph-theory
discrete-mathematics
algorithms
+
–
1
votes
0
answers
482
Algo. for Graph Isomorphism
Hi Guys, There is no algorithm to find graph isomorphism (as mentioned by @Rupendra Choudhary) then how much time does Brute force algorithm will takes (means one answer could be n! but can we do better then this )?
Hi Guys,There is no algorithm to find graph isomorphism (as mentioned by @Rupendra Choudhary) then how much time does Brute force algorithm will takes (means one answer c...
Chhotu
230
views
Chhotu
asked
Nov 10, 2017
Algorithms
graph-theory
algorithms
engineering-mathematics
+
–
0
votes
1
answer
483
Which one is right ? Graph theory
1. whenever cut edges exist, cut vertices also exist because at least one vertex of a cut edge is a cut vertex. 2. if a cut vertex exists, then a cut edge may or may not exist.
1. whenever cut edges exist, cut vertices also exist because at least one vertex of a cut edge is a cut vertex.2. if a cut vertex exists, then a cut edge may or may not ...
hem chandra joshi
1.2k
views
hem chandra joshi
asked
Nov 9, 2017
Graph Theory
graph-theory
+
–
3
votes
1
answer
484
Cut Sets in graph
Question: Number of cut sets possible a tree with 10 vertices _________ My approach : Number of edges in a tree with 10 vertices = 9. Each of these can be considered as a cut set as deleting one edge necessarily disconnects the graph. Also any combination (I mean ... cut sets = 2^9 - 1 = 511. But the answer is written 9. Apparently they are not considering the super sets. Why?
Question: Number of cut sets possible a tree with 10 vertices _________My approach : Number of edges in a tree with 10 vertices = 9. Each of these can be considered as a...
humblefool
3.4k
views
humblefool
asked
Nov 9, 2017
Graph Theory
engineering-mathematics
graph-theory
discrete-mathematics
cut
set-theory&algebra
+
–
0
votes
1
answer
485
complement of a graph let n=3 it is complete graph what is meant by its complement ?
hem chandra joshi
1.9k
views
hem chandra joshi
asked
Nov 7, 2017
Graph Theory
graph-theory
+
–
1
votes
2
answers
486
PERFECT MATCHING IN COMPLETE GRAPH
Parshu gate
2.7k
views
Parshu gate
asked
Nov 6, 2017
Graph Theory
discrete-mathematics
graph-theory
graph-matching
+
–
2
votes
1
answer
487
What are the relevant chapters for GATE from the Graph Theory book by Narsingh Deo?
What are the relevant chapters for GATE from the Graph Theory book by Narsingh Deo?
What are the relevant chapters for GATE from the Graph Theory book by Narsingh Deo?
GäteMann
1.7k
views
GäteMann
asked
Nov 5, 2017
Graph Theory
graph-theory
narsingh-deo
+
–
0
votes
0
answers
488
GRAPH THEORY EDGE COLORING
Parshu gate
608
views
Parshu gate
asked
Nov 5, 2017
Algorithms
graph-theory
graph-coloring
edge-coloring
+
–
0
votes
0
answers
489
Can any one explain below line clearly with example ?
The bipartite graph G = (V ,E) with bipartition (V1, V2) has a complete matching from V1 to V2 if and only if |N(A)| ≥ |A| for all subsets A of V1.
The bipartite graph G = (V ,E) with bipartition (V1, V2) has a complete matching from V1 to V2 if and only if |N(A)| ≥ |A| for all subsetsA of V1.
hem chandra joshi
230
views
hem chandra joshi
asked
Oct 25, 2017
Mathematical Logic
graph-theory
+
–
2
votes
1
answer
490
An undirected graph has an even number of vertices of odd degree.
What does it means ? An undirected graph has an even number of vertices of odd degree. But let a 4 vertex cycle graph if it not complete having even vertex and even degree each vertex .Is it rt?
What does it means ?An undirected graph has an even number of vertices of odd degree. But let a 4 vertex cycle graph if it not complete having even vertex and even degree...
hem chandra joshi
6.9k
views
hem chandra joshi
asked
Oct 24, 2017
Mathematical Logic
graph-theory
+
–
0
votes
0
answers
491
Chromatic polynomials
Check which of the following can be chromatic polynomials of a non-null graph ? i) x5 - 4x3 - 2x2 + x + 4 ii) x6 - 3x5 + 2x4 - 1 P.S I know for a non-null graph G, X(G) (i.e. chromatic number) is at least 2. How to proceed further ??
Check which of the following can be chromatic polynomials of a non-null graph ?i) x5 - 4x3 - 2x2 + x + 4ii) x6 - 3x5 + 2x4 - 1P.S I know for a non-null graph G, X(G) (i.e...
just_bhavana
1.5k
views
just_bhavana
asked
Oct 24, 2017
Mathematical Logic
graph-theory
graph-coloring
+
–
1
votes
0
answers
492
Graph theory
What type of graph is STAR? A. Bipartite B. Tripartite C. Mutipartite PS : I know a star graph is bipartite but can't we say that a bipartite graph is also tripartite . I. E. It can be partitioned into 3 independent sets. Similarly , it is mutipartite as well.
What type of graph is STAR?A. BipartiteB. TripartiteC. MutipartitePS : I know a star graph is bipartite but can't we say that a bipartite graph is also tripartite . I. E...
VS
521
views
VS
asked
Oct 23, 2017
Others
discrete-mathematics
graph-theory
+
–
3
votes
0
answers
493
Self Doubt ( Decrease key operation )
While going through dijkstra's algorithm, there is a term "decrease key". I am not getting the meaning when it says "we do decrease key operation". What exactly we do and what is the meaning of decrease key ?
While going through dijkstra's algorithm, there is a term "decrease key". I am not getting the meaning when it says "we do decrease key operation". What exactly we do and...
Hitoshi
1.6k
views
Hitoshi
asked
Oct 15, 2017
Algorithms
algorithms
dijkstras-algorithm
graph-theory
+
–
4
votes
1
answer
494
GATE2001-2.15 GATE1994-1.6
How many undirected graphs are possible with n vertices if graphs are not necessarily connected if they are necessarily connected
How many undirected graphs are possible with n verticesif graphs are not necessarily connectedif they are necessarily connected
rishi71662data4
1.4k
views
rishi71662data4
asked
Oct 12, 2017
Graph Theory
graph-theory
combinatory
+
–
1
votes
0
answers
495
Narsing Deo--Graph theory
Show that every planar graph with at least 4 vertices has at least 4 vertices of degree less than or equal to 5.This will also prove there is no 6-connected planar graph. I have proved it partly,can someone please give provide a simple proof to ... also 2* no of edges. Is there a interconnection between these terms no just in terms of formula?Can we use it interchangebly.
Show that every planar graph with at least 4 vertices has at least 4 vertices of degree less than or equal to 5.This will also prove there is no 6-connected planar graph....
Surajit
500
views
Surajit
asked
Oct 8, 2017
Graph Theory
graph-theory
+
–
0
votes
1
answer
496
GRAPH THEORY
Let G be an undirected graph on n nodes. Any two of the following statements implies the third. Is it true or False? 1. G is connected. 2. G doesn't have cycles. 3. G contain n-1 edges.
Let G be an undirected graph on n nodes. Any two of the following statements implies the third. Is it true or False?1. G is connected.2. G doesn't have cycles.3. G contai...
User007
509
views
User007
asked
Sep 27, 2017
Graph Theory
graph-theory
graph-connectivity
true-false
+
–
2
votes
1
answer
497
Ace Test Series: Graph Theory - Graph Connectivity
Shivam Chauhan
685
views
Shivam Chauhan
asked
Sep 26, 2017
Graph Theory
ace-test-series
graph-theory
graph-connectivity
+
–
0
votes
2
answers
498
UGC NET CSE | December 2008 | Part 2 | Question: 2
The graph K3,4 has: $3$ edges $4$ edges $7$ edges $12$ edges
The graph K3,4 has:$3$ edges $4$ edges $7$ edges $12$ edges
rishu_darkshadow
901
views
rishu_darkshadow
asked
Sep 25, 2017
Graph Theory
ugcnetcse-dec2008-paper2
graph-theory
+
–
3
votes
0
answers
499
Preparation of Graph Theory
Hello Sir, I have gone through the previous year questions and also gave some tests till now. From this experience I have realized that in GRAPH THEORY - almost 90% of the questions are theory based as a result I am not able to give ... and suggestions on how to get out of this situation and start understanding the subject answer the questions with confidence.. Thank you
Hello Sir, I have gone through the previous year questions and also gave some tests till now. From this experience I have realized that in GRAPH THEORY - ...
Parshu gate
446
views
Parshu gate
asked
Sep 22, 2017
Study Resources
graph-theory
discrete-mathematics
engineering-mathematics
+
–
1
votes
0
answers
500
GATE 1987#Binary Tree
https://gateoverflow.in/2604/gate1995_1-17 .What is the degree of a node in a tree? Is it same as a graph OR the number of children of that node?
https://gateoverflow.in/2604/gate1995_1-17 .What is the degree of a node in a tree? Is it same as a graph OR the number of children of that node?
Abhi Girin
375
views
Abhi Girin
asked
Sep 21, 2017
Programming in C
data-structures
binary-tree
graph-theory
+
–
0
votes
0
answers
501
graph theory
"A planar graph need not to be connected" Can someone plz explain with an example .
"A planar graph need not to be connected" Can someone plz explain with an example .
Pawan Kumar 2
215
views
Pawan Kumar 2
asked
Sep 20, 2017
Set Theory & Algebra
gra
graph-theory
+
–
0
votes
0
answers
502
DYNAMIC PROGRAMMING
Parshu gate
429
views
Parshu gate
asked
Sep 17, 2017
Algorithms
algorithms
dynamic-programming
graph-theory
+
–
0
votes
1
answer
503
UGC NET CSE | December 2009 | Part 2 | Question: 22
The number of edges in a complete graph of n vertices is (A) n (B) n(n – 1)/2 (C) n(n + 1)/2 (D) (n^2)/2
The number of edges in a complete graph of n vertices is(A) n(B) n(n – 1)/2(C) n(n + 1)/2(D) (n^2)/2
rishu_darkshadow
816
views
rishu_darkshadow
asked
Sep 17, 2017
Graph Theory
ugcnetcse-dec2009-paper2
graph-theory
+
–
0
votes
1
answer
504
UGC NET CSE | December 2009 | Part 2 | Question: 02
Circle has ____________ (A) No vertices (B) Only 1 vertex (C) ∞ vertices (D) None of these
Circle has ____________(A) No vertices(B) Only 1 vertex(C) ∞ vertices(D) None of these
rishu_darkshadow
960
views
rishu_darkshadow
asked
Sep 16, 2017
Graph Theory
ugcnetcse-dec2009-paper2
graph-theory
+
–
2
votes
2
answers
505
Graph Theory
Consider a 'reversed Kruskal' Algorithm for computing a MST. Initialize T to be the set of all edges in the graph. Now consider edges from largest to smallest cost. For each edge, delete it from T if that edge belongs to a cycle in T. Assuming all the edge costs are distinct, does this new algorithm correctly compute a MST? a) Yes b) no c) cant say
Consider a 'reversed Kruskal' Algorithm for computing a MST. Initialize T to be the set of all edges in the graph. Now consider edges from largest to smallest cost. For e...
Rakshit Gupta
1.3k
views
Rakshit Gupta
asked
Sep 13, 2017
Graph Theory
graph-theory
graph-matching
graph-connectivity
spanning-tree
+
–
1
votes
2
answers
506
Graph theory
The total number of non isomorphic graph which can be formed with 3 vertices________________________
The total number of non isomorphic graph which can be formed with 3 vertices________________________
srestha
864
views
srestha
asked
Sep 13, 2017
Graph Theory
graph-theory
+
–
0
votes
1
answer
507
Virtual Gate Test Series: Discrete Mathematics - Graph Theory
Which of the following is true? The size of the maximum independent set on G is the same as the size of maximum clique on G'(Complement of G) The size of minimum vertex cover on G is the same as the size of maximum ... ;(complement of G) The size of minimum vertex cover on G is the same as the size of maximum clique on G'
Which of the following is true?The size of the maximum independent set on G is the same as the size of maximum clique on G'(Complement of G)The size of minimum vertex cov...
kunalv
426
views
kunalv
asked
Sep 10, 2017
Graph Theory
discrete-mathematics
graph-theory
virtual-gate-test-series
+
–
1
votes
0
answers
508
How many simple path from u to v going through w?
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, ... vertices in G. How many simple paths are there from u to v going through w? Please explain in detail. Thank you.
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...
Hemant Parihar
898
views
Hemant Parihar
asked
Sep 9, 2017
Graph Theory
graph-theory
shortest-path
+
–
1
votes
1
answer
509
Graph theory Narshing Deo
theorem no 10.1 Narsingh Deo prove that the no. of labeled graph of n vertices of n is 2^(n(n-1)/2)
theorem no 10.1 Narsingh Deoprove that the no. of labeled graph of n vertices of n is 2^(n(n-1)/2)
Ravi prakash pandey
383
views
Ravi prakash pandey
asked
Sep 5, 2017
Graph Theory
graph-theory
graph-connectivity
descriptive
+
–
0
votes
1
answer
510
Graph theory-Relation.
Can anyone explain "closure of relation" or share link for that.
Can anyone explain "closure of relation" or share link for that.
elakashi sharma
292
views
elakashi sharma
asked
Aug 21, 2017
Mathematical Logic
graph-theory
+
–
Page:
« prev
1
...
12
13
14
15
16
17
18
19
20
21
22
...
30
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register