Sajátos gráfok, rész- és algráfok

• Egy G = (X,U) gráf részgráfjának (románul: graf parțial) nevezünk egy olyan G’ = (X, U’) gráfot, mely esetén U’ részhalmaza U-nak.
• Egy G = (X,U) gráf algráfjának (subgraf) nevezünk egy olyan G’ = (X’, U’) gráfot, mely esetén X’ részhalmaza X-nek és U’-ben megvan az összes olyan él, ami a G-ben az X’-ben maradt pontokra illeszkedett (vagyis csak azok az élek hiányoznak, amik a törölt pontokra illeszkedtek).
• Egy G = (X,U) gráf komplementere az a gráf, amiben a csomópontok ugyanazok és pont azok az élek vannak meg benne, amik az eredetiben nem voltak.

Tulajdonságok:

Egy n ponttal és m éllel rendelkező gráfnak hány részgráfja és hány algráfja van (az előbbi definíciók szerint)?

• 2^m részgráfja van (ennyiféleképpen lehet kiválasztani a törölni kívánt élek részhalmazát)
• 2ⁿ-1 algráfja van (mert 2ⁿ-féleképpen választható ki a pontok egy részhalmaza, de nem törölhetjük mindet, mert a megmaradt gráfnak legalább egy pontja kell legyen)

További megnevezések:

• „teljes gráf” (graf complet) – minden lehetséges él megvan benne; jelölés: K_n – az n pontú teljes gráf (éleinek száma: komb(n,2))
• „üres gráf” (románul: graful nul) – nincsenek élei
• „reguláris/szabályos gráf” – minden pontnak ugyanannyi a fokszáma
• „páros gráf” – olyan gráf, melyben a csomópontok két halmazba oszthatók (particionálhatók) úgy hogy a gráf minden éle az egyik csoporttól a másik csoport valamelyik csomópontja felé menjen
• „teljes páros gráf” – olyan páros gráf, amiben minden lehetséges él be van húzva

Séta, vonal, út

• „séta” – csomópontok sorozata, ahol két-két egymás melletti csomópont szomszédos (RO: lanț)
• „vonal” – olyan séta, ami nem megy át kétszer ugyanazon az élen (RO: lanț simplu)
• „út” – olyan séta, ami nem megy át kétszer ugyanazon a ponton (és emiatt élen sem) (RO: lanț elementar)
• „zárt vonal” – olyan vonal, amiben az első és utolsó csomópont megegyezik (ciclu)
• „kör” – olyan út, amiben az első és utolsó pont megegyezik (zárt út) (RO: ciclu elementar); megj. Ilyenkor az első és utolsó pont azonossága nem számít ismétlődésnek.
• „körmentes gráf”: gráf, amiben nincsenek körök (emiatt: zárt séták sem) (RO: graf aciclic, mert a körök hiánya és zárt vonalak hiánya egyenértékű)

Példák: a mellékelt gráfban

• 1 2 3 5 6 3 7 4 3 2 – séta, de nem vonal;
• 1 2 3 5 6 3 7 4 3 – séta is, vonal is, de nem út;
• 7 4 3 6 – séta is, vonal is, út is;
• 7 4 3 6 5 3 7 – zárt séta, zárt vonal, de nem kör;
• 7 4 3 7 – zárt séta, zárt vonal, kör is.

Euleri és hamiltoni gráfok:

• egy vonalat „Euler-vonal”-nak hívunk, ha tartalmazza a gráf minden élét (pontosan egyszer);
• egy gráf euleri, ha van benne zárt Euler-vonal;
• egy út „Hamilton-út”, a gráf minden pontját tartalmazza (pontosan egyszer);
• egy gráf „hamiltoni”, ha van benne Hamilton-kör (zárt Hamilton-út).

Példa: a mellékelt gráf euleri, mert a 2, 3, 4, 1, 7, 6, 1, 2 egy zárt Euler-vonala, de nem hamiltoni, mert bár van benne Hamilton-út (pl. 2, 3, 4, 1, 7, 6), nincs benne Hamilton-kör.

Érdekesség: königsbergi hidak problémája

Tétel (Euler):

• Egy izolált pontokat nem tartalmazó G gráf akkor és csak akkor euleri, ha összefüggő és minden csomópont fokszáma páros. (bizonyításért +pont)

Tétel (Dirac):

