NZ-flows in strong products of graphsImrich, Wilfried (Avtor) Peterin, Iztok (Avtor) Špacapan, Simon (Avtor) Zhang, Cun-Quan (Avtor) matematikateorija grafovceloštevilski pretokikrepki produktpoticiklinikjer ničelni pretokmathematicsgraph theoryinteger flowsstrong productpathscyclesZa 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.20102015-07-10 15:16:46Delo ni kategorizirano51864sl