Prirejanja in pokritja

  • Naj bo neusmerjen graf.
  • Množici pravimo prirejanje (angl. matching), če nobeni dve povezavi iz nimata skupnega krajišča (tj., ).
    • Prirejanje je popolno prirejanje, če je vsako vozlišče grafa krajišče povezave iz (tj., ).
  • Množici pravimo pokritje (angl. vertex cover), če ima vsaka povezava iz krajišče v (tj., ).

Primeri prirejanj

  • Prirejanje:

  • Ni prirejanje:

  • Popolno prirejanje:

  • Trditev. Če ima popolno prirejanje, je soda.

Primeri pokritij

  • Pokritje:

  • Ni pokritje:

  • (Najmanjše) pokritje:

  • Iščemo čim večje prirejanje in čim manjše pokritje.

    • ... velikost največjega prirejanja v
    • ... velikost najmanjšega pokritja v

Primera

  • , :

  • :

Velikosti prirejanj in pokritij

  • Trditev. Naj bo prirejanje in pokritje v grafu . Potem velja .

  • Posledica. Če velja , potem je največje prirejanje in najmanjše pokritje v .

  • Posledica. Za vsak graf velja .

  • Opomba. Lahko se zgodi, da velja . Za dvodelne grafe velja (dokaz kasneje).

  • Dokaz. Ker ima vsaka povezava iz vsaj eno krajišče v , obstaja preslikava , za katero velja . Ker je vsako vozlišče iz krajišče največ ene povezave iz , je preslikava injektivna, od koder sledi .

Terminologija

Definicija. Naj bo prirejanje v grafu . Rečemo, da je

  • vozlišče
    • prosto, če , in
    • vezano, če ;
  • povezava
    • prosta, če , in
    • vezana, če ; ter
  • pot v
    • izmenična (alternirajoča), če se v njej izmenjujejo proste in vezane povezave, in
    • povečujoča, če je izmenična ter se začne in konča s prostim vozliščem.

Povečujoče poti

Če na povečujoči poti zamenjamo proste in vezane povezave, se prirejanje poveča:

Bergeev izrek

  • Definicija. Simetrična vsota množic in je

  • Trditev. Če je prirejanje v in povečujoča pot z množico povezav , je prirejanje v in .

  • Trditev (Berge). Naj bo prirejanje v grafu . Potem je največje prirejanje v natanko tedaj, ko zanj ne obstaja povečujoča pot.

Dokaz

Dokazujemo enakovredno izjavo: ni največje prirejanje v natanko tedaj, ko zanj obstaja povečujoča pot.

  • Sledi iz prejšnje trditve.
  • Denimo, da ni največje prirejanje v .
    • Potem obstaja prirejanje v , za katerega velja .
    • Potem je graf z maksimalno stopnjo - njegove povezane komponente so poti in sodi cikli.



Dokaz (2)

  • Ker je , obstaja v pot , katere prva in zadnja povezava sta v .
  • Trdimo, da je povečujoča pot za :
    • je alternirajoča, saj in zato ;
    • začne in konča se s prostim vozliščem:
      • denimo, da je krajišče poti in ni prosto za ;
      • potem obstaja povezava , kar je v protislovju s predpostavko, da je prirejanje.

Madžarska metoda

  • Iskanje največjega prirejanja se torej prevede na iskanje povečujočih poti.

  • Če je graf dvodelen (, , ; ekvivalentno, v ni lihih ciklov), povečujočo pot poiščemo z madžarsko metodo.

    • Naj bo dvodelen graf in prirejanje v . Postavimo množico prostih vozlišč v kot množico in .
    • Ponavljamo:
    • Če je v v nekem trenutku prosto vozlišče, smo našli povečujočo pot.
      • Postopek ustavimo in povečamo prirejanje (in začnemo od začetka).
    • Sicer sta v nekem trenutku nova in enaka starima.

Največje prirejanje in najmanjše pokritje

  • Izrek. Če sta nova in enaka starima, potem je največje prirejanje, je najmanjše pokritje, in .

  • Dokaz. Trdimo:

    • med in ni prostih povezav (sicer bi lahko povečali )
    • med in ni vezanih povezav (do vodijo vezane povezave samo iz )
    • med in ni vezanih povezav (sicer bi lahko povečali )

Nadaljevanje dokaza

  • Množica je torej pokritje.

  • Definirajmo še množico vezanih povezav med in ter množico vezanih povezav med in .

  • Potem je ter velja (sicer je v prosto vozlišče) in (vsa prosta vozlišča iz so v ).

  • Velja torej

  • je torej največje prirejanje, pa najmanjše pokritje.

Primer

  • Imamo prosto vozlišče v , torej smo našli povečujočo pot.

  • Ni več prostih vozlišč v , torej imamo največje prirejanje in najmanjše pokritje .

Kőnig-Egerváryjev izrek

  • V posebnem (za dvodelne grafe) velja torej Kőnig-Egerváryjev izrek.

    • Za dvodelen graf velja .

  • Opomba. Obstaja tudi algoritem za iskanje povečujoče poti v splošnem grafu: Edmondsov algoritem (angl. tudi blossom algorithm).

    • Ta algoritem je "učinkovit", torej polinomski.
    dvodelni grafi splošni grafi
    največje prirejanje lahek (MM) lahek (Edmonds)
    najmanjše pokritje lahek (MM) težek

Hallov izrek

  • Naj bo dvodelen graf.
  • Potem obstaja popolno prirejanje iz v (tj., prirejanje, ki pokrije ) natanko tedaj, ko velja , kjer je soseščina (angl. neighbourhood) množice .

Dokaz

  • () Naj bo popolno prirejanje iz v .
  • Obstaja injektivna preslikava , .

Dokaz (2)

  • () Uporabimo madžarsko metodo, da dobimo največje prirejanje in najmanjše pokritje .
  • Velja , torej .

  • Nadalje velja

  • Ker velja , sledi , torej smo našli popolno prirejanje iz v .

Opomba

  • Hallov izrek je oblike .

    • Če želimo dokazati, da obstaja popolno prirejanje iz v , ga poiščemo.
    • Če želimo dokazati, da ne obstaja popolno prirejanje iz v , poiščemo , da velja .

  • Taka karakterizacija recimo ni znana za hamiltonskost grafa (obstoj Hamiltonovega cikla).

Minimalna in maksimalna popolna prirejanja

  • Imamo poln dvodelen graf , kjer je , in , ter uteži (cene) na povezavah (), ki jih zapišemo v matriko .

  • Tak graf ima popolnih prirejanj.

    • Iščemo popolno prirejanje z minimalno (maksimalno) ceno, kjer je cena prirejanja enaka .

  • Primeri.

    • Problem štafete;
    • druge razporeditve opravil ( ljudi, opravil, vsak dobi natanko eno opravilo).

Opazka

  • Če v matriki odštejemo konstanto od vseh elementov v eni vrstici ali enem stolpcu, se optimalna rešitev ne spremeni, saj ima vsako popolno prirejanje natanko eno povezavo s krajiščem v vozlišču, ki ustreza izbrani vrstici ali stolpcu.

  • Cena vsakega popolnega prirejanja se tedaj zmanjša za .

  • Primer. Zmanjšajmo za najmanjšo vrednost v vsaki vrstici, nato pa še v vsakem stolpcu:

Madžarska metoda z utežmi (MMU)

Iščemo minimalno popolno prirejanje.

  • 1. Od vsake vrstice odštejemo njen minimum. Od vsakega stolpca odštejemo njegov minimum. Dobimo nenegativno matriko z vsaj eno ničlo v vsaki vrstici in vsakem stolpcu.
  • 2. Poiščemo ničel, v vsaki vrstici in vsakem stolpcu eno. Če jih najdemo, nam dajo minimalno popolno prirejanje.
  • 3. Sicer lahko vse ničle v matriki pokrijemo z manj kot vrsticami in stolpci. Naj bo minimum nepokritih števil. Od nepokritih števil odštejemo , dvakrat pokritim številom pa prištejemo . Vrnemo se na 2. korak.

