Ggthjy

How were pictures turned from film to a big picture in a picture frame before digital scanning?

Flight departed from the gate 5 min before scheduled departure time. Refund options

Does the Black Tentacles spell do damage twice at the start of turn to an already restrained creature?

What would you call this weird metallic apparatus that allows you to lift people?

Universal covering space of the real projective line?

How does Belgium enforce obligatory attendance in elections?

As a dual citizen, my US passport will expire one day after traveling to the US. Will this work?

What is the difference between CTSS and ITS?

Project Euler #1 in C++

Positioning dot before text in math mode

Does any scripture mention that forms of God or Goddess are symbolic?

Can an iPhone 7 be made to function as a NFC Tag?

What does it mean that physics no longer uses mechanical models to describe phenomena?

How does light 'choose' between wave and particle behaviour?

How many time has Arya actually used Needle?

Is multiple magic items in one inherently imbalanced?

Do I really need to have a message in a novel to appeal to readers?

Why are vacuum tubes still used in amateur radios?

Is openssl rand command cryptographically secure?

Tips to organize LaTeX presentations for a semester

Did any compiler fully use 80-bit floating point?

What is the difference between a "ranged attack" and a "ranged weapon attack"?

What does Turing mean by this statement?

retrieve food groups from food item list

What is a fractional matching?

4

1

$begingroup$

For the maximum matching problem, we can find the fractional matching which I understand involves some sort of weighting for the edges. However, I cannot seem to find an exact and simple explanation of what a fractional matching is. How does it compare to an integral matching?

If this question seems too basic, could I please have a link to somewhere that explains it?

graphs matching

share|cite|improve this question

asked 2 days ago

monadoboimonadoboi

1587

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  "involves some sort of weighting for the edges" It quite literally is a weighting for the edges, with suitable constraints. Could you explain what it is you do not understand about that? Otherwise, I'm not quite sure what you're asking.
  $endgroup$
  – Discrete lizard♦
  2 days ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Can you give a reference or the full problem where you encoutered the "fractional matching" notion ?
  $endgroup$
  – Vince
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I suppose I'm looking for a clear definition of fractional matching. What exactly constitutes a matching that is fractional? With a normal matching, it's a set of edges that have no common vertices. How does that differ in a fractional matching? Sorry if it's unclear.
  $endgroup$
  – monadoboi
  2 days ago
  

  
  
  
  

add a comment | 

4

1

$begingroup$

For the maximum matching problem, we can find the fractional matching which I understand involves some sort of weighting for the edges. However, I cannot seem to find an exact and simple explanation of what a fractional matching is. How does it compare to an integral matching?

If this question seems too basic, could I please have a link to somewhere that explains it?

graphs matching

share|cite|improve this question

asked 2 days ago

monadoboimonadoboi

1587

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  "involves some sort of weighting for the edges" It quite literally is a weighting for the edges, with suitable constraints. Could you explain what it is you do not understand about that? Otherwise, I'm not quite sure what you're asking.
  $endgroup$
  – Discrete lizard♦
  2 days ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Can you give a reference or the full problem where you encoutered the "fractional matching" notion ?
  $endgroup$
  – Vince
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I suppose I'm looking for a clear definition of fractional matching. What exactly constitutes a matching that is fractional? With a normal matching, it's a set of edges that have no common vertices. How does that differ in a fractional matching? Sorry if it's unclear.
  $endgroup$
  – monadoboi
  2 days ago
  

  
  
  
  

add a comment | 

$begingroup$

For the maximum matching problem, we can find the fractional matching which I understand involves some sort of weighting for the edges. However, I cannot seem to find an exact and simple explanation of what a fractional matching is. How does it compare to an integral matching?

If this question seems too basic, could I please have a link to somewhere that explains it?

graphs matching

share|cite|improve this question

asked 2 days ago

monadoboimonadoboi

1587

$endgroup$

share|cite|improve this question

asked 2 days ago

monadoboimonadoboi

1587

share|cite|improve this question

asked 2 days ago

monadoboimonadoboi

1587

asked 2 days ago

monadoboimonadoboi

1587

asked 2 days ago

monadoboimonadoboi

1587

3 Answers
3

active

oldest

votes

7

$begingroup$

Given a graph $G=(V,E)$, we can represent a matching as a function $f$ from the edges $E$ to ${0,1}$ such that for each vertex $vin V$, we have $sum_{win N(v)} f(v,w) leq1$, where $N(v)$ is the neighbourhood of $v$, i.e. the set of its adjacent vertices. (We have equality for a perfect matching) In this representation, $f(e)=1$ means the edge $e$ is part of the matching.

A fractional matching can then be represented by a function $f'$ from the edges $E$ to the continuous interval $[0,1]$, with the same constraint, i.e. $sum_{win N(v)} f'(v,w) leq1$. So, intuitively, each vertex is 'divided' over its incident edges such that it is participating in at most one edge 'in total'.

share|cite|improve this answer

edited 2 days ago

David Richerby

70.7k16107198

answered 2 days ago

Discrete lizard♦Discrete lizard

