FMF, Mathematical Library, Lj. (MAKLJ)
-
Popolni grafi in Bergeova domneva : magistrsko deloDemš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 thesisPublication and manufacture - Ljubljana : [U. Demšar], 1999Language - slovenianCOBISS.SI-ID - 8897625
Author
Demšar, Urška, 1972-
Other authors
Petkovšek, Marko, 1955-
Topics
popolni grafi |
razredi popolnih grafov |
krepka domneva o popolnosti |
perfect graphs |
classes of perfect graphs |
strong perfect graphs
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Call number – location, accession no. ... |
Copy status | Reservation |
---|---|---|
Skladišče-Jadranska 21 0000010941/0000000100 Skladišče-Jadranska 21 10941/100 |
available - reading room
|
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
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:
If the library membership card is not in the list,
add a new one.
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 |
---|---|
Demšar, Urška, 1972- | ![]() |
Petkovšek, Marko, 1955- | 01935 |
Source: Personal bibliographies
and: SICRIS
Select pickup location:
Material pickup by post
Delivery address:
Address is missing from the member's data.
The address retrieval service is currently unavailable, please try again.
By clicking the "OK" button, you will confirm the pickup location selected above and complete the reservation process.
By clicking the "OK" button, you will confirm the above pickup location and delivery address, and complete the reservation process.
By clicking the "OK" button, you will confirm the address selected above and complete the reservation process.
Notification
Automatic login and reservation service currently not available. You can reserve the material on the Biblos portal or try again here later.
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.
Pickup location | Material status | Reservation |
---|
Reservation in progress
Please wait a moment.
Reservation was successful.
Reservation failed.
Reservation...
Membership card:
Pickup location: