Ugrás a tartalomhoz

Matematikai mozaik

Andrásfai Béla, Bakos Tibor, Bognár Jánosné, Bognár Mátyás, Gallai Tibor, Hódi Endre, Laczkovich Miklós, Molnár Ferenc, Reimann István, Rényi Alfréd, Révész Pál, Rónyai Lajos, Surányi János, Vadkerty Tibor, Varga Tamás

Typotex

A KÖNIGSBERGI HIDAK, A KILENC ÖSVÉNY ÉS MÁS GRÁFELMÉLETI PROBLÉMÁK

A KÖNIGSBERGI HIDAK, A KILENC ÖSVÉNY ÉS MÁS GRÁFELMÉLETI PROBLÉMÁK

GALLAI, TIBOR


Königsbergi hidak. Euler-vonal.  A XVIII. század 30-as éveiben Königsberg város polgárai a következő kérdést vetették fel: Königsbergnél a régi és új Pregel összefolyásánál a Pregel folyó egy szigetet alkot, s itt annak idején 7 híd állt. Milyen sorrendben kell az egyes hidakon áthaladni, hogy minden hídon egyszer és csakis egyszer menjünk keresztül? (1. ábra.)

A kérdésre csak tagadó válasz adható: a hidakat nem lehet a kívánt módon bejárni. Ezt szeretnénk most belátni.

Először a térképvázlatot egy egyszerűbb képpel helyettesítjük. Minden partot egy-egy ponttal (A

A , B B , C C , D D ) jelképezünk, a hidakat pedig egy-egy, a pontokat összekötő vonallal (2. ábra). A kapott ábrát gráfnak nevezik. Ebben lényegtelen a pontok helyzete és a vonalak alakja, csak az a fontos, hogy melyik két pontot hány vonal köt össze. A A , B B , C C , D D a gráf csomópontjai vagy szögpontjai (a továbbiakban ezeket többnyire csak pontoknak nevezzük), a csomópontokat összekötő vonalak a gráf élei. (Egy élnek csak a végpontjai csomópontok!)

Problémánkat most így fogalmazhatjuk meg: hogyan lehet a ceruzát felemelés nélkül úgy végigvezetni a gráf élein, hogy mindegyiken egyszer és csakis egyszer haladjunk keresztül, vagy még rövidebben, hogyan lehet az ábrát egyetlen összefüggő vonallal megrajzolni? Ehhez hasonló az a közismert feladat, amely a 3. ábrán

látható „ház” egyetlen vonallal való megrajzolását követeli meg. Itt a gráf 5 csomópontból és 8 élből áll. (A négyzet átlóinak metszéspontját tehát nem tekintjük csomópontnak, ott áthaladva nem szabad irányt változtatni, a teljes átlók alkotnak csak egy-egy élt.)

A 2. ábra megrajzolásával próbálkozva egy híján sikerült minden élt egyetlen vonalba belefoglalni (4. ábra). Figyeljük meg itt, hogy egy olyan pontnál, amelyik sem nem kezdőpont, sem nem végpont (B

B és D D ), ugyanannyiszor lépünk be, mint ahányszor kifutunk, a kezdőpontnál (A A ) eggyel többször lépünk ki, a végpontnál (C C ) pedig eggyel többször lépünk be (mint ahányszor be-, ill. kifutottunk). Nem nehéz utánagondolni, hogy megállapításaink nemcsak a 4. ábrára, hanem minden olyan, egyetlen vonallal megrajzolt gráfra is érvényesek, amelynél a vonal kezdőpontja nem esik egybe a végpontjával. A rövidség kedvéért nevezzünk egy vonalat nyitottnak, ha kezdő- és végpontja különböző, zártnak pedig, ha e két pont egybeesik. Ekkor megállapításainkból következik, hogy bármely nyitott vonallal megrajzolt gráfban a kezdő- és végponttól különböző pontokhoz páros számú, a kezdő- és végponthoz pedig páratlan számú él illeszkedik. Egy ponthoz illeszkedő élek számát a pont fokának nevezik. Egy pontot, amelynek foka páros, ill. páratlan, röviden páros, ill. páratlan pontnak fogunk mondani. Az előzőek most így fogalmazhatók:

