bélyegkép|364x364px|Egy gyökerezett fák sorozata, amelyeket egy 3 címkéből álló halmazból címkéznek (kék < piros < zöld). A sorozat n-edik fája legfeljebb n csúcsot tartalmaz, és egyik fa sem ágyazható be végtelenül a sorozat későbbi fáiba. A azt a leghosszabb lehetséges sorozathosszat jelöli, amely egy ilyen sorozat esetén előfordulhat. A Kruskal-tétel a matematikában, különösen a gráfelmélet területén egy alapvető fontosságú állítás, amely az optimális faépítési problémák megoldására ad választ. A tételt Joseph Kruskal amerikai matematikus fogalmazta meg 1956-ban, és fő alkalmazási területe a minimális feszítőfa keresése egy súlyozott, összefüggő gráfban. A Kruskal-tétel alapján egy súlyozott gráf minimális feszítőfája úgy határozható meg, hogy a gráf éleit a súlyuk alapján növekvő sorrendbe rendezzük, majd ezen élek közül iteratívan kiválasztjuk azokat, amelyek a már meglévő struktúrához hozzáadva nem képeznek kört. Az így létrejövő fa a gráf minden csúcsát tartalmazza, miközben az élek összsúlya minimális marad.

A tétel a matematikai optimalizáció és a számítástechnika számos területén alkalmazható, különösen a hálózatok elemzésében, útvonaltervezésben és adatstruktúrák kezelésében. Például használható elektromos hálózatok tervezésére, ahol a cél a költségek minimalizálása, vagy logisztikai problémákban, ahol a legrövidebb összekötő útvonalakat keresik.

A tétel jelentősége túlmutat az egyszerű algoritmikus megoldásokon, mivel szorosan kapcsolódik a gráfelmélet alapvető fogalmaihoz, mint a körmentesség, összefüggőség és súlyozott élek szerepe. Ezen kívül jól szemlélteti az algoritmusok hatékonyságának és helyességének kombinációját, mivel Kruskal algoritmusa viszonylag egyszerű, mégis robusztus megoldást kínál nagy méretű problémák esetén is.

Történet A Kruskal-tétel története a 20. század közepére nyúlik vissza, amikor a matematikusok a gráfelmélet egyre bővülő alkalmazási lehetőségeivel kezdtek foglalkozni. A tételt 1956-ban fogalmazta meg Joseph Kruskal, aki a Princeton Egyetemen dolgozott, és a matematikai optimalizáció, valamint a gráfelmélet iránti érdeklődése vezetett a felfedezéshez. Kruskal ezt az elméletet az optimális faépítés problémájának megoldására hozta létre, és ezzel alapvető szerepet játszott a gráfok kezelésére szolgáló algoritmusok fejlesztésében.

A gráfelméletben egy "feszítőfa" olyan fákra vonatkozik, amelyek összekötnek minden csúcsot egyetlen összefüggő gráfban, miközben nincsenek benne körök. A minimális feszítőfa a gráf minden csúcsát tartalmazó feszítőfa, amely az élek összsúlyát minimalizálja. Az ilyen problémák rendkívül fontosak számos területen, például a számítógépes hálózatok tervezésében, a közlekedési rendszerek optimalizálásában és más logisztikai feladatokban. A Kruskal-tétel tehát nemcsak elméleti szempontból, hanem a gyakorlati alkalmazásokban is kiemelkedő jelentőséggel bír.

Joseph Kruskal maga is tisztában volt az algoritmus gyakorlati hasznával, amikor a tételt kifejlesztette. Az ötletet egy egyszerű, de hatékony algoritmus formájában tette közzé, amely képes a gráfok minimális feszítőfáját megtalálni anélkül, hogy bonyolultabb számításokra lenne szükség. Az algoritmus lépései a következők: először rendezzük az éleket növekvő sorrendbe súlyuk alapján, majd kezdjük el egyesével hozzáadni őket a feszítőfa szerkezetéhez, ügyelve arra, hogy mindig csak olyan élt adjunk hozzá, amely nem okoz kört a már meglévő struktúrában. Ezt az eljárást addig ismételjük, amíg az összes csúcs össze nem lesz kötve. A tétel alapvető eredménye, hogy az így kapott feszítőfa a lehető legkisebb súlyú lesz.

Kruskal munkája közvetlenül kapcsolódik a gráfelmélet és az algoritmusok fejlődéséhez. Az algoritmus megalkotása előtt a minimális feszítőfa keresése összetett feladatnak tűnt, és az elérhető megoldások nem biztosítottak hatékony módszert a nagyobb gráfok kezelésére. Kruskal módszere azonban egyszerűsítette ezt a problémát, és még ma is az egyik legfontosabb algoritmus a gráfelméletben. A tétel alkalmazása lehetővé tette, hogy a tudósok gyorsabban és hatékonyabban oldjanak meg különböző hálózati problémákat, például az internetes adatátviteli útvonalak optimalizálását, vagy éppen az elektromos hálózatok kiépítését.

