Hitta maximal matchning med hjälp av utökande vägar i en graf
Jag behöver hjälp med att förstå hur man hittar en maximal matchning i en graf. Det jag förstår är att man börjar välja vilken kant som helts, som tex 2-c. Dock förstår jag inte hur jag tänker sen. Jag vet svaret på frågan som är {{1,a},{2,c},{3,b},{4,d},{5,e}}. Dock vill jag förstå hur man själv löser detta.
Idealt så vill man ju kanske använda en 'optimal algoritm' i något avseende men en i mina ögon ganska uppenbar "snål algoritm" förefaller vara:
Låt säga att du börjar med att makera en kant säg 2c. När du väl gjort detta så faller övriga kanter i grafen i n i två kategorier.
A) Kanter som delar hörn med 2c
B) Kanter som inte delar hörn med 2c
Om du vill uttöka matchingen med fler kanter så kan du markera vilken som helst av kanterna i kategori B). Säg 4d. Därefter befinner du dig i en ny situation där övriga kanter kan delas in i två nya kategorier
A') Kanter som delar hörn med 2c eller 4d
B') Kanter som inte delar hörn med 2c eller 4d
Man kan fortsätta att upprepa detta med att markera kanter som inte delar hörn med kanter man redan markerat fram tills dess att det inte finns några fler att markera och då man har en maximal matchning eftersom definitionen ju ska vara att man inte kan addera fler kanter till mängden.
Om en graf har flera maximala matchingar så garanterar inte denna process att man hittar en specifik matching såsom den med minst eller flest kanter men man kan i så fall upprepa processen med några olika start-kanter och producera några olika matchingar, mest primitivast genom att implementera ett sökträd.
