Matchning
En matchning är inom matematik, specifikt grafteori, en mängd av bågar (kanter) i en graf sådan att inget par av bågar har någon gemensam nod. Motsvarande begrepp med noder istället för bågar kallas för oberoende mängd.
Definitioner
[redigera | redigera wikitext]
Givet en graf är en matchning M en delmängd av bågmängden B, sådan att ingen av noderna i N tillhör fler än en båge i M. En matchnings storlek är antalet bågar i matchningen.
En nod är matchad om den ligger i en båge i matchningen, annars är den omatchad.
En maximal matchning är en matchning som inte är en matchning om man lägger till fler bågar. Annorlunda uttryckt är en matchning maximal om den inte är en äkta delmängd av någon annan matchning.
En största matchning av en graf G är en matchning som innehåller flest bågar för matchningar i G, dvs det finns ingen matchning i G som innehåller fler bågar. En graf G:s matchningstal, ofta betecknat , är storleken för en största matchning i grafen. Varje största matchning är maximal, men det omvända gäller inte.
En perfekt matchning är en matchning som matchar alla noder i grafen. En perfekt matchning är en största matchning, omvändningen är falsk. Alla perfekta matchningar är också en bågövertäckning med minimal storlek.
En nästan perfekt matchning är en matchning där exakt en nod är omatchad, något som endast kan inträffa i grafer med ett udda antal av noder.
En alternerande väg med avseende på en matchning M i en graf är en väg där varannan båge tillhör matchningen och de andra inte tillhör matchningen. En utökande väg är en alternerande väg som startar och slutar i omatchade noder. En matchning är maximal om och endast om den inte har någon utökande väg.
Resultat
[redigera | redigera wikitext]Königs sats säger att i bipartita grafer har en största matchning samma storlek som en minsta nodövertäckning.
Tuttes sats karakteriserar grafer med perfekta matchningar. Edmonds matchningsalgoritm hittar en största matchning i en graf på polynomiell tid.
Referenser
[redigera | redigera wikitext]- Diestel, Reinhard (2005). Graph Theory. Springer Verlag. ISBN 3-540-26182-6