egyetlen nyitott vonallal megrajzolt gráfban a kezdő- és a végpont páratlan, a többi pont pedig páros.

Ugyanilyen módon látható be a következő állítás is:

egyetlen zárt vonallal megrajzolt gráfban valamennyi pont páros.

Állításaink alapján megállapíthatjuk, hogy a königsbergi hidak gráfja (2. ábra) nem rajzolható meg sem zárt, sem pedig nyitott vonallal. Ebben a gráfban ugyanis mind a négy pont páratlan. A 3. ábra gráfja nem rajzolható meg zárt vonallal, mert a két alsó pont páratlan. Ha nyitott vonallal megrajzolható, a kezdő- és végpontnak az alsó két pontnak kell lennie. Néhány próbálkozás után valóban sikerült megfelelő nyitott vonalat találni (5. ábra). Ha az alsó két pontot még egy újabb éllel is összekötjük, akkor az új gráfban (6. ábra) már minden pont páros lesz, és az 5. ábra alapján azonnal látható, hogy az új gráf megrajzolható egyetlen zárt vonallal (7. ábra).

Az elmondottakból sejthető a következő, Eulertől származó tétel (a tétel bizonyítását nem közöljük):

Minden véges, összefüggő és csupa páros pontot tartalmazó gráf megrajzolható egyetlen zárt vonallal.

A gráf összefüggő volta nyilvánvalóan szükséges az egyetlen vonallal való megrajzolhatósághoz. (A 8. ábrán látható, két különálló háromszögből álló gráfot nem lehet egyetlen vonallal megrajzolni.)

Fel kell tenni a gráf végességét is (véges a gráf, ha véges sok éle és véges sok csomópontja van), mert hiszen minden zárt és nyitott vonal véges sok élből áll, egy végtelen gráf pedig általában végtelen sok élt tartalmaz. A 9. ábrán a végtelen gráf csomópontjai a számegyenesnek az egész számokhoz tartozó pontjai, élei a szomszédos egészeket összekötő szakaszok. A 10. ábrán a „végtelen kockás papiros” gráfját, ill. annak egy részletét tüntettük fel.

Megemlítjük, hogy az olyan zárt vonalakat, amelyek egy gráf minden élét tartalmazzák, a gráf Euler-vonalainak nevezzük.

Euler tételéből következtetést vonhatunk le olyan összefüggő és véges gráfok megrajzolhatóságára, amelyekben két páratlan pont van, és amelyekben valamennyi többi pont páros. Ha egy ilyen gráfban a két páratlan pontot egy új éllel összekötjük, akkor olyan összefüggő és véges gráfhoz jutunk, amelyben minden pont páros. (Vö. a 3. és 6. ábrával!) Euler tétele szerint ez megrajzolható egyetlen zárt vonallal (7. ábra). Ha ebből a zárt vonalból elhagyjuk az új élt, olyan nyitott vonal marad vissza, amely az eredeti gráf minden élét tartalmazza, és amelynek kezdő- és végpontja a két páratlan pont (5. ábra). Ezzel beláttuk a következő állítás helyességét:

Minden olyan véges és összefüggő gráf, amelyben két páratlan pont van, és amelyben a többi pont páros, megrajzolható egyetlen nyitott vonallal. A nyitott vonal kezdő- és végpontja a két páratlan pont.

Hasonló meggondolásokkal látható be Euler tételéből a következő, általánosabb tétel is: ha egy véges és összefüggő gráfban a páratlan pontok száma 2k

2 k (k k tetszőleges pozitív egész szám), akkor a gráf k k számú nyitott vonallal megrajzolható. E nyitott vonalak mindegyikének kezdő- és végpontja egy-egy páratlan pont. Nem nehéz azt sem belátni, hogy az említett tulajdonságokkal rendelkező gráf nem rajzolható meg k k -nál kevesebb számú vonallal. (Pl. a 2. ábra gráfja két vonallal megrajzolható, eggyel nem.)

Az említett tételekkel a véges és összefüggő gráfok mindegyikét érintettük. Egyszerűen megmutatható ugyanis, hogy véges gráf nem tartalmazhat 1 vagy 3 vagy 5… páratlan pontot.

