Questions tagged [matching-theory]
For questions about matchings in graphs.
566
questions
-1
votes
3
answers
84
views
An Optimization Problem With Permutation Function [closed]
When I tried to solve an one-to-one assignment problem, I constructed it as the following optimization problem, which is a min-max optimization problem with the optimization objective being functions.
...
- 11
0
votes
0
answers
35
views
Let A be a 2n-element set. Find the number of pairings of A.
I am having trouble understanding how one of the solutions to this problem works:
Let a pairing of A partition the set into 2-element subsets. Example: a pairing of {a, b, c, d, e, f, g, h} is {{a, b},...
- 47.4k
0
votes
0
answers
34
views
How DTW decides which element to take next?
I'm currently working on an DTW algorithm implementation and do have a question about how DTW works if the next steps are the same or if the correct next step is the actually not less-cost one.
I do ...
- 47.4k
0
votes
1
answer
49
views
A proof for the statement: The 3-Dimensional matching problem is NP-Complete
The 3-Dimensional Matching Problem is relatively well known in the fields of discrete mathematics and computer science. The problem consists of determining whether a tripartite
$3$-hypergraph with ...
- 47.4k
16
votes
5
answers
8k
views
A magic trick - find out the fifth card if four is given
Here is a magic trick I saw. My question is how the magician and his partner did it.
Given the simple French deck of cards, with $52$ cards. A person from the audience chooses randomly five cards ...
- 646
0
votes
0
answers
8
views
Bipartite Matching With Distant Constraints
I am investigating the complexity of the following problem.
Let a complete bipartite graph $G = (V \cup V', E: V \times V')$ with |V| < |V'|, where the nodes have weights $w: V \cup V' \to \mathbb{...
- 9
2
votes
1
answer
43
views
If a graph is 1-factoreable, then it has no cut vertex.
I'm trying to prove the statement: if a graph $G$ is 1-factorable, then $G$ has no cut vertex.
Assuming $G$ has a cut vertex, let be $v\in V(G)$ a cut vertex of $G$. Then the connected components of $...
- 51.8k
2
votes
0
answers
16
views
Matching number of a graph is equal to the independence number of its line graph.
Let $\alpha'(G)$ the matching number of a graph $G$, $L(G)$ its line graph and $\alpha(L(G))$ the stability number of its line graph. I need to prove that $\alpha'(G)=\alpha(L(G))$. Let $M$ be a ...
- 2,117
1
vote
0
answers
18
views
How sensitive are maximum-size matchings to edge deletion in random graphs?
My question concerns the sensitivity of maximum-size matchings (and more generally maximum-size $k$-cycle collections) to deletion of an edge in the graph.
Given a graph $G$, let a $k$-cycle be a ...
- 11
6
votes
2
answers
3k
views
Matching in a bipartite graph saturating $X$
Let $G$ be a bipartite graph with bipartitions $X, Y$ . Suppose $X$ has no isolated vertices (i.e., vertices with degree $0$) and for all $(x,y) ∈ E$ with $x ∈ X$, $y ∈ Y$, $degree(x) ≥ degree(y)$. ...
- 435
0
votes
1
answer
32
views
Understanding proof of Hall's graph theorem
I am struggling with understanding proof of Halls theorem.
Theorem: Let $G=(V_1\cup V_2,E)$ be a bipartite graph and for each $U\subseteq V_1$ let $$N_{G}(U)=\{v\in V_2\ :\ \exists u\in U\text{ such ...
- 47.4k
1
vote
1
answer
259
views
Find a maximum-weight matching in general graph with constrained cardinality
Let $G=(V,E)$ be a general graph, where edges have weights $w(e)$ and $|V|$ is even.
One of the classic problem is to find a maximum-weight perfect matching (MWPM) of the graph G.
The MWPM problem can ...
- 47.4k
0
votes
1
answer
41
views
What Mathematical Structure can be used for this Optmisation Problem
I'm working with an optimisation problem that I'm unsure how to express in a Mathematical Construct.
Here we have $2n$ known numbers $x_i \in \mathbb{R}^+$ that we need to arrange into $n$ equations ...
- 47.4k
3
votes
3
answers
939
views
Graph with exactly one perfect matching
How do I prove that if $G$ is a graph with $2n$ vertices and has exactly one perfect matching, then $|E(G)| \le n^2$?
- 341
1
vote
1
answer
39
views
Problem in proving that every tree has at most one perfect matching.
I would like to prove that every tree has at most one perfect matching. I approached it in the same way as described here: Perfect matching in a tree. However, I don't understand the concluding ...
- 406