20.500.12556/DKUM-51864 NZ-flows in strong products of graphs NZ-pretoki v krepkem produktu grafov Za krepki produkt ▫$G_1 boxtimes G_2$▫ grafov ▫$G_1$▫ in ▫$G_2$▫ dokažemo, da je ▫${mathbb{Z}}_3$▫-pretočno kontraktibilen natanko tedaj, ko ▫$G_1 boxtimes G_2$▫ ni izomorfen ▫$Tboxtimes K_2$▫ (kar poimenujemo ▫$K_4$▫-drevo), kjer je ▫$T$▫ drevo. Sledi, da za ▫$G_1 boxtimes G_2$▫ obstaja NZ 3-pretok, razen če je ▫$G_1 boxtimes G_2$▫ ▫$K_4$▫-drevo. Dokaz je konstruktiven in implicira polinomski algoritem, ki nam vrne NZ 3-pretok, če ▫$G_1 boxtimes G_2$▫ ni ▫$K_4$▫-drevo, oziroma NZ 4-pretok sicer. We prove that the strong product ▫$G_1 boxtimes G_2$▫ of ▫$G_1$▫ and ▫$G_2$▫ is ▫${mathbb Z}_3$▫-flow contractible if and only if ▫$G_1 boxtimes G_2$▫ is not ▫$T boxtimes K_2$▫, where ▫$T$▫ is a tree (we call ▫$T boxtimes K_2$▫ a ▫$K_4$▫-tree). It follows that ▫$G_1 boxtimes G_2$▫ admits an NZ 3-flow unless ▫$G_1 boxtimes G_2$▫ is a ▫$K_4$▫-tree. We also give a constructive proof that yields a polynomial algorithm whose output is an NZ 3-flow if ▫$G_1 boxtimes G_2$▫ is not a ▫$K_4$▫-tree, and an NZ 4-flow otherwise. matematika teorija grafov celoštevilski pretoki krepki produkt poti cikli nikjer ničelni pretok mathematics graph theory integer flows strong product paths cycles true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 15:16:46 2015-07-10 15:16:46 2022-05-31 03:08:20 2019-07-11 07:30:29 2010 0 0 str. 267-276 iss. 4 Vol. 64 2010 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 25747712 15616089 0364-9024 URN:SI:UM:DK:AIHBFNKY http://dx.doi.org/10.1002/jgt.20455 1 https://dk.um.si/Dokument.php?lang=slv&id=76424 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0