Másképpen kifejezve:

Minden véges gráfban a páratlan pontok száma páros.

A végesség kikötése lényeges, mert pl. az a gráf, amelynek csomópontjai a számegyenes pozitív egész számokkal megjelölt pontjai, élei pedig a számegyenes e pontokat összekötő szakaszai, egyetlen páratlan pontot tartalmaz (11. ábra).

A végtelen gráfokkal kapcsolatban is felvethető az a kérdés, hogy melyek „rajzolhatók meg” egyetlen, mindkét irányban végtelen vonallal. Nyilvánvalóan megrajzolható ilyen módon a 9. ábra gráfja. A 12. ábra mutatja, hogy a 10. ábra gráfjával ugyanez a helyzet.

A megrajzolhatósághoz itt is szükséges a gráf összefüggő volta, valamint az, hogy minden pont páros legyen (feltételezzük, hogy minden ponthoz csak véges sok él illeszkedik). A 13. ábra gráfja (ennek csomópontjai egy derékszögű koordináta-rendszer két tengelyén fekvő, egész koordinátájú pontok, élei pedig a tengelyeknek e pontokat összekötő szakaszai) azonban azt mutatja, hogy ez a két feltétel nem elégséges ahhoz, hogy egy végtelen gráf a kívánt módon megrajzolható legyen. Megadhatók a megrajzolásnak szükséges és elégséges feltételei is; ezek azonban összetettebbek.

Hamilton-vonal. Másodfokú faktorok.  Az eddig tárgyalt problémákban szereplő vonalak „keresztezhették” önmagukat (l. pl. a 7. ábrát!). A gráfelméletben fontos szerepet játszanak az önmagukat nem keresztező vonalak is. Ezek közül a zártakat körutaknak, röviden köröknek nevezzük. Ha egy kör 3, 4 stb. élt tartalmaz, akkor háromszögnek, négyszögnek stb. is mondjuk.

A 14. ábrán a vastagon rajzolt élek olyan kört (hatszöget) alkotnak, amely a gráf minden csomópontján átmegy. Egy ilyen kört a gráf Hamilton-vonalának nevezünk. Nem minden gráfnak van Hamilton-vonala. Pl. a 15. ábrán látható gráfnak nincs.

A Hamilton-vonalak létezésére nem ismerünk olyan feltételeket, melyek szükségesek és elégségesek is. A következőkben ismertetünk két egyszerűen megfogalmazható elégséges feltételt (ezeknek bizonyítása lényegesen nehezebb, mint az előzőekben említett Euler-tételé).

Ha egy gráfban minden pont foka ≥k

k (k k tetszőleges, 1-nél nagyobb egész szám) és a gráf nem tartalmaz 2k 2 k -nál több pontot, akkor van Hamilton-vonala. (Dirac tétele.)

(E tétel alkalmazható pl. a 14. ábra gráfjára.)

Ha egy háromszöget úgy bontunk szét háromszögekre, hogy bármely két háromszögnek (az eredetit is beleértve) vagy nincsen közös pontja, vagy egyetlen csúcsuk, vagy egy egész oldaluk közös (l. 14. ábra), továbbá ha az eredeti háromszöget nem tekintve, az ábra egyetlen háromszögén belül sincsenek további háromszögek (a 16. ábra felosztása nem ilyen), akkor annak a gráfnak, amelynek csomópontjai a háromszögek csúcsai, élei pedig a háromszögek oldalai, van Hamilton-vonala. (Whitney tétele.)

Ez a tétel is alkalmazható a 14. ábra gráfjára. Mindkét tételben a feltételek nem „szükségesek”, tehát léteznek olyan gráfok, amelyek e feltételeknek nem tesznek eleget, és mégis van Hamilton-vonaluk. (A 16. ábra gráfja is ilyen.)

