Dark Mode

Recent questions tagged graph-matching

1 vote

0 answers

1

DRDO CSE 2022 Paper 1 | Question: 9
Count the number of perfect matchings in the bipartite graph whose adjacency matrix $\text{A}$ is as follows. \[\left[\begin{array}{lll} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{array}\right]\]

admin asked in Graph Theory Dec 15, 2022

by admin

67 views

4 votes

2 answers

2

TIFR CSE 2022 | Part B | Question: 2
Let $G=(V, E)$ be an undirected simple graph. A subset $M \subseteq E$ is a matching in $G$ if distinct edges in $M$ do not share a vertex. A matching is maximal if no strict superset of $M$ is a matching. How many maximal matchings does the following graph have? $1$ $2$ $3$ $4$ $5$

admin asked in Graph Theory Sep 1, 2022

by admin

315 views

3 votes

1 answer

3

TIFR CSE 2022 | Part B | Question: 6
We are given a graph $G$ along with a matching $M$ and a vertex cover $C$ in it such that $|M|=|C|$. Consider the following statements: $M$ is a maximum matching in $G$. $C$ is a minimum vertex cover in $G$. $G$ is a bipartite graph. Which of ... $(1)$ and $(2)$ are correct All the three statements $(1), (2),$ and $(3)$ are correct

admin asked in Graph Theory Sep 1, 2022

by admin

370 views

0 votes

0 answers

4

Best Open Video Playlist for Graph Theory: Matching Topic | Discrete Mathematics
Please list out the best free available video playlist for Graph Theory: Matching Topic from Discrete Mathematics as an answer here (only one playlist per answer). We'll then select the best playlist and add to GO ... ones are more likely to be selected as best. For the full list of selected videos please see here

makhdoom ghaya asked in Study Resources Aug 15, 2022

by makhdoom ghaya

51 views

1 vote

1 answer

5

TIFR CSE 2021 | Part A | Question: 6
A matching in a graph is a set of edges such that no two edges in the set share a common vertex. Let $G$ be a graph on $n$ $\textit{vertices}$ in which there is a subset $M$ of $m$ $\textit{edges}$ which is a matching. Consider a random process where each vertex in the ... $\left ( 1-p^{2} \right )^{m}$ $1-\left ( 1-p\left ( 1-p \right ) \right )^{m}$

soujanyareddy13 asked in Graph Theory Mar 25, 2021

by soujanyareddy13

423 views

1 vote

1 answer

6

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

gatecse asked in Graph Theory Sep 13, 2019

504 views

1 vote

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?

Ashish Goyal asked in Graph Theory Jan 30, 2019

by Ashish Goyal

993 views

0 votes

2 answers

8

Gateforum Test Series: Graph Theory - Graph Matching

Gupta731 asked in Graph Theory Jan 2, 2019

601 views

3 votes

1 answer

9

Zeal Test Series 2019: Graph Theory - Graph Matching

Prince Sindhiya asked in Graph Theory Dec 22, 2018

by Prince Sindhiya

563 views

0 votes

1 answer

10

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

Na462 asked in Mathematical Logic Oct 13, 2018

by Na462

1.3k views

1 vote

1 answer

11

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

abhishek1995_cse asked in Graph Theory Jul 24, 2018

by abhishek1995_cse

453 views

0 votes

1 answer

12

Perfect Matching
Perfect matching is a set of edges such that each vertex appears only once and all vertices appear at least once (EXACTLY one appearance). So for n vertices perfect matching will have n/2 edges and there won't be any perfect matching if n is odd. ... 't know whether i got it properly or not. Can please anybody explain the Perfect matching in a complete graph with simpler examples ?

Na462 asked in Graph Theory Jun 10, 2018

by Na462

750 views

1 vote

1 answer

13

Ace Test Series: Graph Theory - Matching
my answer is C but the answer given is A someone please explain

ashish pal asked in Graph Theory Jan 20, 2018

375 views

1 vote

2 answers

14

graph theory
Maximum no of edges in a triangle-free, simple planar graph with 10 vertices

Parshu gate asked in Graph Theory Dec 23, 2017

670 views

2 votes

1 answer

15

Matchings in a Graph

Parshu gate asked in Graph Theory Nov 29, 2017

397 views

2 votes

0 answers

16

chromatic number
Let G be a planar Graph Such that every phase is bordered by exactly 3 edges which of the following can never be value for X(G) a)2 b)3 C)4 d)none of these

Parshu gate asked in Graph Theory Nov 11, 2017

905 views

1 vote

2 answers

17

PERFECT MATCHING IN COMPLETE GRAPH

Parshu gate asked in Graph Theory Nov 6, 2017

2.1k views

0 votes

0 answers

18

DISCRETE
Let T be a tree with n vertices and k be the maximum size of an independent set in T. Then the size of maximum matching in T is (A) k (B) n−k (C) (n−1)/2

ashutoshsharma asked in Graph Theory Sep 21, 2017

by ashutoshsharma

183 views

2 votes

2 answers

19

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

Rakshit Gupta asked in Graph Theory Sep 14, 2017

by Rakshit Gupta

902 views

3 votes

3 answers

20

[Discrete Maths] Graph Theory Rosen,Chromatic number
What are the chromatic number of following graphs? Answer is 6 and 4 respectively.But i am getting 3 for both. Please someone confirm this?

rahul sharma 5 asked in Mathematical Logic Jun 13, 2017

by rahul sharma 5

1.4k views

0 votes

1 answer

21

[Discrete maths] graph theory Perfect matching
When matching number and covering number are same then can we say that it is a perfect matching case?Do i need to check the elements of the set( edges in both matching and covering) also if their cardinality is same?If yes,then can someone give me ... but still it is not a perfect match?I am not able to find such a case and i think it will not exist.

rahul sharma 5 asked in Mathematical Logic Jun 8, 2017

by rahul sharma 5

799 views

0 votes

1 answer

22

narsingh deo
In a village there are equal no of boys and girls of marriageable age.Each boy dates a certain no. of girls and each girl dates a certain number of boys,under what condition is it possible that every girl and boy gets married to one of their dates?

Learner_jai asked in Graph Theory Feb 27, 2017

463 views

2 votes

3 answers

23

made easy
Please explain how perfect matching in given tree is 1? Why not 3 with edges ab,ce,df?

gaurav9822 asked in Mathematical Logic Aug 10, 2016

509 views

6 votes

3 answers

24

Virtual Gate Test Series: Discrete Mathematics - Graph Theory (Matching Number)
Find the matching number for the given graph-

learncp asked in Graph Theory Jan 26, 2016

697 views

Page:

Recent questions tagged graph-matching