4,58811538

$endgroup$

add a comment | 

5

$begingroup$

To add to Discrete lizard's answer, I would recommend you look into mathematical programming and optimization. The matching problem can be modelled as what is called an integer program (in fact the constraints that $sum_{win N(v)} f(v,w) leq1$ for all $v in V$ are the constraints that define the matching problem where for each $e in E$, $f(e)$ is a variable. Furthermore, an integer program demands that the variables be integers. But you can see a natural relaxation of the integer program into a linear program by allowing your variables to take non-integer values. Solutions to this relaxed optimization problem are what we call fractional matchings.

A lot of problems on graphs can be modelled as integer programs, and relaxing them to linear programs is a common technique, so it might be worth looking into.

share|cite|improve this answer

answered 2 days ago

NaturalLogZNaturalLogZ

513

New contributor

NaturalLogZ is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Indeed, integer programming (IP) is related, but I'd like to add a few remarks. First, solving IPs in general is an NP-hard problem, while a maximum cardinality matching can be found in polynomial time with the Hungarian algorithm. The IP formulation still has its uses, however, in case there are additional constraints that can nicely be encoded in an IP. Second, if (and only if) our graph is bipartite, the matrix describing the IP is totally unimodular, which means that the IP has the same solution as the relaxed LP and in particular that therefore there are no optimal fractional matchings.
  $endgroup$
  – Discrete lizard♦
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Welcome to the site!
  $endgroup$
  – David Richerby
  2 days ago
  

  
  
  
  

add a comment | 

2

$begingroup$

The formal definitions are very nice, but here's a simplier more intuitive explanation. In a fractional matching, every edge has a number. The sum all all the edge numbers connected to any vertex must be less than 1.

share|cite|improve this answer

answered yesterday

KeatingeKeatinge

1415

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f107149%2fwhat-is-a-fractional-matching%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

7

$begingroup$

Given a graph $G=(V,E)$, we can represent a matching as a function $f$ from the edges $E$ to ${0,1}$ such that for each vertex $vin V$, we have $sum_{win N(v)} f(v,w) leq1$, where $N(v)$ is the neighbourhood of $v$, i.e. the set of its adjacent vertices. (We have equality for a perfect matching) In this representation, $f(e)=1$ means the edge $e$ is part of the matching.

A fractional matching can then be represented by a function $f'$ from the edges $E$ to the continuous interval $[0,1]$, with the same constraint, i.e. $sum_{win N(v)} f'(v,w) leq1$. So, intuitively, each vertex is 'divided' over its incident edges such that it is participating in at most one edge 'in total'.

share|cite|improve this answer

edited 2 days ago

David Richerby

70.7k16107198

answered 2 days ago

Discrete lizard♦Discrete lizard

4,58811538

$endgroup$

add a comment | 

7

$begingroup$

Given a graph $G=(V,E)$, we can represent a matching as a function $f$ from the edges $E$ to ${0,1}$ such that for each vertex $vin V$, we have $sum_{win N(v)} f(v,w) leq1$, where $N(v)$ is the neighbourhood of $v$, i.e. the set of its adjacent vertices. (We have equality for a perfect matching) In this representation, $f(e)=1$ means the edge $e$ is part of the matching.

A fractional matching can then be represented by a function $f'$ from the edges $E$ to the continuous interval $[0,1]$, with the same constraint, i.e. $sum_{win N(v)} f'(v,w) leq1$. So, intuitively, each vertex is 'divided' over its incident edges such that it is participating in at most one edge 'in total'.

share|cite|improve this answer

edited 2 days ago

David Richerby

70.7k16107198

answered 2 days ago

Discrete lizard♦Discrete lizard

4,58811538

$endgroup$

add a comment | 

$begingroup$

Given a graph $G=(V,E)$, we can represent a matching as a function $f$ from the edges $E$ to ${0,1}$ such that for each vertex $vin V$, we have $sum_{win N(v)} f(v,w) leq1$, where $N(v)$ is the neighbourhood of $v$, i.e. the set of its adjacent vertices. (We have equality for a perfect matching) In this representation, $f(e)=1$ means the edge $e$ is part of the matching.

A fractional matching can then be represented by a function $f'$ from the edges $E$ to the continuous interval $[0,1]$, with the same constraint, i.e. $sum_{win N(v)} f'(v,w) leq1$. So, intuitively, each vertex is 'divided' over its incident edges such that it is participating in at most one edge 'in total'.

share|cite|improve this answer

edited 2 days ago

David Richerby

70.7k16107198

answered 2 days ago

Discrete lizard♦Discrete lizard

4,58811538

$endgroup$

share|cite|improve this answer

edited 2 days ago

David Richerby

70.7k16107198

answered 2 days ago

Discrete lizard♦Discrete lizard

4,58811538

edited 2 days ago

David Richerby

70.7k16107198

edited 2 days ago

David Richerby

70.7k16107198

answered 2 days ago

Discrete lizard♦Discrete lizard

4,58811538

answered 2 days ago

Discrete lizard♦Discrete lizard

4,58811538

5

