Avancerad

Matchning i grafer

Perfekt matchning, maximala matchningar och bipartita grafer.

matchning perfekt matchning bipartit Halls sats

Föreställ dig att du organiserar en skolbal där du vill para ihop personer för dans. Varje person kan bara dansa med vissa andra (de de känner), och ingen kan dansa med mer än en person samtidigt. Detta är exakt vad matchningsteori handlar om - att hitta optimala parningar i nätverk av relationer. Det används för allt från att matcha studenter med universitet till att tilldela organ för transplantation.

Fördjupning

En matchning i en graf är en mängd kanter där ingen nod är incident till mer än en kant. Maximal matchning har flest möjliga kanter, medan perfekt matchning täcker alla noder. Teori för matchningar i bipartita grafer är särskilt välutvecklad med polynomiella algoritmer, medan allmänna grafer kräver mer sofistikerade tekniker som blossoms och augmenterande vägar.

Grundläggande definitioner

En matchning M i graf G är en mängd kanter så att ingen nod är incident till mer än en kant i M. En nod är matchad om den är incident till en kant i M, annars omatchad. Maximal matchning är en matchning som inte kan utökas. Maximum matchning har största möjliga kardinalitet.

Matchning M: ingen nod incident till >1 kant i M

Typer av matchningar

Perfekt matchning:

· Täcker alla noder i grafen

· Existerar endast om |V| är jämnt

· |M| = |V|/2

Maximum matchning:

· Största möjliga kardinalitet

· Kan men behöver inte vara perfekt

Maximal matchning:

· Kan inte utökas genom att lägga till kanter

· Kan vara mindre än maximum

· Lätt att hitta girig, men inte nödvändigtvis optimal

Matchningar i bipartita grafer

Bipartita grafer har noder uppdelade i två disjunkta mängder med kanter endast mellan mängderna. Matchningsteori för bipartita grafer är välförstått med effektiva algoritmer. Halls äktenskapsats ger nödvändigt och tillräckligt villkor för perfekt matchning.

Halls sats: Perfekt matchning ⟺ |N(S)| \geq |S| för alla S \subseteq A

Halls äktenskapsats

Sats (Hall, 1935): Bipartit graf G = (A ∪ B, E) har matchning som täcker A om och endast om |N(S)| ≥ |S| för alla S ⊆ A.

Interpretation:

· N(S) = grannar till noder i S

· Varje delmängd S av A måste ha minst |S| grannar i B

· Nödvändigt: omatchningsbar S skulle kräva > |N(S)| matchningar

· Tillräckligt: konstruktivt bevis via maximala flöden

Exempel: A = {a₁,a₂,a₃}, B = {b₁,b₂,b₃}

Om N({a₁,a₂}) = {b₁}, då violeras Halls villkor

Ungerska algoritmen

Ungerska algoritmen (Kuhn-Munkres) löser viktad matchning i bipartita grafer - hitta perfekt matchning med minimal/maximal total vikt. Den använder duala variabler och komplementär slakhet för att konstruera optimal lösning stegvis.

Ungerska algoritmen - översikt

Problem: Hitta minimum-vikt perfekt matchning

Algoritm:

1. Initiera duala variabler (vertex potentials)

2. Konstruera equality subgraph

3. Hitta maximal matchning i equality subgraph

4. Om perfekt: klar

5. Annars: uppdatera duala variabler

6. Upprepa från steg 2

Tidskomplexitet: O(n³) för n×n bipartit graf

Tillämpning: Tilldelningsproblem

Problem: Tilldela n arbetare till n jobb för minimal total kostnad

Modellering:

· Bipartit graf: arbetare vs jobb

· Kantvikter = kostnader

· Sök minimum-vikt perfekt matchning

Exempel kostnadmatris:

Job1 Job2 Job3

W1 9 2 7

W2 6 4 3

W3 5 8 1

Optimal tilldelning: W1→Job2, W2→Job3, W3→Job1

Total kostnad: 2 + 3 + 5 = 10

Allmänna grafer och blossoms

För allmänna (icke-bipartita) grafer är matchning mer komplext på grund av udda cykler. Edmonds blossom-algoritm hanterar detta genom att 'kontrahera' udda cykler till enskilda noder. Augmenterande vägar används för att förbättra matchningar iterativt.

Blossom-kontraktion för hantering av udda cykler

Augmenterande vägar

Augmenterande väg:

· Väg från omatchad nod till omatchad nod

· Alternerande matchade/omatchade kanter

· Udda längd (startar och slutar omatchad)

Berth-sats: Matchning M är maximum ⟺ ingen augmenterande väg existerar

Edmonds algoritm:

1. Hitta augmenterande väg (om den finns)

2. Symmetric difference med nuvarande matchning

3. Upprepa tills ingen augmenterande väg finns

Blossom-hantering:

· Udda cykel skapar "blossom"

· Kontrahera blossom till supernod

· Lös rekursivt

· Expandera lösning tillbaka

Vertex covers och Königs sats

Ett vertex cover är en mängd noder som täcker alla kanter. Königs sats säger att i bipartita grafer är storleken av maximum matchning lika med storleken av minimum vertex cover. Detta ger elegant koppling mellan matchnings- och täckningsproblem.

Königs sats: |maximum matching| = |minimum vertex cover| (bipartita grafer)

