2. FEJEZET: Részgráfok és a komplementergráf -- izomorfia

Definíció. A 2.1. feladat olyan gráfról szólt, amelyben minden pont foka azonos. A 2.2.-2.5. feladatokban is lényegében ilyen gráfokról volt szó (bár ott nem használtuk a gráfelméleti nyelvet). Az ilyen gráfok fontos szerepet játszanak, ezért külön nevük van, reguláris gráfnak nevezzük őket. Ha minden pont foka k, akkor azt mondjuk, hogy a gráf k-reguláris. A reguláris gráfnak lehetnek többszörös élei, ekkor a többszörös éleket természetesen multiplicitással számoljuk. Mint a fokszám definíciójánál említettük, például egy háromszoros xy él x-nél is, y-nál is hármat ad a fokszámhoz.

A 2.1. feladat szerint pontosan egy hatpontú 4-reguláris egyszerű gráf van. Ezt a gráfot a térgeometriából is ismerjük, az oktaéder csúcsai és élei által alkotott gráfról van szó. A 2.2.-2.5. feladatok arról szóltak, hogy milyen n és k számokra van n pontú, egyszerű k-reguláris gráf. Az általános kérdést a 2.7. feladat taglalja.

Definíció. A reguláris gráfoknak speciális esete, de önmagában is fontos az olyan egyszerű gráf, amelynek bármely két éle éllel van összekötve. Az ilyen gráfot teljes gráfnak nevezzük. Az n pontú teljes gráfot Kn -nel jelöljük.

Másik speciális eset az olyan gráf, amelyben semelyik két pont között nem fut él, az ilyen gráfot üres gráfnak nevezzük.

Reguláris gráfokra vonatkozó feladatok - e fejezeten kívül - az 5.13., 5.14., 5.20., 5.21., 8.1., 6.1-6.4., GR.II.1.31. feladatok, továbbá néhány feladat (például a 7.28. feladat) a fákról (közelebbről: favázakról) szóló fejezetben. Lásd még a 10.10., a 10.11., a GR.II.1.3. és a GR.II.1.4. feladatokat is.

Sok reguláris gráffal találkozhatunk majd a speciális gráfelméleti témákat tárgyaló kötetben, így a Ramsey-típusú tételekről (GR.II.3.) , a Turán-tételről (GR.II.2.), valamint a Gráfok izomorfiájáról (GR.II.4.) szóló fejezetben. Speciális reguláris gráfokkal, például a szabályos testek élgráfjaival, a Petersen-gráffal és a Kneser-gráfokkal és általában a csúcstranzitív gráfokkal foglalkozik a Gráfok automorfizmusai c. fejezet (GR.II.5.).

Már az 1.4. feladat megoldásánál is segített, hogy az ismeretségek helyett a ,,nem-ismeretségeket", illetve a nem-ismeretségek helyett az ismeretségeket vizsgáltuk. Ugyanez az ötlet segített például a K.I.18.10. feladat b) részének a megoldásánál is, amikor azt a gráfot néztük, amely az eredeti gráfban be nem húzott élekből áll. Az 1.17., a 2.1. és a 2.12. feladat megoldásának is az volt a kulcsa, hogy áttértünk arra a gráfra, amely a ,,nem-élekből" áll. Az így kapott gráfok ugyanis sokkal könnyebben áttekinthetők voltak.

Ezek a példák is mutatják, hogy sokszor könnyít a helyzetünkön, ha egy adott relációnál nem azt vizsgáljuk, hogy melyik objektumok között áll fenn, hanem azt, hogy melyikek között nem áll fenn. Megjegyezzük, hogy az ötlet nagyon hasonló ahhoz, mint amikor a valószínűségszámításban egy esemény valószínűsége helyett a komplementer esemény valószínűségét számoljuk ki, mert az egyszerűbben kiszámolható. Érdemes tehát definiálnunk a gráf komplementerét: Definíció. A G egyszerű gráf komplementerének azt a G ‾ gráfot nevezzük, amelynek pontjai azonosak G pontjaival, és két pontja között pontosan akkor fut él, ha a G gráfban nem fut közöttük él. Figyeljünk rá, hogy csakis egyszerű gráf komplementerét definiáltuk. Nem ilyen egyszerű az olyan gráfok komplementerét definiálni, amelyek nem egyszerűek (hogy a szóviccel éljünk). Nyilvánvaló a definícióból, hogy egy gráf komplementerének komplementere önmaga.

Ha megnézzük az 1.17. és 1.18. feladatokat, a megoldásnak lényeges pontja volt, hogy a gráf bizonyos pontjait és a belőle induló éleket elhagytuk és csak az így maradó gráfot vizsgáltuk. Az így kapott gráfot az eredeti gráf részgráfjának nevezzük. De vigyáznunk kell, az így kapott gráfok a részgráfoknak csak egyik fajtáját alkotják, az úgynevezett feszített részgráfokat. A pontos definíció a következő:

Ha a G gráfból elhagyunk néhány (esetleg minden) pontot a belőle induló élekkel, akkor az így kapott gráfot a G gráf feszített részgráfjának nevezzük. Egy másik megfogalmazási lehetőség: ha Y a G gráf pontjainak részhalmaza (lehet az üres halmaz és az egész V(G) halmaz is!), akkor tekinthetjük azt a gráfot, amelynek ponthalmaza Y, élhalmaza pedig azok az élek, amelyek Y pontjai között futnak az eredeti G gráfban. Az így kapott gráfot a G gráf Y által feszített részgráfjának nevezzük. Megjegyezzük, hogy ha az egyszerű gráf egy feszített részgráfja teljes gráf, akkor ezt a részgráfot a gráf klikkjének is szokás nevezni.

