5. Párosítás fogalma
Párosítás fogalma. Független élhalmaz, lefogó élhalmaz, független ponthalmaz, lefogó ponthalmaz, illetve ν(G), ϱ(G), α(G) és τ (G) fogalmai, ezek egymással való kapcsolatai. Gallai tétele.
Párosítások és független élhalmazok
- A $G$ gráfban az $M \subseteq E(G)$ élhalmazt párosításnak vagy független élhalmaznak nevezzük, ha ($M$ nem tartalmaz hurokélt és) $M$ semelyik két élének nincs közös végpontja.
- $M$ maximális párosítás, ha $G$-nek nincs $|M|$-nél nagyobb méretű párosítása.
- A $G$-béli maximális párosítások méretét $\nu(G)$ jelöli.
- Az $M$ független élhalmaz teljes párosítás, ha $G$ minden csúcsára illeszkedik $M$-béli él.
Párosítások vizuális típusai
Nincs közös végpont.
Minden csúcs lefedett.
Példafeladat: Független élek maximális száma
7.2. Feladat
Határozzuk meg az alábbi $G$ gráfban a független élek maximális számát, $\nu(G)$-t!
Megoldás levezetése
$G$-ben könnyű négy élű párosítást találni. Egy lehetséges választás a 7.3. ábrán látható $M = \{\{a,b\}, \{f,g\}, \{d,j\}, \{i,e\}\}$ élhalmaz.
Miért nincs 5 élű párosítás?
Tekintsük a kékkel jelölt $X = \{b, d, g, i\}$ csúcshalmazt. Ez a halmaz lefogja a gráf összes élét (minden élnek legalább az egyik végpontja $X$-ben van).
Mivel $|X| = 4$, egy tetszőleges párosítás minden élének tartalmaznia kell legalább egy végpontot $X$-ből. Ha lenne 5 független élünk, a skatulya-elv alapján $X$ valamelyik csúcsára legalább két él illeszkedne, ami ellentmond a párosítás definíciójának.
7.3. ábra: 4-es párosítás és lefogó halmaz
Lefogó ponthalmazok
- A $G$ gráf csúcsainak egy $X \subseteq V(G)$ halmazát lefogó ponthalmaznak nevezzük, ha $G$ minden élének legalább az egyik végpontja $X$-beli.
- $X$ minimális lefogó ponthalmaz, ha $G$-ben nincs $|X|$-nél kisebb lefogó ponthalmaz.
- A $G$-béli minimális lefogó ponthalmazok méretét $\tau(G)$ jelöli.
Hogyan „fogunk le” egy élet?
Egy csúcshalmaz akkor „fogja le” a gráfot, ha nincs olyan él, amelynek mindkét végpontja kívül esne a halmazon. A lenti ábrán látható, hogy a kijelölt csúcsok az összes élet érintik.
Párosítás és lefogó ponthalmaz kapcsolata
Minden $G$ gráfra $\nu(G) \leq \tau(G)$ teljesül.
Bizonyítás levezetése
Legyen $G$-ben $M$ egy maximális párosítás és $X$ egy minimális lefogó ponthalmaz; ekkor tehát $|M| = \nu(G)$ és $|X| = \tau(G)$.
$X$ minden élnek legalább az egyik végpontját tartalmazza, így ez nyilván $M$ éleire is teljesül.
Azonban ugyanaz az $X$-beli csúcs nem illeszkedhet két $M$-beli élre is, mert $M$ párosítás (független élhalmaz).
Más szóval: minden $M$-beli élre legalább egy különböző $X$-beli csúcsnak kell illeszkednie. Ebből tehát $|M| \leq |X|$ és így $\nu(G) \leq \tau(G)$ valóban következik.
Kidolgozott példa: $\nu(G)$ és $\tau(G)$ meghatározása
A feladat szövege
Határozzuk meg egy adott $G$ gráfban a lefogó pontok minimális számát, azaz $\tau(G)$ értékét!
Megoldás levezetése
1. Tegyük fel, hogy találtunk a gráfban egy négy élű párosítást. Ebből a definíció alapján következik, hogy a maximális párosítás mérete legalább 4: $\nu(G) \geq 4$.
2. Tegyük fel továbbá, hogy sikerült mutatni egy négy pontú lefogó ponthalmazt is. Ebből adódik, hogy a minimális lefogó pontszám legfeljebb 4: $\tau(G) \leq 4$.
Az 5.3-as állítást ($\nu(G) \leq \tau(G)$) felhasználva:
Ebből adódik a végeredmény: $\nu(G) = \tau(G) = 4$.
Független ponthalmaz
Definíció A $G$ gráf csúcsainak egy $Y \subseteq V(G)$ halmazát független ponthalmaznak nevezzük, ha $Y$-nak semelyik két eleme nem szomszédos $G$-ben (és $Y$-beli csúcsra hurokél sem illeszkedik).
Függetlenségi szám
A $G$-beli független ponthalmazok közül a maximálisaknak a méretét $\alpha(G)$ jelöli.
Lefogó élhalmaz
Definíció Az izolált pontot nem tartalmazó $G$ gráf éleinek egy $Z \subseteq E(G)$ halmazát lefogó élhalmaznak nevezzük, ha $G$-nek minden csúcsára illeszkedik legalább egy $Z$-beli él.
Lefogó élszám
A $G$-beli lefogó élhalmazok közül a minimálisaknak a méretét $\rho(G)$ jelöli.
Független pontok és lefogó élek
Állítás Minden (izolált pontot nem tartalmazó) $G$ gráfra $\alpha(G) \leq \rho(G)$ teljesül.
A bizonyítás logikája
Legyen $G$-ben $Y$ egy maximális független ponthalmaz és $Z$ egy minimális lefogó élhalmaz; ekkor tehát $|Y| = \alpha(G)$ és $|Z| = \rho(G)$.
A lefedés kényszere
Mivel $Z$ lefogó élhalmaz, minden csúcsra illeszkedik $Z$-beli él, így ez $Y$ csúcsaira is igaz.A függetlenség kényszere
Ugyanaz a $Z$-beli él nem illeszkedhet két $Y$-beli csúcsra is, mert $Y$ független (nincs köztük él).Más szóval: minden $Y$-beli csúcsra másik $Z$-beli élnek kell illeszkednie. Ebből tehát $|Y| \leq |Z|$ és így $\alpha(G) \leq \rho(G)$ valóban következik.
Példa: $\alpha(G)$ és $\rho(G)$ meghatározása
Feladat kitűzése
Határozzuk meg a 7.5. ábrán látható gráfban a független pontok maximális számát ($\alpha(G)$) és a lefogó élek minimális számát ($\rho(G)$)!
7.5. ábra: Független pontok (sárga) és lefogó élek (zöld)
Megoldás levezetése
$Y = \{a, c, e, f, h, j\}$
$\alpha(G) \geq 6$
$Z = \{\{a,b\}, \{b,h\}, \{c,d\}, \{d,j\}, \{e,i\}, \{f,g\}\}$
$\rho(G) \leq 6$
Mivel korábbról tudjuk, hogy $\alpha(G) \leq \rho(G)$, a fenti konstrukciókból adódik:
$\alpha(G) = \rho(G) = 6$Lefogó és független ponthalmaz kapcsolata
Állítás Legyen $G$ tetszőleges gráf, $X \subseteq V(G)$ csúcshalmaz és $Y = V(G) \setminus X$ az $X$ komplementere. Ekkor $X$ pontosan akkor lefogó ponthalmaz, ha $Y$ független ponthalmaz $G$-ben.
Egy $H$ halmaz pontosan akkor lefogó, ha minden $\{u,v\}$ élre $u \in H$ vagy $v \in H$ teljesül. Ez logikailag pontosan azt jelenti, hogy nincs olyan él, aminek mindkét végpontja $H$-n kívül (azaz a komplementer $\bar{H}$-ban) lenne. Ez pedig a független halmaz definíciója.
Gallai-tétel (pontokra)
Minden $n$ csúcsú, hurokélmentes gráfra:
Következmény: Ha meg tudjuk határozni a gráf függetlenségi számát, abból egy kivonással azonnal megkapjuk a minimális lefogó pontok számát is.
Párosítások és lefogó élek kapcsolata
Legyen $G$ egy $n$ csúcsú, izolált pontot nem tartalmazó gráf.
- (i) ha $G$-ben van $k$ élű párosítás, akkor van benne legfeljebb $n-k$ élű lefogó élhalmaz.
- (ii) ha $G$-ben van $k$ élű lefogó élhalmaz, akkor van benne legalább $n-k$ élű párosítás.
Konstrukciós logika
Van $k$ független élünk ($2k$ csúcs lefedve). A maradék $n-2k$ magányos csúcshoz választunk egy-egy tetszőleges rájuk illeszkedő élet.
A lefogó élek részgráfja $c$ darab komponensre bomlik. Élszám: $k \ge n-c$. Minden komponensből egy-egy élet választva párosítást kapunk.
Gallai-tétel (élekre)
Minden $n$ csúcsú, izolált pontot nem tartalmazó gráfra:
Gallai-tételek
Tétel (Gallai Tibor, 1959)
Minden $n$ csúcsú $G$ gráfra fennállnak az alábbi összefüggések:
*Ha $G$-nek nincs izolált pontja.
Vizuális emlékeztető: A paraméterek összege
Figyeld meg a szimmetriát: mindkét esetben egy „független” jellegű és egy „lefogó” jellegű mennyiség összege adja ki a teljes csúcsszámot ($n$).
A bizonyítás alapja
(i) Az 5.7-es állításból tudjuk, hogy egy $X$ halmaz pontosan akkor minimális lefogó ponthalmaz, ha a komplementere maximális független ponthalmaz. Mivel $|X| + |V \setminus X| = n$, az egyenlőség közvetlenül következik.
(ii) Az 5.8-as lemmában bemutatott konstrukciókat használva belátható, hogy $\rho(G) \leq n - \nu(G)$ és $\nu(G) \geq n - \rho(G)$. A két egyenlőtlenség összevetéséből adódik az élekre vonatkozó Gallai-tétel.
Paraméterek Gyorsáttekintője
| Jel | Név | Cél | Gallai-pár |
|---|---|---|---|
| $\nu$ | Párosítási szám | Max független él | $\nu + \rho = n$ |
| $\tau$ | Lefogó pontszám | Min pont fedi élt | $\alpha + \tau = n$ |
| $\alpha$ | Függetlenségi szám | Max független pont | $\alpha + \tau = n$ |
| $\rho$ | Lefogó élszám | Min él fedi pontot | $\nu + \rho = n$ |
Összefoglaló Kvíz
Gráfelméleti Összefüggések
Vidd az egeret a kártyák fölé a helyes válaszért!
#01 Párosítás vs Lefogás
Milyen egyenlőtlenség áll fenn minden gráf esetén $\nu(G)$ és $\tau(G)$ között?
#02 Gallai Tibor tétele
Mennyi a függetlenségi szám ($\alpha$) és a lefogó pontszám ($\tau$) összege egy $n$ csúcsú gráfban?
#03 Élefedés feltétele
Milyen gráfokra érvényes a $\nu(G) + \rho(G) = n$ összefüggés?
#04 Komplementaritás
Hogyan kaphatunk meg egy maximális független ponthalmazt a lefogó pontokból?
Tudtad-e?
A MAGYAR MÓDSZER
A párosítási problémák megoldását "Hungarian Method" néven ismeri a világ. Harold Kuhn amerikai matematikus nevezte el így 1955-ben, elismerve Kőnig Dénes és Egerváry Jenő úttörő munkásságát.
VESECSERE ÉS ÉLETMENTÉS
Amikor egy donor nem kompatibilis a betegével, a kórházak kereszt-transzplantációt szerveznek. Ez matematikailag egy maximális párosítás keresése egy országos donor-recipiens gráfban, ami életeket menthet.
MUNKAERŐ-OPTIMALIZÁLÁS
A nagyvállalatok algoritmusai a Kőnig-tételt használják a dolgozók és feladatok párosítására. Ha ismerjük a képességeket, a tétel megmondja, mi a legtöbb munka, amit egyszerre kiadhatunk.
BÁSTYÁK A SAKKTÁBLÁN
Hány bástya helyezhető el egy sakktáblán úgy, hogy ne üssék egymást? Ez valójában egy páros gráf $\nu(G)$ párosítási számának meghatározása, ahol a sorok és oszlopok a csúcshalmazok.