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. 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 , 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.

Rekonstrueerimisprobleemi puhul võib rääkida suurimatest alamgraafidest nii tippude  kui ka servade  eemaldamise mõttes. Servade puhul saab rääkida ka väikseimatest ülemgraafidest.

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

Käsitlus isomorfismiklasside baasil

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 .

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 

Graafiteooria