Barion Pixel Gráf komplementere, csúcshalmazok | mateking
 

Diszkrét matematika epizód tartalma:

Itt röviden és szuper-érthetően elmeséljük mi egy gráf komplementere, 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

Itt van ez a 6 csúcsú egyszerű gráf.

Biztosra mentünk, és minden csúcsot mindegyikkel összekötöttük.

Vagyis ez itt egy K6.

Egy gráf komplementere azt a gráfot jelenti, aminek csúcsai ugyanazok, mint az eredeti gráfnak, és két csúcs pontosan akkor szomszédos benne, ha az eredeti gráfban nem.

Ebben a gráfban mindenki mindenkivel szomszédos…

így aztán a komplementer ez.

Ha néhány csúcs van csak összekötve…

akkor a komplementerben is néhány csúcs lesz összekötve.

Azok, akik eredetileg nem.

Nem túl meglepő, hogy egy gráf és komplementere együtt kiadja a teljes gráfot.

Hiszen egy él vagy az eredeti gráfban van behúzva…

vagy, ha ott nincs, akkor a komplementerben.

Most pedig nézzünk egy nagyon hasznos dolgot.

Van ez a gráf, és válasszuk ki néhány csúcsát.

Mondjuk, válasszuk ki ezeket itt.

Ezek a csúcsok ötödfokú csúcsok.

De csak hárman vannak, ezért csúcsonként csak 2 fokszámnyi élt tudnak egymás közt elpasszolni…

a maradék többi él kénytelen valamilyen más csúcsba vezetni.

Itt vannak aztán ezek a csúcsok is.

Egymás közt itt sem túl sok él megy.

A maradék többi él itt is kénytelen másfelé szerencsét próbálni.

És éppen ugyanannyi elvándorló él van az egyik halmaz csúcsainál, mint a másiknál.

Így aztán nagy az öröm az egymásra találásnál.

Most nézzük, mi a helyzet ezzel az egyszerű gráffal.

Annyit tudunk róla, hogy van 3 ötödfokú csúcsa és 3 elsőfokú csúcsa.

Lássuk a gráf éleit.

Egyáltalán nem biztos, hogy itt mindenki mindenkivel össze van kötve.

De most képzeljük azt egy pillanatra, hogy igen.

A csúcsok fokszáma 5, így aztán még van jónéhány él, ami kivezet az A-n kívülre.

Amíg ezeket az éleket a többi csúcs képes fogadni, nincs is semmi baj.

De most úgy tűnik, hogy nagy baj van.

Sajnos a B halmaz legfeljebb 3 élt tud fogadni.

És az A-ból legalább 9 él indul.

Ha nincs mindenki mindenkivel összekötve, akkor még több is.

De a 9 él az biztos.

Így aztán nem lesz egyezség. Ilyen gráf nem létezhet.

Ha persze G nem egyszerű gráf, úgy könnyű…

De a megadott tulajdonságokkal rendelkező egyszerű gráf…

nem létezik.

Egy 24 csúcsú G egyszerű gráfban 12 csúcs foka 5, a másik 12 csúcs foka pedig 16. Összefüggő-e a G gráf komplementere?

A 12 csúcs, ahol mindenkinek a fokszáma 16 meglehetősen brutális.

Ha minden csúcs minden másikkal össze van kötve…

már az is elképesztően sok él.

És akkor itt minden csúcs fokszáma még csak 11.

Úgy jön ki a 16, ha van még csúcsonként plusz 5 él.

Most nézzük, a B halmaz mennyit képes közülük fogadni.

Pont ennyit.

Vagyis az A halmazból csúcsonként legalább 5 él kell, hogy kivezessen, a B pedig csúcsonként maximum ennyit képes fogadni.

Ez azt jelenti, hogy pontosan tudjuk, hogyan néz ki a gráf.

Van benne egy K12 és annak minden csúcsa össze van kötve a B halmaz 5 különböző csúcsával.

Most nézzük, hogy mi lesz ennek a gráfnak a komplementere.

Itt senki senkivel nem lesz összekötve, az egyszer biztos.

Aztán a csúcsonkénti 5 él helyett a többi csúcsba megy 7 él.

B-ben meg jó sok él be lesz húzva, de a lényeg…

ezek az élek.

Ez garantálja, hogy B-ben bármely két csúcs között vezet út.

Mivel pedig A-nak bármely csúcsa össze van kötve legalább egy B-beli csúccsal, így bármely két A-beli csúcs között is vezet út.

Így aztán a G gráf komplementere összefüggő.

Egy összefüggő egyszerű gráfnak 40 csúcsa és 42 éle van. Bizonyítsuk be, hogy van a gráfban 3 különböző kör. Két kör akkor különböző, ha van legalább egy olyan él, amelyiket az egyik kör tartalmazza, de a másik nem.

Nem fogunk itt bajlódni 40 darab csúccsal.

Azt kell megérteni, hogy lehetne 50 csúcsú és 52 élű is a gráf, vagy 1000 csúcsú és 1002 élű, a lényeg itt nem ez.

A lényeg itt az, hogy egy n csúcsú összefüggő gráfnak minimum n-1 darab éle van.

Ebben az esetben a gráf körmentes, hiszen fa.

Ha hozzáveszünk az n-1 darab élhez még egyet, akkor valahol kör keletkezik.

Ha még egy élt hozzáveszünk, akkor még egy kör keletkezik, ami biztosan különbözik az előző körtől, hiszen abban nem szerepelhetett az az él, amit most vettünk hozzá a gráfhoz.

És még egy él hozzávételével még egy kör keletkezik.

Az állítást bizonyítottuk, ráadásul nem csak a 40 csúcs 42 él esetre, hanem általánosan.

Még azon is el lehet filozofálni, hogy összesen hány kör keletkezik.

Van úgy, hogy csak 3…

Aztán lehet benne 4 kör is.

És maximum 6.

Egy összefüggő egyszerű gráfnak 1000 csúcsa és 1000 éle van. Bizonyítsuk be, hogy van a gráfban 3 különböző feszítőfa. Két feszítőfa akkor különböző, ha van legalább egy olyan él, amelyiket az egyik feszítőfa tartalmazza, de a másik nem.

Vegyük a gráfnak egy feszítőfáját. A feszítőfának 999 éle van.

Ha ezek után hozzávesszük az ezredik élt, akkor keletkezik egy kör.

Nem tudjuk, hogy a kör hány élt tartalmaz…

De három különböző élt egészen biztosan.

Bármelyiket elhagyva a gráfnak egy-egy különböző feszítőfáját kapjuk.

Van itt ez a három gráf…

ami valójában csak egy.

Ez a három gráf ugyanannak a gráfnak a három különböző vizualizációja.

A három gráf egymással

BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez