Diszkrét matematika epizód tartalma:
Itt röviden és szuper-érthetően elmeséljük mi egy gráf komplementere, hogyan kell gráfok komplementerével kapcsolatos feladatokat megoldni, mi a kapcsolata a gráfnak és komplementerének a teljes gráffal, aztán gráfok különböző fokszámú csúcsainak halmazait nézegetjük. És néhány rendkívül hasznos felismerésre jutunk.
Egy 100 pontú gráfról tudjuk, hogy 50 csúcs mindegyikének a foka legfeljebb 7 a másik 50 csúcs foka pedig legalább 56.
Kérdés: hány éle van ennek a gráfnak?
Ezek azok a feladatok, amiért az ember nagyon utálja a gráfelméletet…
vagy épp nagyon szereti.
Lássuk, mit kezdhetnénk az ilyen megfoghatatlannak tűnő kérdésekkel.
Az első fontos észrevétel, hogy egy egyszerű gráfban a csúcsok foka azért nem lehet olyan hatalmas.
K6-ban például minden csúcs foka 5.
És K50-ben minden csúcs foka 49.
Ezt már föl sem tudjuk rajzolni…
És nyilván ez a sötét gondolat motiválta a feladat készítőjét is.
Rajzolgatás helyett gondolkodnunk kell.
Ennek az 50 csúcsnak a fokszáma olyan nagy…
hogy csúcsonként csak 49 élt tudnak egymás közt elpasszolni.
a maradék 56-49=7 él kénytelen valamilyen más csúcsba vezetni.
Hívjuk a csúcsoknak ezen halmazát A halmaznak.
Ha az A halmazban valóban egy K50 lakozik és minden csúcs pontosan 56 fokú, akkor pontosan 350 él hagyja el az A halmazt.
De az is lehet, hogy ez az 50 csúcs nem egy teljes gráfot alkot.
Ilyenkor vannak további élek, amik kivezetnek A-ból.
A másik 50 csúcs halmaza legyen a B halmaz.
Ebben a B halmazban a csúcsok foka legfeljebb 7. Ha a halmazon belül semelyik két csúcs között nem vezet él, akkor...
legfeljebb ennyi él vezethet kívülről a B halmazba.
Ha az egyik halmaz legalább 350 éltől akar megszabadulni…
a másik pedig legfeljebb ennyit tud fogadni, akkor valami azt súgja, hogy itt a 350 lesz a végső egyezség.
Van tehát ez a 350 él.
B-ben további élek már nem lehetnek.
A-ban pedig még ezen a 350 élen kívül minden csúcs mindegyikkel össze van kötve:
Ez így akkor összesen annyi, mint 350+1225=1575 él.
Hát, ennyi éle van a gráfnak.
Nézzünk még egy ilyet.
Egy konferencián 60-an vesznek részt. A résztvevők közül 20-an már legalább 27 emberrel kezetfogtak, a többiek pedig még csak legfeljebb 4 emberrel.
Hány kézfogás történt eddig?
Ez a történet valahonnan nagyon ismerősnek tűnik…
Ja igen, ezt a feladatot oldottuk meg az előbb.
Van ez a 20 ember azzal a rengeteg kézfogással…
Ha itt mindenki mindenkivel kezetfog, akkor ez egy K20.
K20-ban a csúcsok fokszáma 19, de itt a csúcsok fokszáma 27, vagyis csúcsonként legalább 27-19=8 él kivezet a halmazból.
Hívjuk a csúcsoknak ezen halmazát A halmaznak.
Ha az A halmazban valóban egy K20 lakozik és minden csúcs pontosan 27 fokú, akkor pontosan 160 él hagyja el az A halmazt.
De az is lehet, hogy ez az 20 csúcs nem egy teljes gráfot alkot.
Ilyenkor vannak még további élek, amik kivezetnek A-ból.
A másik 40 csúcs halmaza legyen a B halmaz.
Ebben a B halmazban a csúcsok foka legfeljebb 4. Ha a halmazon belül semelyik két csúcs között nem vezet él, akkor...
legfeljebb ennyi él vezethet kívülről a B halmazba.
Ha az egyik halmaz legalább 160 éltől akar megszabadulni...
a másik pedig legfeljebb ennyit tud fogadni, akkor valami azt súgja, hogy itt a 160 lesz a végső egyezség.
Van tehát ez a 160 él.
B-ben további élek már nem lehetnek.
Ők a kockák. Elmennek úgy egy konferenciára, hogy még csak kezet se fognak egymással.
Az A-ban vannak a hiperaktívak, már mindenki mindenkivel kezetfogott, ami egy K20:
És már elkezdtek barátkozni a kockákkal is, 8 kézfogás/fő sebességgel.
Ez így akkor annyi mint 190+160=250 darab kézfogás.
Ennyi kézfogás történt eddig.
Végül nézzünk meg egy nagyon izgalmas ügyet.
Bizonyítsuk be, hogy egy G gráf és a komplementere közül legalább az egyik összefüggő.
Ha az eredeti G gráf összefüggő, akkor nincsen semmi baj.
Az állítás igaz.
Ha az eredeti G gráf nem összefüggő, akkor több komponensből áll.
Nézzük először azt az esetet, amikor kettőből.
Arról nem rendelkezünk információval, hogy a komponenseken belül mely csúcsok szomszédosak.
De az biztos, hogy a gráf komplementerében az A komponens egy tetszőleges csúcsa össze lesz kötve B minden csúcsával.
Mert a komplementerben minden olyan élt be kell húznunk, ami most nincs behúzva.
És mivel az A komponens bármely csúcsa össze lesz kötve B minden csúcsával…
az így keletkező gráf biztosan összefüggő.
Hiszen ennek a gráfnak részgráfja egy A és B pontosztályú páros gráf.
Ha pedig az eredeti G gráfnak több komponense van…
akkor az iménti gondolatmenet bármely két komponensre igaz.
Így a komplementer gráfban bármely két csúcsosztály pontjai összefüggő részgráfot alkotnak.
És emiatt a komplementer gráf összefüggő.
Diszkrét matematika epizód.