Említettük, hogy a 15. ábra gráfjának nincsen Hamilton-vonala, tehát nem lehet a gráf valamennyi csomópontját belefoglalni egyetlen körbe. Lehetséges azonban a csomópontokat két olyan körbe foglalni, amelyeknek nincs közös pontjuk. (A megvastagított élek két ilyen kört alkotnak.) Egy tetszőleges gráfnál a köröknek olyan rendszerét, amelynek körei együtt a gráfnak minden csomópontját tartalmazzák, de amelyek közül bármelyik kettőnek nincs közös pontja, a gráf másodfokú faktorának nevezzük. (A Hamilton-vonal is másodfokú faktor!) Másodfokú faktora sincs minden gráfnak, még olyanoknak sem mindig, amelyekben – ilyen volt a 15. ábra gráfja is – minden pont foka ugyanakkora. A 17. ábrán levő gráfban minden pont harmadfokú, de a gráfnak nincsen másodfokú faktora. Mint az alábbi, bizonyítás nélkül közölt (Petersentől származó) tételek mutatják, egy gráfnak az a „szabályossága”, hogy minden pontjának ugyanakkora a foka, esetleges egyszerűbb kiegészítő feltételekkel együtt biztosítja másodfokú faktor létezését.

Ha egy véges gráf minden pontjának ugyanakkora a foka, és ez a fokszám pozitív páros szám, akkor a gráfnak van másodfokú faktora.

(Ez a tétel alkalmazható pl. a 14. ábra gráfjára.)

Ha egy véges és összefüggő gráf minden pontjának ugyanakkora a foka, és ez a fokszám 1-nél nagyobb páratlan szám, továbbá, ha a gráfnak nincsen hídja, akkor a gráfnak van másodfokú faktora. (Hídnak nevezzük egy összefüggő gráfnak olyan élét, amelynek elhagyása két össze nem függő részre bontja a gráfot.)

A 17. ábra gráfjának három hídja van. Az utóbbi tétel alkalmazható a 15. ábra gráfjára.

Megjegyezzük, hogy az utolsó két tétel feltételeinek teljesülése sem szükséges a másodfokú faktor létezéséhez. Pl. a 3. ábra gráfjának van másodfokú faktora, pedig nem teljesíti e tételek feltételeit.

Elektromos hálózatok.  A gráfok köreinek vizsgálata igen fontos a gráfelmélet elektrotechnikai alkalmazásaiban. A múlt század 40-es éveiben Kirchhoff dolgozta ki az elektromos hálózatok számítási eljárásának alapjait. Ezekben felhasználta a gráfok köreinek néhány tulajdonságát. Egy elektromos hálózat ágai a gráf éleinek, összekapcsolási pontjai a gráf csomópontjainak tekinthetők. A továbbiakban csak olyan hálózatokról lesz szó, amelyekben csupán ohmikus ellenállások (pl. izzólámpák) és telepek (zseblámpaelemek) fordulnak elő. A 18. ábrán egy 6 ágból és 4 csomópontból álló hálózat látható.

Telep csak az egyik ágban van; ennek elektromotoros erejét (feszültségét) E

E -vel jelöljük (egy zseblámpaelemnél ez 4,5 volt). A telepet tartalmazó ág ellenállása, a telep belső ellenállásával együtt legyen R_0 R 0 (R_0 R 0 az ohmok számát jelöli), a többi ágban elhelyezett ellenállások nagysága legyen rendre R_1 R 1 , R_2 R 2 , R_3 R 3 , R_4 R 4 és R_5 R 5 .

A 19. ábrán az izzókat jelző köröket elhagytuk, csak az ellenállások értékét írtuk a megfelelő gráfélek mellé, az elem rajzát pedig a szokásos jelzéssel helyettesítettük.

A legegyszerűbb számítási feladatokban megadják az E

E feszültség és az R_0 R 0 , R_1 R 1 , …, R_5 R 5 ellenállások nagyságát, és ezekből kell meghatározni az egyes ágakban folyó áramok erősségét (intenzitását), valamint az áramlási irányokat. A továbbiakban azt akarjuk megmutatni, hogyan segíti elő a hálózati gráf tulajdonságainak vizsgálata az intenzitások meghatározását.

Az áramlási irányok meghatározása nem okoz külön gondot. Vegyünk fel ugyanis minden egyes ágban tetszőlegesen egy-egy áramlási irányt, és ezzel együtt tekintsük a meghatározandó I_0

I 0 , I_1 I 1 , …, I_5 I 5 intenzitásokat előjeles (pozitív vagy negatív) mennyiségeknek, olyan értelemben, hogy ha egy ágban, pl. R_1 R 1 -ben, a tényleges áramlás iránya megegyezik a felvett iránnyal, akkor I_1 I 1 -et pozitívnak, ha ellentétes vele, akkor negatívnak tekintjük.

(20. ábra. Pl. ha a számítások az I_1=–0,5

I 1 = 0,5 amper értéket szolgáltatják, akkor az R_1 R 1 ágban a tényleges áramlás iránya a (2)-es csomóponttól az (1)-es felé mutat.)

6 ismeretlent (I_0

I 0 , I_1 I 1 , …, I_5 I 5 ) kell meghatároznunk. Ehhez 6 egyenletre van szükségünk, mégpedig olyan 6 egyenletre, amelyek függetlenek egymástól, vagyis ahol egyik sem „következménye” a másik ötnek. (Pl. az x+y=5 x + y = 5 és a 2x+2y=10 2 x + 2 y = 10 egyenletekből nem lehet egyértelműen kiszámítani az x x és y y ismeretleneket. Ezek az egyenletek nem függetlenek egymástól, a második „semmi újat” nem mond az elsőhöz képest; az elsőt kielégítő, bármelyik x x , y y számpár a másodikat is kielégíti.) Az egyenleteket az ún. Kirchhoff-féle törvények alapján lehet felírni. Az első törvény azt mondja ki, hogy bármely csomópontnál a befutó áramok intenzitásainak összege egyenlő a kifelé haladók intenzitásainak összegével. Ennek alapján minden csomóponthoz felírhatunk egy-egy egyenletet:

(1)I_0=I_1+I_3 I 0 = I 1 + I 3
(2)I_1=I_2+I_5 I 1 = I 2 + I 5
(3)I_3+I_5=I_4 I 3 + I 5 = I 4
(4)I_2+I_4=I_0 I 2 + I 4 = I 0

A második Kirchhoff-törvény a hálózat köreire vonatkozik (és lényegében az Ohm-törvénynek egyszerű következménye). Válasszunk ki a gráfban egy kört, és lássuk el tetszőleges befutási iránnyal (21. ábra szaggatott vonalai)!

A kör által tartalmazott minden egyes ág (él) ellenállását szorozzuk meg az ágban folyó áram intenzitásával, és lássuk el ezeket a szorzatokat +

+ vagy – előjellel aszerint, hogy az ág irányítása megegyező vagy ellenkező a kör befutási irányával. A Kirchhoff-törvény szerint ekkor a kapott értékek összege megegyezik a kör ágaiban elhelyezkedő telepek (megfelelő előjellel vett) feszültségeinek összegével. A 21. ábrán négy irányított kört tüntettünk fel. Az ezekhez tartozó egyenletek:

(5)R_0I_0+R_3I_3+R_4I_4=E R 0 I 0 + R 3 I 3 + R 4 I 4 = E
(6)R_1I_1+R_5I_5–R_3I_3=0 R 1 I 1 + R 5 I 5 R 3 I 3 = 0
(7)R_2I_2–R_4I_4–R_5I_5=0 R 2 I 2 R 4 I 4 R 5 I 5 = 0
(8)R_0I_0+R_1I_1+R_2I_2=E R 0 I 0 + R 1 I 1 + R 2 I 2 = E

(Egy kör befutási irányának megváltoztatása a körhöz tartozó egyenletben a tagok előjelének megváltozását eredményezi.) Ha a befutási irányoktól eltekintünk, akkor gráfunknak a feltüntetett 4 körön kívül (ezek mind háromszögek) még három köre van (ezek négyszögek, l. 22. ábra).

Irányításuk után ezekhez is felírható egy-egy egyenlet. Így 7 kör-egyenlet és 4 csomóponti egyenlet, tehát összesen 11 egyenletünk lesz. Ezek közül kell 6 függetlent kiválasztani. A választásban nem szerepelhet mind a négy csomóponti egyenlet. Könnyen ellenőrizhető ugyanis, hogy közülük az első hármat összeadva éppen a negyediket kapjuk. De nem szerepelhet mind a négy felírt kör-egyenlet sem, mert itt is igaz, hogy közülük az első három összege éppen a negyediket (a (8)-as egyenletet) adja.