A Kruskal-tétel különösen az 1960-as években vált népszerűvé, amikor a számítógépes tudományok gyors fejlődése lehetővé tette a matematikai elméletek gyorsabb alkalmazását. A tétel széles körben alkalmazható különböző adatstruktúrákhoz, és ma már alapvető része a számítógépes programozásnak. Az algoritmus megvalósítása gyors, és jól skálázható nagyobb problémákra is, ezért a gráfok kezelésében egy nélkülözhetetlen eszközzé vált.

A tétel hatása nem csupán a matematikai és informatikai közösségekben volt jelentős, hanem a tudományos élet más területein is. A Kruskal-tétel alkalmazása hozzájárult a logisztikai és közlekedési rendszerek hatékonyabbá tételéhez, a hálózati infrastruktúrák optimalizálásához, és még az internet fejlődésében is szerepet játszott. Az algoritmus hatékonysága és egyszerűsége lehetővé tette a tudósok számára, hogy könnyebben oldjanak meg olyan problémákat, amelyek korábban bonyolult számításokat igényeltek.

Kruskal fatétele (Nash-Williams bizonyítása alapján) A következőkben a Kruskal-fatételnek azt a változatát ismertetjük, amelyet Nash-Williams bizonyított; maga Kruskal kicsit általánosabb formában fogalmazta meg az eredményt. Minden vizsgált fa véges, és gyökerezettnek tekintjük őket.

Előzetes fogalmak

Gyökerezett fa Legyen egy véges fa kiválasztott gyökérrel. A fa csúcsait jelöljük stb. betűkkel. Utód és közvetlen utód Utód: Adott egy gyökerezett fa . Legyen és két csúcs -ben. Azt mondjuk, hogy „ utódja -nek”, ha a gyökértől -ig vezető egyetlen egyszerű út tartalmazza is. Közvetlen utód: Azt mondjuk, hogy „ közvetlen utódja -nek”, ha w utódja -nek, és a -től w-ig vezető úton semmilyen más csúcs nem szerepel (azaz és élszomszédok a fában). Részben rendezett halmaz (poset) Legyen egy részbenrendezett halmaz (angolul partially ordered set, rövidítve poset). Ez azt jelenti, hogy -ben létezik egy reláció, amely reflexív, antiszimmetrikus és tranzitív, de nem feltétlen totális. Címkézett gyökeres fa Azt mondjuk, hogy egy gyökeres fa „-beli címkékkel ellátott”, ha a fa minden egyes csúcsa kap egy címkét -valamely eleméből. Ez lehet például egy szám, betű, rendezett pár, stb., melyeknek egymáshoz való viszonyát a reláció határozza meg.

Inf-beágyazhatóság (inf-embeddable) reláció Legyen és két, -beli címkékkel ellátott gyökerezett fa. Azt mondjuk, hogy

(„ beleágyazható -be” vagy inf-embeddable -be), ha létezik egy injektív leképezés

,

amely kielégíti a következő feltételeket:

1. Címkék rendezése

Minden csúcsra -ben igaz, hogy címkéje (megelőzi vagy egyenlő) az címkéjét -ben.

(Nash-Williams bizonyítása esetén a „megelőzi” azt jelenti, hogy a címke relációban nem nagyobb. Gyakran erősebb változatban – Kruskal leírásában – megkövetelik, hogy szigorúan kisebb, rendezési értelemben megelőző legyen, ám a lényeget ez nem változtatja meg.)

2. Utódviszony megtartása

Ha utódja -nek -ben, akkor is utódja -nek -ben. Magyarul: ha w a gyökértől -ig vezető útban tartalmazza -t, akkor ugyanez a viszony fennáll a leképezett csúcsoknál is.

3. Különböző közvetlen utódok képe

Ha és két különböző, közvetlen utódja -nek -ben, akkor a -ben és közötti útnak tartalmaznia kell -t. Ez azt fejezi ki, hogy a képfában is „közvetlen szülőként” (őscsúcs) jelenik meg a megfelelő csúcsokhoz. Ha ez nem teljesülne, akkor F(v)nem lenne közös csúcs a két útban, azaz megsérülne a gyökeres szerkezet megfelelő leképezése.

Kruskal fatétele A Kruskal fatétele (Nash-Williams bizonyítása alapján) a következő állítást mondja ki:

Tétel. Ha jól-kvázi-rendezett (angolul well-quasi-ordered, rövidítve ), akkor az -beli címkékkel ellátott minden véges gyökeres fa halmaza is jól-kvázi-rendezett a fent definiált (inf-beágyazhatósági) reláció szerint.

Mit jelent a jól-kvázirendezés (WQO)?

