Ulami hüpotees

Ulami hüpoteesi (inglise keeles Ulam’s Conjecture) nime all tuntud probleem on üks rohket vastukaja leidnud probleemide rühmast, mille tõstatas 1960. aastal Stanisław Ulam^[1]. See on tuntud ka kui rekonstruktsiooniprobleem (inglise: Reconstruction Conjecture) ning puudutab suhteid graafi ja selle suurimate alamgraafide vahel. Graafiteoorias on see üks põhiprobleemidest.

Klassikaline käsitlus[muuda | muuda lähteteksti]

Hüpotees on sõnastatud järgmiselt: "Olgu graafil $G$ p tippu $v$ ja graafil $H$ p tippu $u$ , kus p>3. Kui iga tipu puhul on alamgraafid $G\setminus v$ ja $H\setminus u$ isomorfsed, siis on graafid $G$ ja $H$ isomorfsed".

Ilmselt oli Ulam huvitatud küsimusest, kas graafi $G$ alamgraafide $G\setminus v$ hulk sisaldab piisavat teavet graafi enda kohta. Seni on positiivne vastus saadud vaid üksikute graafiklasside kohta nagu McKay poolt kuni 11-tipuliste ^[2], samuti regulaarsete-, intervall-, mittesidusate graafide, teede ja mõnede väga spetsiifiliste kohta. Miks?

Bollobás näitas tõenäosuse seisukohalt, et kõik graafid on rekonstrueeritavad^[3].

Rekonstrueerimisprobleemi puhul võib rääkida suurimatest alamgraafidest nii tippude $G\setminus v$ kui ka servade $G\setminus e$ eemaldamise mõttes^[4]. Servade puhul saab rääkida ka väikseimatest ülemgraafidest.

Vanameistri W. T. Tutte järgi peaks rekonstruktsiooniprobleemi lahenduse otsingud algama just isomorfismiklassidest^[5], mis loob täiesti uue pildi sellest probleemist.

Käsitlus isomorfismiklasside baasil[muuda | muuda lähteteksti]

Näide: kuueelemendiliste struktuuride süsteemi võre esimene pool

Isomorfismiklass kujutab endast isomorfsete graafide hulka. Isomorfsed graafid omavad üht ja sama struktuuri. See struktuur on kujutatav kanooniliselt vastava semiootilise mudeli $S$ näol. Igal graafil (struktuuril) on oma suurimad alamgraafid (alamstruktuurid) ja väikseimad ülemgraafid (ülemstruktuurid) mis saadakse vastavalt serva (seose) eemaldamisel või lisamisel. Kõik n-tipulised graafid (n-elemendilised struktuurid) moodustavad mitteisomorfsete graafide süsteemi mille elementideks on struktuurid (vastavat isomorfismiklassi esindavad graafid) ja seosteks struktuuridevahelised seosed ^[6]^[7].

Kommentaarid: a) Iga graaf selles kuueelemendilise struktuuride võres esindab oma isomorfismiklassi ehk struktuuri, mis on esitatud mudeli $S$ näol. b) Iga struktuur selles võres on mõne(de) teise (teiste) struktuuri(de) suurim alamstruktuur või väikseim ülemstruktuur. c) Iga struktuur on dekomponeeritav oma suurimateks alamstruktuurideks või komponeeritav oma väikseimateks ülemstruktuurideks. d) Iga struktuur on rekonstrueeritav (taastatav) oma nii oma suurimate alamstruktuuride kui ka väikseimate ülemstruktuuride baasil. e) Esitatud struktuuride täiendid asuvad sümmeetriliselt selle võre teises pooles. f) Kuueelemendiliste struktuuride (mitteisomorfsete graafide) arv on 156.

Kõik struktuurid (graafid) kuuluvad niisugustesse võredesse. Rekonstruktsiooniprobleem seisneb siin vaid küsimuses: Kas erinevad struktuurid saavad omada ühesuguseid suurimaid alamstruktuure ja väikseimaid ülemstruktuure. Sellele probleemile üksikute graafiklasside pidi lähenemine oleks absurdne.

Viited[muuda | muuda lähteteksti]

↑ Ulam, S. M. 1960. A collection of mathematical problems. Wiley, New York
↑ McKay, B. D. 1997. Small graphs are reconstructible – Australas. J. Combin., 15 (1997), 123–126
↑ Bollobás, B. 1990. Almost every graph has reconstruction number three. – J. Graph Theory, 14 (1990), 1–4
↑ Harary, F. 1964. On the reconstruction of a graph from a collection of subgraphs. – Theory of Graphs and its Applications - Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 47–52
↑ W. T. Tutte. 1998. Graph Theory As I Have Known It. Clarendon Press, Oxford.
↑ J.-T. Tevet. 2002. Isomorphism and Reconstructions of the Graphs: A constructive approach and development. S.E.R.R., Tallinn.
↑ J.-T. Tevet. 2009. Graafide varjatud külgi. S.E.R.R., Tallinn. ISBN 9789949213108

[1] Ulam, S. M. 1960. A collection of mathematical problems. Wiley, New York

[2] McKay, B. D. 1997. Small graphs are reconstructible – Australas. J. Combin., 15 (1997), 123–126

[3] Bollobás, B. 1990. Almost every graph has reconstruction number three. – J. Graph Theory, 14 (1990), 1–4

[4] Harary, F. 1964. On the reconstruction of a graph from a collection of subgraphs. – Theory of Graphs and its Applications - Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 47–52

[5] W. T. Tutte. 1998. Graph Theory As I Have Known It. Clarendon Press, Oxford.

[6] J.-T. Tevet. 2002. Isomorphism and Reconstructions of the Graphs: A constructive approach and development. S.E.R.R., Tallinn.

[7] J.-T. Tevet. 2009. Graafide varjatud külgi. S.E.R.R., Tallinn. ISBN 9789949213108

[1]

[2]

[3]

[4]

[5]

[6]

[7]