$begingroup$

To add to Discrete lizard's answer, I would recommend you look into mathematical programming and optimization. The matching problem can be modelled as what is called an integer program (in fact the constraints that $sum_{win N(v)} f(v,w) leq1$ for all $v in V$ are the constraints that define the matching problem where for each $e in E$, $f(e)$ is a variable. Furthermore, an integer program demands that the variables be integers. But you can see a natural relaxation of the integer program into a linear program by allowing your variables to take non-integer values. Solutions to this relaxed optimization problem are what we call fractional matchings.

A lot of problems on graphs can be modelled as integer programs, and relaxing them to linear programs is a common technique, so it might be worth looking into.

share|cite|improve this answer

answered 2 days ago

NaturalLogZNaturalLogZ

513

New contributor

NaturalLogZ is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Indeed, integer programming (IP) is related, but I'd like to add a few remarks. First, solving IPs in general is an NP-hard problem, while a maximum cardinality matching can be found in polynomial time with the Hungarian algorithm. The IP formulation still has its uses, however, in case there are additional constraints that can nicely be encoded in an IP. Second, if (and only if) our graph is bipartite, the matrix describing the IP is totally unimodular, which means that the IP has the same solution as the relaxed LP and in particular that therefore there are no optimal fractional matchings.
  $endgroup$
  – Discrete lizard♦
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Welcome to the site!
  $endgroup$
  – David Richerby
  2 days ago
  

  
  
  
  

add a comment | 

5

$begingroup$

To add to Discrete lizard's answer, I would recommend you look into mathematical programming and optimization. The matching problem can be modelled as what is called an integer program (in fact the constraints that $sum_{win N(v)} f(v,w) leq1$ for all $v in V$ are the constraints that define the matching problem where for each $e in E$, $f(e)$ is a variable. Furthermore, an integer program demands that the variables be integers. But you can see a natural relaxation of the integer program into a linear program by allowing your variables to take non-integer values. Solutions to this relaxed optimization problem are what we call fractional matchings.

A lot of problems on graphs can be modelled as integer programs, and relaxing them to linear programs is a common technique, so it might be worth looking into.

share|cite|improve this answer

answered 2 days ago

NaturalLogZNaturalLogZ

513

New contributor

NaturalLogZ is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Indeed, integer programming (IP) is related, but I'd like to add a few remarks. First, solving IPs in general is an NP-hard problem, while a maximum cardinality matching can be found in polynomial time with the Hungarian algorithm. The IP formulation still has its uses, however, in case there are additional constraints that can nicely be encoded in an IP. Second, if (and only if) our graph is bipartite, the matrix describing the IP is totally unimodular, which means that the IP has the same solution as the relaxed LP and in particular that therefore there are no optimal fractional matchings.
  $endgroup$
  – Discrete lizard♦
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Welcome to the site!
  $endgroup$
  – David Richerby
  2 days ago
  

  
  
  
  

add a comment | 

$begingroup$

To add to Discrete lizard's answer, I would recommend you look into mathematical programming and optimization. The matching problem can be modelled as what is called an integer program (in fact the constraints that $sum_{win N(v)} f(v,w) leq1$ for all $v in V$ are the constraints that define the matching problem where for each $e in E$, $f(e)$ is a variable. Furthermore, an integer program demands that the variables be integers. But you can see a natural relaxation of the integer program into a linear program by allowing your variables to take non-integer values. Solutions to this relaxed optimization problem are what we call fractional matchings.

A lot of problems on graphs can be modelled as integer programs, and relaxing them to linear programs is a common technique, so it might be worth looking into.

share|cite|improve this answer

answered 2 days ago

NaturalLogZNaturalLogZ

513

New contributor

NaturalLogZ is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this answer

answered 2 days ago

NaturalLogZNaturalLogZ

513

New contributor

NaturalLogZ is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 2 days ago

NaturalLogZNaturalLogZ

513

New contributor

NaturalLogZ is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 2 days ago

NaturalLogZNaturalLogZ

513

2

$begingroup$

The formal definitions are very nice, but here's a simplier more intuitive explanation. In a fractional matching, every edge has a number. The sum all all the edge numbers connected to any vertex must be less than 1.

share|cite|improve this answer

answered yesterday

KeatingeKeatinge

1415

$endgroup$

add a comment | 

2

$begingroup$

The formal definitions are very nice, but here's a simplier more intuitive explanation. In a fractional matching, every edge has a number. The sum all all the edge numbers connected to any vertex must be less than 1.

share|cite|improve this answer

answered yesterday

KeatingeKeatinge

1415

$endgroup$

add a comment | 

$begingroup$

The formal definitions are very nice, but here's a simplier more intuitive explanation. In a fractional matching, every edge has a number. The sum all all the edge numbers connected to any vertex must be less than 1.

share|cite|improve this answer

answered yesterday

KeatingeKeatinge

1415

$endgroup$

share|cite|improve this answer

answered yesterday

KeatingeKeatinge

1415

answered yesterday

KeatingeKeatinge

1415

answered yesterday

KeatingeKeatinge

1415