ALL libraries (COBIB.SI union bibliographic/catalogue database)
13.
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
It was not necessary to add the material to the shelf.
Bibliographic material was successfully added on shelf.
Adding bibliographical material on shelf was not successful.
Material is already on the shelf.
Permalink
URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year
Impact factor
Edition
Category
Classification
JCR
SNIP
JCR
SNIP
JCR
SNIP
JCR
SNIP
Select the library membership card:
DRS,
in which the journal is indexed
Database name
Field
Year
Links to authors' personal bibliographies
Links to information on researchers in the SICRIS system
Subject headings in COBISS General List of Subject Headings
Select pickup location
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
