20.500.12556/DKUM-65352 Recognizing weighted directed Cartesian graph bundles Prepoznavanje uteženih usmerjenih kartezičnih grafovskih svežnjev 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 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. mathematics graph theory graph bundles Cartesian graph product weighted digraphs half-convexity matematika teorija grafov grafovski svežnji kartezični produkt grafov uteženi digrafi polkonveksnost true true true Angleški jezik Slovenski jezik Znanstveno delo 2017-03-31 14:25:23 2017-03-31 14:27:07 2024-09-17 08:56:59 2019-07-11 15:15:30 2000 0 0 str. 39-56 št. 1 Letn. 20 2000 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1234-3099 519.17 7487065 10205960 1234-3099 URN:SI:UM:DK:N75MZMEW Discussiones_Mathematicae_Graph_Theory_2000_Zmazek,_Zerovnik_Recognizing_weighted_directed_cartesian_graph_bundles.pdf Discussiones_Mathematicae_Graph_Theory_2000_Zmazek,_Zerovnik_Recognizing_weighted_directed_cartesian_graph_bundles.pdf 1 B13BFD09296133BCEA4D4844419EDF39 c79105eb2fb642e718c22b86bcf78c09d28dcd83e6f749f98608fb514a9ee2af 0bf5cf9c-7c0e-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=110431 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1105 1 https://dk.um.si/Dokument.php?lang=slv&id=110430 Pedagoška fakulteta 0 0 0