Grafovski produkti in prepoznavanje grafovskih svežnjev : doktorska disertacija
Zmazek, Blaž
V prvem poglavju podamo osnovne definicije in pojem predstavitve grafa v obliki kartezičnega grafovskega svežnja. Na osnovnih primerih si ogledamo strukturo kartezičnih grafovskih svežnjev in ...predstavimo postopek za faktorizacijo kartezičnih grafovskih produktov. V drugem poglavju izpeljemo dve novi lastnosti direktnega grafovskega produkta , ki v teoriji grafov zavzema pomembno vlogo. V prvem razdelku se lotimo problema izomorfnosti povezanih komponent direktnega produkta dvodelnih grafov. Predstavimo lastnost faktorjev grafa, ki zagotavlja izomorfnost povezanih komponent. Izkaže se, da je pri določenih pogojih ta lastnost tudi potrebna. V drugem razdelku pokažemo, da "Vizingova" domneva v primeru direktnega produkta ne velja. V tretjem poglavju prevedemo problem prepoznavanja kartezičnega grafovskega svežnja na problem konstrukcije enolično lokalno produktne ekvivalenčne relacije ter zapišemo polinomski algoritem, ki nam iz takšne ekvivalenčne relacije izračuna faktorizacijo kartezičnega grafovskega svežnja. V nadaljevanju podamo lastnosti trakov v kartezičnih grafovskih svežnjih nad baznimi grafi brez trikotnikov s skupno povezavo. S pomočjo lokalnih lastnosti trakov definiramo enolično lokalno produktno ekvivalenčno relacijo ▫$\Delta$▫ in dokažemo pravilnost postopka za njen izračun. Posledica tega postopka je opis kartezičnih grafovskih svežnjev z enolično faktorizacijo. V zadnjem razdelku z dokazom polinomske časovne zahtevnosti postopka za izračun relacije opravičimo njen obstoj. V četrtem poglavju pokažemo, da lahko postopek prepoznavanja kartezičnih grafovskih svežnjev posplošimo na usmerjenin utežen primer. Temeljni rezultat tega poglavja je algoritem za prepoznavanje usmerjenih in uteženih kartezičnih grafovskih svežnjev na treh točkah.
Type of material - dissertation
; adult, serious
Publication and manufacture - Maribor : [B. Zmazek], 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.