A feladat általánosításáról szól a 3.9. feladat.

A feszített részgráfok tehát fontos ,,szereplői" a gráfelméletnek. De nemcsak az ilyen részgráfok érdekesek. Ha például azt kérdezzük - l. például A ,,Turán-tétel" két egyszerű esete c. alfejezetet -, hogy bizonyos egyszerű gráfokban van-e ,,háromszög" (azaz három olyan pont, amelyek közül mindegyik össze van kötve a másikkal), akkor feszített részgráfot keresünk. Akkor is feszített gráfra gondolunk, ha azt kérdezzük, van-e három pont, amelyek közül egyik sincs összekötve a másikkal. Ha azonban azt kérdezzük, hogy van-e négy olyan pont, amelyek közül az első össze van kötve a másodikkal, a második a harmadikkal, a harmadik a negyedikkel és a negyedik az elsővel (azaz van-e benne ,,négyszög"), akkor már nem feltétlenül feszített részgráfra gondolunk, hiszen az is jó lehet nekünk, ha négy olyan pontot találunk, amelyek közül bármely kettő között fut él. Az 1.15. feladatban azt kellett bizonyítani, hogy egy telített és izolált pont nélküli egyszerű gráfban mindig van két független él. Itt sem érdekelt minket, hogy a talált négy pont között fut-e még más él is a két független élen kívül. Általában is gyakran keresünk lehetőleg minél nagyobb független élrendszert egy gráfban, és ilyenkor általában nem ,,zavar" minket, ha az élek végpontjai között más élek is futnak. A részgráfot tehát általánosan is definiáljuk. Az analógia a halmaz és részhalmaz fogalma lehet. De rögtön látni fogjuk, hogy van különbség is.
Definíció. Adott egy G gráf. A G' gráfot pontosan akkor nevezzük a G gráf részgráfjának, ha pontjai a G pontjai közül kerülnek ki, élei pedig a G gráf élei közül. Az említett különbség abból adódik, hogy a részgráf élhalmaza nem lehet az eredeti élhalmaz bármelyik részhalmaza, mert egy él csak akkor szerepelhet egy gráfban, ha a végpontjai a ponthalmazhoz tartoznak. Tehát a részgráf élhalmaza az eredeti élhalmaz olyan részhalmaza, amely a részgráf pontjai között futó élhalmaznak is része. Egy halmaz részhalmazaihoz hozzáértjük az üres halmazt is, ugyanígy itt a részgráfokhoz hozzávesszük az üres részgráfot is, tehát azt, amelynek sem pontja, sem éle nincsen. Ez a legegyszerűbb részgráf. Egy halmaz részhalmazaihoz hozzáértjük magát a halmazt is. Mi felel meg ennek a gráfoknál? Első lépésben nyilván maga a gráf. Csakhogy a gráfot két halmaz - a pontok és az élek halmaza - együtt jellemez. Ennek megfelelően itt kétféle kitüntetett részgráf van. Az egyik a már definiált feszített részgráf. A másik az, ahol a részgráf ponthalmaza azonos a gráféval. Az ilyen részgráfokat - kissé suta magyar szóval - feszítő részgráfnak nevezzük.
A feszítő részgráfok közül különösen az úgynevezett feszítő fák, vagy favázak lesznek fontosak, ezekkel ALG.II. kötet külön fejezetében, a Fák, favázak című (ALG.II.3.) fejezetben foglalkozunk.

Kommentár.

A 2.12. feladatban magától értetődően beszéltünk arról, hogy hány hét-, vagy kilencpontú 2-reguláris gráf van. A K.I.18.19., az 1.14. és a 2.30. feladatban magától értetődően beszéltünk arról, hogy például hány négypontú, kétélű gráf van vagy hány ötpontú négyélű gráf van. Valójában persze végtelen sok van, hiszen a pontok halmazát végtelen sokféleképp választhatjuk. Mi mégis arra jutottunk, hogy például négypontú, kétélű gráfból csak kettő van. Eközben tehát magától értetődően azonosnak tekintettünk bizonyos gráfokat. A 2.3. feladatban kétféleképp rajzoltuk fel ugyanazt az ,,ültetési rendet", azaz gráfot. Próbáljuk megfogalmazni, mikor tekintünk két gráfot azonosnak. Nyilván akkor, ha a két gráf pontjai megfeleltethetőek egymásnak úgy, hogy az élek ,,ugyanazok" legyenek a két gráfban. Az ilyen gráfokat izomorf gráfoknak nevezzük. A pontos definíció a következő: Definíció. A G és a G' gráfot akkor és csak akkor tekintjük egymással izomorfnak, vagy egyszerűen izomorfnak, ha létezik a pontjaik között olyan egy-egy értelmű megfeleltetés, amely mellett igaz, hogy G-ben két pont között pontosan akkor fut él, ha G'-ben a megfelelőik között is fut él. Természetesen ugyanez igaz fordítva is: G'-ben két pont között pontosan akkor fut él, ha G-ben is fut él az ,,ősképeik" között. Magát az ,,izomorfiát létrehozó" egy-egyértelmű leképezést szokás izomorfiának nevezni.
Megjegyzés. A gráfok izomorfiájával kapcsolatos feladatok a GR.II. kötet Szimmetria és aszimmetria című fejezetében találhatók.