Véges ponthalmazok legrövidebb hálózatai Kábelrakás kis költséggel

Véges ponthalmazok legrövidebb hálózatai Kábelrakás kis költséggel Bessenyei Mihály U.M. Debreceni Egyetem, Matematikai Intézet, Analízis Tanszék

(Szabó Gréta egyetemi hallgatóval közös munka alapján) Medve Matektábor, Pusztafalu, 2016. július 19.

Bessenyei Mihály és Szabó Gréta

Kábelrakás kis költséggel

Legrövidebb hálózat a négyzethez

Feladat Négy település egy négyzet csúcsaiban helyezkedik el. Kössük össze a településeket Ethernet kábellel a lehet® legkevesebb költséggel!



Legrövidebb hálózat a négyzethez zikus módra Analógia egy dimenzóval magasabb néz®pontból Meghatározandó az egységkocka éleire fölfeszül® minimális felszín¶ felület. A megoldást a kocka élhálózatának szappanos vízbe merítésével modellezhetjük. A kapott konguráció eredeti síkbeli problémánkra az alábbi elrendez®dést (topológiát) sejteti:



Legrövidebb hálózat a négyzethez zikus módra A lokalitási elv Kérdés még a kapott topológia elhelyezkedése (geometriája). Ehhez elegend® ismerni, hogy a csomópontokban milyen szög alatt futnak be az élek. Ha az el®bbi elhelyezkedés valóban minimum, akkor bármelyik csomópont kis környezetében is minimumot szolgáltat. Kérdés tehát, hogy három pont hogyan köthet® össze legrövidebb hálózattal. Toricelli asztala Egy asztal lapjára három lyukat fúrunk, melyeken azonos hosszúságú zsineget f¶zünk át. Az asztallap fölött a zsinegeket összecsomózzuk, majd a csomópontot és a lelógó zsinegvégeket is azonos súllyal terheljük. Energiaminimum elve: a zsinegek összhossza az asztalon minimális. Newton II. törvénye: a csomópontban az élek szöge 2π/3. Vagyis: három pont legrövidebb hálózatát (optimális kongurációját) az úgynevezett izogonális pont felvételével nyerjük. Bessenyei Mihály és Szabó Gréta


Legrövidebb hálózat a négyzethez matematikus módra Tétel Ha ABC olyan háromszög, melynek minden szöge kisebb, mint 2π/3, akkor a PA + PB + PC érték az izogonális pont választása mellett minimális. Tétel Az egységnégyzet négy csúcsát összeköt® legrövidebb hálózat az el®bb √ látott lényegében egyértelm¶ konguráció. Ennek teljes hossza 1 + 3. Bizonyítás A hálózat olyan fagráf, melynek minden éle egyenes szakasz. Lokalitás elv el®ször: alappontból egy és csak egy él indulhat. Lokalitás elv másodszor: csomópontban három él fut össze. Fagráfban

c

= e + 1, így két csomópont beiktatása szükséges.



Véges ponthalmaz legrövidebb hálózata

Tétel Ha H véges síkbeli ponthalmaz, G(V , E ) ennek legrövidebb hálózata, akkor

G(V , E ) ⊂ conv(H ) és

H

⊂ V;

G(V , E ) olyan fagráf, melynek élei egyenes szakaszok; minden alappontból legfeljebb három él indul; minden csomópontból pontosan három él indul; élek csak

V

pontjaiban találkozhatnak és legalább 2π/3 szögben.

Továbbá, ha H térbeli halmaz, akkor a föntiek mellett még az is teljesül, hogy a csomópontból induló három él közös síkban van. Végezetül, a csomópontok száma legalább kett®vel kevesebb az alappontok számánál.



Legrövidebb hálózat a szabályos ötszöghöz Tétel A szabályos ötszög legrövidebb hálózata az a lényegében egyértelm¶en meghatározott fagráf, melynek élei egyenes szakaszok, az alappontok foka egy, három darab három fokú csomópontot tartalmaz, és az élek páronként azonos szög alatt találkoznak.



Legrövidebb hálózat a szabályos hatszöghöz Megengedett kongurációk Szabályos hatszög legrövidebb hálózatában vagy minden alappontból egy él indul, vagy két alapponttól eltekintve mindegyikb®l kett®. Az els® esetben négy csomópont beiktatása szükséges, és lényegében két ilyen konguráció létezik:



Legrövidebb hálózat a szabályos hatszöghöz Tétel A szabályos hatszög legrövidebb hálózatát a kerület mentén haladó, egy oldalt nem tartalmazó töröttvonal származtatja:



Legrövidebb hálózat a szabályos tetraéderhez Tétel A szabályos tetraéder legrövidebb hálózata az a lényegében egyértelm¶en meghatározott fagráf, melynek élei egyenes szakaszok, az alappontok foka egy, két darab három fokú csomópontot tartalmaz, és√az élek √ páronként azonos szög alatt találkoznak. Ennek teljes hossza 2/2 − 3/3.



Irodalom Cockayne, E. J., On (1967), 431450.

, Canad. Math. Bull., 10

the Steiner problem

Gilbert, E. N. and Pollak, H. O., Appl. Math., 16 (1968), 129.

Steiner minimal trees

, SIAM J.

Hwang, F. K. and Richards, D. S. and Winter, P., The Steiner tree , Ann. Discrete Math., 53 (1992), North-Holland Publishing Co., Amsterdam. problem

Jarník, V. and Kössler, O., 0 minimálních grafech obsahujících daných bodu, as. P¥stování Mat., 63 (1934) 223235. Korte, B. and Ne²et°il, J., Vojt¥ch Jarnik's work in optimization, Discrete Math., 235 (2001), 117. Melzak, Z. A., On (1961), 143148. Pólya Gy.,

n

combinatorial

, Canad. Math. Bull., 4

the problem of Steiner

, Gondolat Kiadó, Budapest, 1988.

Indukció és analógia



Véges ponthalmazok legrövidebb hálózatai Kábelrakás kis költséggel

Recommend Documents