Blaž Zmazek (Avtor), Janez Žerovnik (Avtor)

Povzetek

Predstavljena je posplošitev prepoznavanja kartezičnih grafovskih svežnjev za utežene usmerjene grafe. Osrednji rezultat predstavlja algoritem, ki vrne množice degeneriranih vektorjev vseh predstavitev usmerjenih grafov v obliki uteženih usmerjenih kartezičnih grafovskih svežnjev nad baznimi grafi brez tranzitivnih turnirjev na treh točkah. Temeljna pojma pri izpeljavi tega rezutata sta relacija ▫$\vec{\delta}^\ast$▫ in polkonveksnost. Relacija ▫$\vec{\delta}^\ast$▫, definirana na množici vektorjev usmerjenega grafa, predstavlja posplošitev znane relacije ▫$\delta^\ast$▫. Podgraf ▫$H$▫ je polkonveksen v ▫$G$▫, če ima poljubna točka ▫$x \in G \setminus H$▫ največ enega predhodnika in največ enega naslednika.

Ključne besede

matematika;teorija grafov;grafovski svežnji;kartezični produkt grafov;uteženi digrafi;polkonveksnost;ne zaključna dela;mathematics;graph theory;graph bundles;Cartesian graph product;weighted digraphs;half-convexity;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM FS - Fakulteta za strojništvo
UDK: 519.17
COBISS: 10205960 Povezava se bo odprla v novem oknu
ISSN: 1234-3099
Št. ogledov: 1303
Št. prenosov: 379
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarni naslov: Prepoznavanje uteženih usmerjenih kartezičnih grafovskih svežnjev
Sekundarni povzetek: In this paper we show that methods for recognizing Cartesian graph bundles can be generalized to weighted digraphs. The main result is an algorithm which lists the sets of degenerate arcs for all representations of digraph as a weighted directed Cartesian graph bundle over simple base digraphs not containing transitive tournament on three vertices. Two main notions are used.The first one is the new relation ▫$\vec{\delta}^\ast$▫ defined among the arcs of a digraph as a weighted directed analogue of the well-known relation ▫$\delta^\ast$▫. The second one is the concept of half-convex subgraphs. A subgraph ▫$H$▫ is half-convex in ▫$G$▫ if any vertex ▫$x \in G \setminus H$▫ has at most one predecessor and at most one successor
Sekundarne ključne besede: Teorija grafov;
URN: URN:SI:UM:
Vrsta dela (COBISS): Znanstveno delo
Strani: str. 39-56
Letnik: ǂVol. ǂ20
Zvezek: ǂno. ǂ1
Čas izdaje: 2000
ID: 9595947