Akademska digitalna zbirka SLovenije - logo
ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • Popolni grafi in Bergeova domneva : magistrsko delo
    Demšar, Urška, 1972-
    Leta 1960 je C. postavil definicijo popolnega grafa ko grafa, pri katerem je kromatično število ▫$x(F)$▫ poljubnega induciranega podgrafa ▫$F$▫ enako številu klike ▫$w(F)$▫. Poleg tega je postavil ... dve domnevi: 1. Graf ▫$G$▫ je popolon natanko takrat, ko v njem ni induciranega podgrafa, ki bi bil izomorfen ▫$C2k+1$▫ ali ▫$C2k+1$▫. 2. Graf ▫$G$▫ je popoln natanko takrat, ko je popoln njegov komplement. Ti dve domnevi sta postali znani kot krepka (1.) in šibka (2.) domneva o popolnih grafih. Šibka domneva je bila dokazana kot šibki izrek o popolnih grafih, krepka domneva pa je še danes eden od velikih odprtih problemov teorije grafov. Namen tega magistrskega dela je podati pregled najnovejših odkritij na področju popolnih grafov: najprej predstaviti teoretične osnove tega področja,ki so znane že nekaj časa, nato pa pregledati nove rezultate iz let 1990 - 1998, predvsem tiste, ki se tako ali drugače ukvarjajo s krepko domnevo popolnih grafih. Magistrsko delo je razdeljeno na štiri poglavja: v prvem poglavju se seznanimo z osnovami teorije o popolnih grafih (šibki in polkrepki izrek o popolnih grafih, krepka domneva o popolnih grafih, minimalna popolnost), drugopoglavje prinaša pregled klasičnih skupin popolnih grafov (trianguliarni grafi, primerjalni grafi, intervalni grafi, permutacijski grafi, razcepljeni grafi, grafi s pragom) in nekaterih večjih do sedaj znanih razredov, ki vsebujejo klasične skupine (npr. Meynielovi grafi, grafi brez ▫$K1,3$▫, krepkopopolni grafi, popolno uredljivi grafi, šibko triangulirani grafi). V trtjem poglavju je podan pregled dokazov krepke domneve pod določenimi pogoji oziroma za posebne razrede grafov (predvsem so tu razredi podani s prepovedanimi induciranimi podgrafi ali pa so to skupine grafov s specifično konstrukcijo, kot na primer povezavni grafi) - navedeni so rezultati iz let 1990-1998. Zadnje poglavje vsebuje skico enega izmed novejših poskusov dokaza krepke domneve o popolnosti, ki zagotavlja njeno asimptotično veljavnost. Seveda pa rezultat ne izključuje možnosti, da domneva kljub vsemu morda ne velja.
    Type of material - master's thesis
    Publication and manufacture - Ljubljana : [U. Demšar], 1999
    Language - slovenian
    COBISS.SI-ID - 8897625

Library/institution City Acronym For loan Other holdings
FMF and IMFM, Mathematical Library, Ljubljana Ljubljana MAKLJ reading room 1 cop.
loading ...
loading ...
loading ...