• Ha egy n csomópontból álló gráfban minden csomópont fokszáma >= n/2, akkor a gráf hamiltoni. (bizonyításért +pont)

Összefüggőség

• Egy gráf összefüggő, ha bármely két csomópontja között van legalább egy út (vagy séta), azaz bármely pontból bármely másikba el lehet jutni.
• Összefüggő komponensnek hívunk egy olyan maximális részt (tehát tovább nem bővíthető részt) a gráfból, ami összefüggő. (Egy nem összefüggő gráf több összefüggő komponensre bomlik.)
• Kétszeresen / duplán összefüggő komponens: olyan maximális rész, ami összefüggő és bármely pont, illetve ahhoz tartozó élek törlése esetén még mindig összefüggő marad. (Alkalmazási lehetőség: számítógép-hálózat, amely el tudja viselni egy csomópont meghibásodását.)

Példa

Ennek a gráfnak négy összefüggő komponense van, az ezekhez tartozó csomópontok:

• {6} - az izolált pont önmagában egy összefüggő komponens
• {1,4,5,9}
• {2,3,8,11}
• {7,10}

Feladat

Mennyi az összefüggő komponensek maximális és minimális száma egy olyan gráfban, aminek n csomópontja és m éle van?

Megoldás

Vegyük észre, hogy egy él bevitele egy gráfba az összefüggő komponensek számát legfeljebb eggyel csökkentheti (mert ha két eddig is azonos komponensben levő pont közé húzunk élet, akkor az összefüggő komponensek száma nem csökken, ha pedig két különböző komponensbe tartozó pont közé húzzuk be, akkor a két komponensből egy lesz, vagyis eggyel csökken az összefüggő komponensek száma).

Minimum:

Ha minimális számú összefüggő komponenst szeretnénk, akkor az üres gráfból indulva (n komponens, mindegyik egy-egy izolált pont) minden élet két különböző komponensben levő pont közé kell behúzni (élenként pontosan eggyel csökkentve az összefüggő komponensek számát). Ez mindaddig lehetséges, amíg az összefüggő komponensek száma egynél nagyobb. Az előző észrevétel alapján tehát az összefüggő komponensek minimális száma max(1, n-m).

Például n=5 és m=3 esetén legalább 5-3=2 összefüggő komponens marad. Egyik lehetőség: Az összefüggő komponensek pontjai: {5}, {1,2,3,4}.

Maximum:

Ha maximális számú összefüggő komponenst szeretnénk, akkor minél gyakrabban akarunk olyan helyzettet, amikor egy meglévő komponensen belül húzható be az új él (ekkor nem csökkenti az összefüggő komponensek számát). Ez úgy érhető el, hogy egy egyre nagyobb összefüggő komponenst készítünk, a többi pontot pedig izoláltan hagyjuk.

• m = 0 esetén az összefüggő komponensek száma nem csökken (n darab marad, mind izolált pont)
• m = 1 esetén az összefüggő komponensek száma eggyel csökken (n-1 marad: n-2 izolált pont és az alábbi komponens)
• m = 2 vagy m = 3 esetén az összefüggő komponensek száma 2-vel csökken (n-2 marad, lesz egy három pontból álló komponens és n-3 izolált pont)
• m = 4, 5, vagy 6 esetén az összefüggő komponensek száma 3-mal csökken (n-3 marad, lesz egy négy pontból álló komponens - mely legfeljebb annyi élet tartalmazhat, mint a 4 pontú teljes gráf - és n-4 izolált pont)

Általában ha m élet kell behúzni, akkor keressük a feláldozandó pontok azon minimális k számát, amelyre egy k pontú algráf tartalmazhat m élet. Mivel a k pontú teljes gráf k*(k-1)/2 élet tartalmaz, ezért ennél több él nem lehet benne.

A feladatra adott válasz tehát:

    komponensek maximális száma = {
        n, ha m = 0;
        n-k+1, különben, ahol k a legkisebb olyan természetes szám, amelyre k*(k-1)/2 >= m
    }

A k értékét meghatározhatjuk próbálgatással vagy a másodfokú egyenlőtlenség megoldásával is.

Például n = 20 és m = 8 esetén:

• k = 4 pont beáldozása nem elég, mert egy 4 pontú gráfban legfeljebb 6 él lehet
• k = 5 pont beáldozása már elég, így a válasz 16 (marad 15 izolált pont és a nagy komponens):