Primer - štafeta

prsno hrbtno delfin prosto počiva počiva
1 65 73 63 57 0 0
2 67 76 65 58 0 0
3 68 72 69 55 0 0
4 67 75 70 59 0 0
5 71 69 75 57 0 0
6 69 71 66 59 0 0

Primer - štafeta (2)

Minimum v vsaki vrstici je - odštejmo še minimume stolpcev:

prsno hrbtno delfin prosto počiva počiva
1 0 4 0 2 0 0
2 2 7 2 3 0 0
3 3 3 6 0 0 0
4 2 6 7 4 0 0
5 6 0 12 2 0 0
6 4 2 3 4 0 0

Primer - štafeta (3)

  • Vse ničle smo pokrili s tremi vrsticami in dvema stolpcema (skupaj manj kot ).

  • Najmanjša nepokrita vrednost je - zmanjšamo nepokrita in povečamo dvakrat pokrita števila za :

    prsno hrbtno delfin prosto počiva počiva
    1 0 4 0 2 2 2
    2 0 5 0 1 0 0
    3 3 3 6 0 2 2
    4 0 4 5 2 0 0
    5 6 0 12 2 2 2
    6 2 0 1 2 0 0

Primer - štafeta (4)

Dobimo optimalno rešitev:

prsno hrbtno delfin prosto počiva počiva
1 65 73 63 57 0 0
2 67 76 65 58 0 0
3 68 72 69 55 0 0
4 67 75 70 59 0 0
5 71 69 75 57 0 0
6 69 71 66 59 0 0
  • Cena optimalne rešitve: 65 + 69 + 65 + 55 + 0 + 0 = 254.

Ničelni graf

  • Kaj pravzaprav naredimo v 2. in 3. koraku?
  • Naj bo dvodelen graf, kjer je (ničelni graf).

  • Na poiščemo največje prirejanje in najmanjše pokritje z madžarsko metodo.

  • Če je popolno prirejanje (), nam to da ničel, eno v vsaki vrstici in stolpcu.

  • Če je , nam vozlišča iz dajo manj kot vrstic in stolpcev, ki pokrijejo vse ničle.

    • Vrsticam v (torej v ) prištejemo , stolpcem izven (torej v ) odštejemo .
    • Res torej od nepokritih števil odštejemo , dvakrat pokritim pa prištejemo .

Končnost MMU

  • Zakaj se madžarska metoda z utežmi vedno ustavi?

    →

  • V tretjem koraku se znebimo povezav med in (dvakrat pokrita števila) in pridelamo vsaj eno povezavo med in (med nepokritimi števili je bil , ki smo ga zmanjšali na ) - naj bo to povezava (, ).

Končnost MMU (2)

  • Imamo dve možnosti:

    • je prosto vozlišče: našli smo povečujočo pot, prirejanje se poveča;
    • je vezano vozlišče: poveča se množica .

  • Množica se lahko poveča največ -krat, preden se poveča prirejanje.

  • Prirejanje se poveča največ -krat.

  • Madžarska metoda z utežmi ima torej največ korakov.

  • Ker pri tem opravi približno operacij za izvedbo madžarske metode, za madžarsko metodo z utežmi potrebujemo operacij.

Opombi

  • Opomba. Če iščemo maksimalno popolno prirejanje, poiščemo minimalno popolno prirejanje za .

  • Opomba. Iščemo po vseh permutacijah ( permutacij).

    • Če se omejimo samo na ciklične permutacije (tj., oblike - permutacij), je to problem potujočega trgovca - zanj ne poznamo učinkovitega algoritma.