Bevis av Königs sats (skiss)

Låt ν(G) = storlek av maximum matchning

Låt τ(G) = storlek av minimum vertex cover

≤-riktning: ν(G) ≤ τ(G)

· Vertex cover måste innehålla minst en endpoint från varje matchningskant

· Maximum matchning har ν(G) disjunkta kanter

· Därför behövs minst ν(G) noder i vertex cover

≥-riktning: τ(G) ≤ ν(G)

· Konstruera vertex cover från maximum matchning M

· Använd Halls sats och maximalt flöde

· Min-cut ger vertex cover av storlek |M|

Tillämpningar och algoritmer

Matchningsproblem uppträder i många praktiska sammanhang: online dating, organ transplantation, stabila äktenskap, och nätverksflöden. Olika varianter kräver olika tekniker: viktad vs oviktad, online vs offline, och stabila vs maximala matchningar.

Gale-Shapley algoritm för stabila äktenskap

Problem: Matcha män och kvinnor till stabila par

Stabilitet: Ingen person föredrar någon annan över sin nuvarande partner som också föredrar dem

Algoritm (män föreslår):

1. Varje man föreslår till sin högst rankade kvinna

2. Kvinnor accepterar bästa förslaget, avvisar andra

3. Avvisade män föreslår till nästa på sin lista

4. Upprepa tills alla är matchade

Egenskaper:

· Alltid terminerar med stabil matchning

· Man-optimal (bästa möjliga för männen)

· Kvinna-pessimal (sämsta stabila för kvinnorna)

Online matching problem

Problem: Noder anländer online och måste matchas omedelbart

Ranking algoritm (Karp et al.):

· Rankar alla möjliga partners i förväg

· Matchar anländande nod med högst rankade tillgängliga

Prestanda:

· Worst-case competitive ratio: 1 - 1/e ≈ 0.632

· Optimal för randomiserade online algoritmer

Tillämpningar:

· AdWords auktioner

· Ride-sharing matchning

· Kidney exchange

Vanliga misstag

❌ Förväxla maximal med maximum matchning

Maximal = kan inte utökas, maximum = största möjliga storlek

Exempel: En maximal matchning kan vara mycket mindre än maximum

❌ Applicera Halls sats på allmänna grafer

Halls sats gäller endast för bipartita grafer

Exempel: Udda cykler i allmänna grafer kräver blossom-algoritm

❌ Glömma stabilitetskrav i stabila matchningar

Maximum matchning behöver inte vara stabil

Exempel: Kan finnas större matchning som inte är stabil

Tillämpningar

Ekonomi och arbetsmarknad

Matcha arbetssökande med arbetsgivare, studenter med universitet

Exempel: Medicinstudenters specialistplacering, college admissions

Hälsovård

Organtransplantation och patientbehandling

Exempel: Kidney exchange programs, läkare-patient tilldelning

Teknik och nätverk

Resursallokering och nätverksoptimering

Exempel: Cloud computing, ad allocation, ridesharing

Övningar

1 Medel

Verifiera Halls villkor för bipartit graf med A={a,b,c}, B={1,2,3} och kanter {(a,1), (a,2), (b,2), (c,3)}.

Tips

Kontrollera |N(S)| ≥ |S| för alla delmängder S av A

Visa facit

N({a}) = {1,2}, |N({a})| = 2 ≥ 1 ✓
N({b}) = {2}, |N({b})| = 1 ≥ 1 ✓
N({c}) = {3}, |N({c})| = 1 ≥ 1 ✓
N({a,b}) = {1,2}, |N({a,b})| = 2 ≥ 2 ✓
N({a,c}) = {1,2,3}, |N({a,c})| = 3 ≥ 2 ✓
N({b,c}) = {2,3}, |N({b,c})| = 2 ≥ 2 ✓
N({a,b,c}) = {1,2,3}, |N({a,b,c})| = 3 ≥ 3 ✓

Svar: Halls villkor uppfyllt, perfekt matchning existerar

2 Medel

Hitta maximum matchning i graf med noder {1,2,3,4,5,6} och kanter {(1,2), (2,3), (3,4), (4,5), (5,6), (6,1), (1,4)}.

Tips

Rita grafen och hitta augmenterande vägar

Visa facit

Svar: Maximum matchning har storlek 3

Exempel: En möjlig maximum matchning: {(1,2), (3,4), (5,6)} eller {(1,6), (2,3), (4,5)}

3 Svår

Lös tilldelningsproblemet med kostnadmatris [[3,1,4], [2,0,5], [1,6,2]] med ungerska algoritmen.

Tips

Subtrahera minsta element från varje rad och kolumn iterativt

Visa facit

Svar: Optimal tilldelning: (1,2), (2,3), (3,1) med total kostnad 6

Förklaring: Efter rad- och kolumnreduktion hittas assignment med noll-kostnader i reducerad matris

Sammanfattning

Matchning i grafer handlar om att para ihop noder utan överlapp. Bipartita grafer har effektiva algoritmer genom Halls sats och ungerska metoden. Allmänna grafer kräver blossom-algoritm för hantering av udda cykler. Königs sats kopplar matchning till vertex covers. Tillämpningar spänner från ekonomi till hälsovård och teknik. Stabila matchningar och online-varianter lägger till ytterligare komplexitet och realism.