A meglepő válasz az, hogy nem, ha csak elméleti kérdés nincs a dolgozatban, fölösleges megtanulni (!) őket. A helyettük alkalmazható gyorsabb, hibamentesebb és determinisztikusabb megvalósítás kerül most ismeretésre, amely még az általános mosópornál is hatékonyabb.
A feladattípus egy látszólag kezelhetetlen kapcsolás eredő ellenállásának kiszámítása. A felhasznált módszerek:
soros kapcsolás helyettesítése az eredő ellenállással
párhuzamos kapcsolás helyettesítése az eredő ellenállással
háromszög-csillag átalakítás
Az állítás az, ezek ismételt alkalmazásával (a Kirchoff-egyenletek gubancos természetének mélyebb ismerete nélkül) minden példatári eredő ellenállásos példa megoldható. A bizonyítás úgy történik, hogy adunk egy algoritmust, és belátjuk, hogy az véges sok lépésen belül helyes eredményt ad.
Az algoritmus:
Mostantól kezdve olyan példát nevezünk példatári példának, amelyben legfeljebb 11 db ellenállás van és a kapcsolás síkba (könyvlapra) rajzolható. Aki ennél bonyolultab feladatok megoldására adja a fejét, annak úgy sincs szüksége arra, hogy ezt a cikket elolvassa. Mellesleg kísérletileg igazolható, hogy ez az önkényes definíció megállja a helyét.
A helyességhez elég belátni, hogy
(1) A 3. lépéshez nem érünk el végtelen sokszor.
(2) A 3. lépésben mindig találunk háromszöget.
(1) igazolása: Az 1. lépés csökkenti az ellenállások számát, a 3. lépés csökkenti a háromszögek számát (vegyük észre, hogy a 3. lépés új háromszöget nem csinál). Ezek közül egyik sem ismétlődhet végtelen sokszor, mert különben 0-nál is kevesebb ellenállás vagy háromszög maradna.
(2) igazolása: Elég belátni, hogy a 3. lépésben sosem érünk olyan gráfhoz (elrendezéshez), melyben minden lapnak (kör (hurok), melynek belsejében nincs további ellenállás) legalább 4 éle (ellenállása) van (ekkor ugyanis van egy olyan lap, melynek legfeljebb 3 éle van, ez a 3 él egy háromszöget alkot, az átalakítás tehát elvégezhető). Az 1. lépés miatt ez a gráf, melyről be akarjuk látni, hogy nem létezik következő két tulajdonsággal rendelkezik:
(3) Minden csúcsból legalább 3 él indul ki.
(4) Minden lapon legalább 4 él van.
Ha é, l, c jelöli az élek, lapok és csúcsok számát, (3) miatt é>=3*c/2, (4) miatt pedig é>=4*l/2. (A kettes osztó azért van ott, mert minden él egyszerre két csúcshoz és két laphoz tartozik). Az Euler-tétel kimondja, hogy síkba rajzolható gráfokra:
(5) l+c=é+2
l-t és c-t felülről becsülve:
(6) é+2=l+c<=é/2+2*é/3
átrendezve:
é>=12
Ez viszont azt jelenti, hogy a kapcsolásban legalább 12 db ellenállás van, ami nem lehet, hiszen az elején feltettük, hogy az ellenállások száma legfeljebb 11.
Ezzel ellentmondásra jutottunk, tehát nem létezik olyan példatári kapcsolás, amelynél a módszerünk csődöt mondana. Q.E.D.
Továbbgondolás: A haladottabb olvasó ilyenkor felteheti a kérdést, hogy mi van a legalább 12-ellenállásos példákkal? Az igaz, hogy könnyen lehet mutatatni olyan 12 ellenállásból álló elrendezést, melyre (2) nem teljesül, és a módszer használhatatlan. Ilyen például a kocka síkba lapított testhálója. Az is igaz viszont, hogy kis finomítással ez a 12-es korlátozás feloldható. Íme:
A háromszög-csillag átalakítás helyett az ötszög-nagycsillag átalakítást használjuk. Ez (az előzőhöz hasonlóan) egy üres ötszögből csinál egy ötágú csillagot közepén a 0 csúccsal. A 0 és a többi csúcs közti helyettesítő ellenállások a következő képletből adódnak:
R1=(R51*R12+R12*R34+R51*R34-R23*R45)/(R12+R23+R34+R45+R51)
R2=(R12*R23+R23*R45+R12*R45-R34*R51)/(R12+R23+R34+R45+R51)
R3=(R23*R34+R34*R51+R23*R51-R12*R45)/(R12+R23+R34+R45+R51)
R4=(R34*R45+R45*R12+R34*R12-R51*R23)/(R12+R23+R34+R45+R51)
R5=(R45*R51+R51*R23+R45*R23-R12*R34)/(R12+R23+R34+R45+R51)
A látszat ellenére könnyű megjegyezni: A nevezőbe az összeg kerül, a számlálóban 3 kettős szorzat összegéből kivonva egy kettős szorzat. A kivonandó indexei azokat a számjegyeket tartalmazzák, amelyeket az eredmény nem (pl R1 esetén 2,3,4,5). A számlálóban lévő összeg 3 fajta R-t tartalmaz: az első kettő az, amelyiket az eredmény is (pl R1 esetén 12,51), a harmadik pedig ami az előző kettőből kimaradt (3 és 4). Szerepel az első két szám szorzata egymással és a harmadik számmal. Mindössze ennyi.
Az, hogy ez a képlet helyes, ugyanúgy látható be, mint a Holics-ban a háromszög-csillag átalakítás helyességének bizonyítása. A végén ugyanúgy össze kell adni majd kivonni egymásból az egyenleteket és a fent vázolt eredményt kapjuk.
A kérdés már csak az, mire jó ez. Először is arra, hogy ha a gráfban van háromszög, négyszög vagy ötszög, akkor az ötszög-nagycsillag átalakítás képes ezt eltüntetni (háromszög esetén 3=4=5; négyszög esetén 4=5), tehát az eredeti algoritmus 3. lépését erre érdemes kicserélnünk.
A helyességhez elég belátni, hogy mindig találunk ilyen háromszöget, négyszöget vagy ötszöget, azaz nem létezik olyan síkba rajzolható gráf, melynek minden lapja legalább hat élt tartalmaz. Ezt viszont Euler óta tudjuk, bizonyítása szögszámolással történik és megtalálható az összes gráfelmélet-könyvben.
1997.
Budaörs, Magyarország.
Ez a lap pts oldalai közül való.