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 UlamUlam, S. M. 1960. A collection of mathematical problems. Wiley, New York. 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
Hüpotees on sõnastatud järgmiselt: "Olgu graafil  p tippu  ja graafil  p tippu , kus p>3. Kui iga tipu puhul on alamgraafid  ja  isomorfsed, siis on graafid  ja  isomorfsed".

Ilmselt oli Ulam huvitatud küsimusest, kas graafi  alamgraafide  hulk sisaldab piisavat teavet graafi enda kohta. Seni on positiivne vastus saadud vaid üksikute graafiklasside kohta nagu McKay poolt kuni 11-tipuliste McKay, B. D. 1997. Small graphs are reconstructible – Australas. J. Combin., 15 (1997), 123–126, 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 rekonstrueeritavadBollobás, B. 1990. Almost every graph has reconstruction number three. – J. Graph Theory, 14 (1990), 1–4.

Rekonstrueerimisprobleemi puhul võib rääkida suurimatest alamgraafidest nii tippude  kui ka servade  eemaldamise mõttesHarary, 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. Servade puhul saab rääkida ka väikseimatest ülemgraafidest.

Vanameistri W. T. Tutte järgi peaks rekonstruktsiooniprobleemi lahenduse otsingud algama just isomorfismiklassidestW. T. Tutte. 1998. Graph Theory As I Have Known It. Clarendon Press, Oxford., mis loob täiesti uue pildi sellest probleemist.

Käsitlus isomorfismiklasside baasil
pisi|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  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 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.

Kommentaarid: a) Iga graaf selles kuueelemendilise struktuuride võres esindab oma isomorfismiklassi ehk struktuuri, mis on esitatud mudeli  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 

Kategooria:Graafiteooria