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.

A képsor tartalma

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ő.

 

Nagyon izgalmas gráfos feladatok

08
hang
Hopsz, úgy tűnik nem vagy belépve, pedig itt olyan érdekes dolgokat találsz, mint például:

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.

Végül is miért ne néznél meg
még egy epizódot?
Ugrás az
összeshez