-
Primeri uporabe mostovnih grafov in njihovih posplošitev : doktorska disertacijaDravec, TanjaMostovni grafi so zelo dobro raziskana družina grafov. Pojavljajo se na različnih področjih, ne samo diskretne matematike, na primer v geometrični teoriji grup. V disertaciji se ukvarjamo z ... različnimi problemi, povezanimi z mostovnimi grafi in njihovimi posplošitvami. Pokažemo, do so ti grafi uporabni tudi zunaj same teorije grafov, saj jih povežemo s teorijo kompleksov. Med drugim se ukvarjamo s povezavo teh grafov in določenih tipov konveksnosti v grafih in z uporabo mostovnih grafov v grafih, prirejenih delno urejenim množicam. Disertacija je sestavljena iz treh delov, pri čemer v vsakem delu prikažemo uporabnost mostovnih grafov na izbranem področju. V prvem delu vpeljemo in proučujemo bukolične komplekse, skupno posplošitev sistoličnih in CAT(0) kubičnih kompleksov. Bukolične komplekse proučujemo z vidika teorije grafov, topološkega vidika in iz perspektive geometrijske teorije grup. Okarakteriziramo jih preko določenih lastnosti njihovih 2-skeletov in 1-skeletov (ki jim pravimo bukolični grafi), s čimer posplošimo več že znanih rezultatov. Prav tako dokažemo, da so bukolični kompleksi skrčljivi in da zadoščajo nekim lastnostim tipa nepozitivnih ukrivljenosti. V drugem delu posplošene mostovne grafe obravnavamo vzporedno s 3-Steinerjevo konveksnostjo. In sicer dokažemo, da so grafi $G$, v katerih so j-krogle g_3-konveksne za vsak j % 1, natanko grafi, ki ne vsebujejo hiše niti grafov K_{2,3} in W_4^- kot induciranih podgrafov, in je vsak cikel v G, dolžine vsaj šest, dobro premostljiv. Okarakteriziramo torej grafe z g_3-konveksnimi kroglami. V tretjem delu disertacije usmerimo pozornost na grafe pokritij-neprimerljivosti delno urejenih množic (C-I grafe) in iščemo njihovo povezavo z mostovnimi grafi. Pokažemo, da v razredu C-I grafov sovpada kar nekaj različnih grafovskih družin. In sicer, v razredu C-I grafov ni razlike med mostovnimi grafi, tetivnimi grafi in grafi intervalov. Ker je problem prepoznavanja grafov pokritij-neprimerljivosti v splošnem NP-poln, se osredotočimo na določene razrede mostovnih grafov. Okarakteriziramo tiste delno urejene množice, ki imajo za graf pokritij-neprimerljivosti bločni graf oziroma razcepljeni graf. Med drugim okarakteriziramo grafe pokritij-neprimerljivosti tako med bločnimi oziroma razcepljenimi grafi kot med tetivnimi kografi. Slednje karakterizacije dajo tudi linearen algoritem za prepoznavanje bločnih oziroma razcepljenih grafov, oziroma tetivnih kografov, ki so grafi pokritij-neprimerljivosti.Type of material - dissertation ; adult, seriousPublication and manufacture - [Maribor : T. Gologranc], 2013Language - slovenianCOBISS.SI-ID - 20253192
Link(s):
Digital Library of the University of Maribor – DLUM
Digitalna knjižnica Slovenije - dLib.siDostop z namenskih računalnikov v prostorih NUK
Author
Dravec, Tanja
Other authors
Brešar, Boštjan
Topics
Univerzitetna in visokošolska dela |
kartezični produkt |
mostovni grafi |
retrakt |
amalgamacija |
Steinerjev interval |
delno urejena množica |
disertacije |
cartesian product |
bridged graph |
amalgamation |
retract |
Steiner interval |
poset |
dissertations
Library | Call number – location, accession no. ... | Copy status |
---|---|---|
Miklošič Library FPNM, Maribor | D DIS 51 GOLOGRANC T. Primeri IN: 920130103 |
available - reading room |
University of Maribor Library | Skladišče II 85531 | available - reading room |
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:
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 |
---|---|
Dravec, Tanja | 32028 |
Brešar, Boštjan | 17005 |
Select pickup location:
Material pickup by post
Notification
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.