A csomóponti egyenletekre belátható, hogy közülük bármely három független egymástól; sőt általánosan is igaz, hogy bármilyen összetett hálózat esetén, ha a hálózat p

p számú csomópontot tartalmaz, akkor bárhogyan is választunk ki közülük p–1 p 1 csomópontot, az ezekhez tartozó egyenletek függetlenek egymástól (a p p -edik csomóponthoz tartozó viszont következménye a többinek).

Nehezebb feladat a 7 kör-egyenlet közül kiválasztani 3 függetlent (a 3 csomóponti egyenlettel együtt így juthatnánk 6 független egyenlethez). Fő célunk éppen az, hogy példánkon keresztül megmutassuk, miként lehet kiválasztani a hálózati gráf vizsgálata révén (tetszőleges hálózat esetén is) a szükséges számú megfelelő kört.

A kör-egyenletek között fennálló kapcsolatok gyökere az irányított gráfkörök közti kapcsolatban keresendő. Hogy az (5)-, (6)- és (7)-tel jelzett egyenletek összege éppen a (8)-as egyenletet fogja adni, az kitűnik a 23. ábrából,

ha annak bal oldali részén az ellentétesen befutott éleket „megsemmisítetteknek” tekintjük.

Emiatt elegendő az egyenletek közti kapcsolatok helyett a gráfkörök közti kapcsolatokat vizsgálni. E vizsgálathoz először meg kell ismernünk az olyan gráfoknak néhány tulajdonságát, amelyekben egyáltalán nincsen kör.

A kör nélküli összefüggő gráfok rajza fához hasonlít, amiért is az ilyen gráfokat fáknak nevezzük (24. ábra).

A szemlélet alapján világosak a fák következő tulajdonságai:

  1. Egy fa két pontját egyetlen olyan úttal lehet csak összekötni, amelyik a fa éleiből van összerakva. (A 24. ábrán a megvastagított élek mutatják a P

    P és Q Q pontokat összekötő utat.)

  2. Ha egy fa két pontját egy új éllel kötjük össze, akkor olyan gráfot kapunk, amelyben pontosan egy kör van (25. ábra).

  3. Minden fa tartalmaz végéleket (a végél olyan él, amelynek egyik végpontjához csak ez az él illeszkedik).

    A 3. tulajdonságból egyszerűen belátható (a végélek egymás utáni elhagyásával végül is egy egyélű fához jutunk), hogy

  4. minden fában a pontok száma 1-gyel több az élek számánál: p=é+1

    p = é + 1 . (p= p = pontok száma, é= é = élek száma)

Ezek után tekintsünk egy tetszőleges, köröket is tartalmazó, összefüggő gráfot (pl. a 19. ábra gráfját). Ha a gráf egyik körének valamelyik élét elhagyjuk, összefüggő gráf marad vissza, és ez a gráf tartalmazza az eredetinek minden csomópontját. Ha az ilyen élelhagyásokat mindaddig ismételjük, ameddig csak kör van a gráfban, akkor olyan kör nélküli gráfhoz jutunk, amelyik összefüggő, és az eredetinek minden csomópontját tartalmazza (26. ábra).

A visszamaradó gráf tehát olyan fa, amely az eredeti gráfnak része, és annak minden csomópontját tartalmazza. Az ilyen fákat az eredeti gráf fa alakú vázainak, röviden favázainak nevezzük. Egy gráfnak általában sok faváza van. (Sokféleképpen választhatjuk ki a köröket, és azokban az elhagyásra szánt éleket.) Minden faváznak azonban ugyanannyi az éle, ti. pontosan eggyel kevesebb, mint ahány csomópontja van az eredeti gráfnak (lásd 4.), s ezért az eredetiből mindig ugyanannyi

é–(p–1)
é ( p 1 )

(é=

é = az eredeti gráf éleinek száma, p= p = az eredeti gráf csomópontjainak száma, p–1= p 1 = a faváz éleinek száma) számú élt kell elhagyni ahhoz, hogy egy faváz maradjon vissza.

(A 26. ábrán é=6

é = 6 , p=4 p = 4 , é–(p–1)=3. é ( p 1 ) = 3 . ) A fák 2.) alatt említett tulajdonsága miatt, ha egy favázhoz visszatesszük bármelyik elhagyott élt, olyan gráfot kapunk, amelynek pontosan egy köre van. Tehát minden elhagyott él a favázzal együtt az eredeti gráfnak pontosan egy körét határozza meg (27. ábra).

Bebizonyítható, hogy egy faváz és a hozzá tartozó elhagyott élek éppen olyan köröket határoznak meg, amelyekhez tartozó egyenletek függetlenek. Ilyen módon bármely faváz segítségével kiválasztható

é–(p–1)
é ( p 1 )

számú független kör-egyenlet. Igazolható, hogy ezek és p–1

p 1 számú csomóponti egyenlet együttvéve is olyan egyenletrendszert alkotnak, amelyben egyik egyenlet sem következménye a többinek. Így tehát éppen

é–(p–1)+(p–1)=é
é ( p 1 ) + ( p 1 ) = é

számú független egyenlethez jutunk; annyi egyenlethez, ahány éle van a gráfnak, azaz ahány ismeretlen intenzitást kell meghatároznunk. Ezekből az egyenletekből kiszámíthatók az áramintenzitások. (Példánkban a (8), (5), (7), (1), (2) és (3) egyenletekből.)

A „9 ösvény” vagy a „3 ház – 3 kút” problémája.  Három házból vezessünk három kúthoz kilenc ösvényt úgy, hogy minden házból minden kúthoz egy-egy ösvény fusson, és az ösvények ne keresztezzék egymást. Ha a házakat és kutakat egy-egy ponttal, az ösvényeket egy-egy vonallal szemléltetjük, akkor az a feladatunk, hogy a 28. ábrán látható „3 ház – 3 kút-gráfot” oly módon rajzoljuk le, hogy az élek közül semelyik kettő se keresztezze egymást. (A gráf 6 csomópontból és 9 élből áll.)

A 29. ábra mutatja, hogy nyolc „ösvényt” még el lehet helyezni kereszteződés nélkül. Ezen az ábrán a hiányzó kilencedik élt, a H_3K_1

H 3 K 1 élt csak úgy lehet megrajzolni, hogy az valamelyik, már megrajzolt élt átmetszi. Bebizonyítható, hogy másféleképpen sem lehet mind a 9 élt úgy megrajzolni síklapon, hogy azok közül legalább kettő ne messe egymást. Ezt röviden úgy fejezzük ki, hogy a 3 ház – 3 kút-gráf nem síkra rajzolható. Ugyancsak igaz, hogy gömbfelületen sem lehet átmetszés nélkül a szóban forgó gráfot megrajzolni. Nem nehéz azonban belátni, hogy egy gyűrűfelületen (mentőöv), valamint egy Möbius-szalagon (egyszer megcsavart szalag, lásd a térképszínezésről szóló és a Csalafinta felületek című cikket!) a 3 ház – 3 kút-gráf megrajzolható úgy, hogy a 9 él ne keresztezze egymást. A térképszínezésről szóló cikkben szerepel a „teljes ötszög” gráfja (30. ábra).

Ebben öt csomópont van, és mindegyik csomópontot egy-egy él köti össze a többi néggyel. Ez a gráf sem rajzolható sem a síkra, sem a gömbfelületre, vagyis nem rajzolható meg úgy ezeken a felületeken, hogy élei ne messék egymást.

A 3 ház – 3 kút-gráf és a teljes ötszög-gráf a „legegyszerűbb”, síkra nem rajzolható gráfok. Igazolható, hogy minden, síkra nem rajzolható gráf tartalmaz vagy a 3 ház – 3 kút-gráfhoz, vagy a teljes ötszög-gráfhoz „hasonló” szerkezetű gráfot. (Kuratowski tétele.) A 31. ábrán

egy 10 csomópontból és 15 élből álló, síkra nem rajzolható gráfot tüntettünk fel. A vastag élek egy, a 3 ház – 3 kút-gráfhoz hasonló szerkezetű gráfot alkotnak benne.