Az halmaz jól-kvázi-rendezett azt jelenti, hogy semmilyen végtelen szigorúan csökkenő sorozat vagy végtelen antichain (páronként összehasonlíthatatlan elemek sorozata) nem létezik -ben. Informálisan: nem lehet a végtelenségig „lefelé” menni a relációban, és nem lehet végtelen sok olyan elemet választani, amelyek közül egyik sem áll relációban a másikkal.

A tétel értelmezése:

Vegyünk egy tetszőleges végtelen sorozatot gyökeres fákkal:

ahol minden T_i egy -beli címkékkel ellátott gyökeres fa, és jól-kvázi-rendezett. Kruskal tétele szerint ebben a végtelen sorozatban mindig találunk két indexet, -t, amelyre

vagyis inf-beágyazható -be a fent definiált módon. Ez rokon szellemiségű eredmény a híres Higman-tétellel és a jólrendezési problémák több más klasszikus tételével, amelyek a „nem lehet végtelen, reláció alá nem rendezhető struktúrákat létrehozni” szemléletre építenek.

Kruskal eredeti megfogalmazása kicsit tágabb kontextusban kezeli a jelölési és a rendezési viszonyokat, például a címkék közti relációkban is lehetnek finomabb feltételek. Ezenkívül az is eltérés, hogy Kruskal egyes változataiban a címkék összehasonlításához szigorúbb rendezési feltételek társulnak, illetve a fákat akár szélsőségesebb módokon is lehet az inf-beágyazhatósággal vizsgálni. A Nash-Williams-féle bizonyítás elsősorban a lényeget ragadja meg, és már így is meglepően erős állítást ad.

Állítás Az itt bemutatott verziót Nash-Williams bizonyította; Kruskal megfogalmazása valamivel erősebb. Az összes vizsgált fa véges.

Adott egy gyökérrel rendelkező fa , valamint csúcsai és . Nevezzük w-t utódjának, ha a gyökértől w-ig vezető egyedi út tartalmazza -t, és közvetlen utódjának, ha ezen kívül az -tól -ig vezető út nem tartalmaz más csúcsot.

Tegyük fel, hogy részben rendezett halmaz. Ha és gyökeres fák, melyek csúcsai -beli címkékkel vannak ellátva, akkor azt mondjuk, hogy inf-beágyazható -be, és írjuk ≤-ként, ha létezik csúcsainak csúcsaiba képező injektív leképezés F, amelyre igaz, hogy:

T1 minden v csúcsára v címkéje megelőzi F(v) címkéjét; Ha -nak bármely utódja -ben, akkor -nak is utódja -ben; Ha és -nak két különböző közvetlen utódja, akkor az -tól -ig vezető út -ben tartalmazza -t.

Kruskal fa-tétele kimondja:

Ha jól kvázi-rendezett, akkor a -beli címkékkel ellátott gyökeres fák halmaza jól kvázi-rendezett az itt definiált inf-beágyazható rendezés szerint. (Másképpen megfogalmazva: ha adott ,,… végtelen sorozata -beli címkékkel ellátott gyökeres fáknak, akkor létezik olyan , hogy .)

Gyenge fa függvény

Legyen P(n) az alábbi állítás:

Létezik olyan m , hogy ha véges sorozata címkézetlen gyökeres fáknak, ahol -nek csúcsa van, akkor található , amelyre teljesül.

A állítások mindegyike igaz Kruskal tételéből és König lemmájából következően. Minden n -re a Peano-aritmetika bizonyítani tudja, hogy igaz, de a Peano-aritmetika nem képes bizonyítani az állítást, hogy „ igaz minden -re” .

Továbbá, a legrövidebb bizonyításának hossza a Peano-aritmetikában rendkívül gyorsan nő n -nek függvényében, sokkal gyorsabban, mint bármely primitív rekurzív függvény vagy például az Ackermann-függvény.

A TREE függvény A TREE függvényt Harvey Friedman definiálta címkék bevonásával, ami egy rendkívül gyorsan növekedő függvényt eredményezett.

Definíció

Legyen a legnagyobb , amelyre az alábbi feltételek teljesülnek:

• Létezik gyökeres fákból álló sorozat, amelyek -elemű címkekészlettel vannak címkézve.

• Minden -nek legfeljebb csúcsa van.

• Az bármely pár esetén (azaz inf-beágyazható -be) nem teljesül.

Példák és növekedési ütem

•

•

• : Olyan rendkívül nagy szám, hogy összehasonlíthatatlanul nagyobb Graham számánál és sok más hatalmas kombinatorikus konstansnál.

Alsó becslések

• Egy alsó becslés -ra , ahol az Ackermann-függvény. Ez az érték megközelítőleg , ahol Graham-függvényt jelöl.

Miért jelentős?

• Robbanásszerű növekedés: Míg a és értékei kis számok, exponenciálisan meghaladja a legtöbb ismert nagy számot, beleértve Friedman , , és Graham számát is.