Povzetek
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 ▫$T\boxtimes 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.
Ključne besede
matematika;teorija grafov;celoštevilski pretoki;krepki produkt;poti;cikli;nikjer ničelni pretok;mathematics;graph theory;integer flows;strong product;paths;cycles;
Podatki
Jezik: |
Angleški jezik |
Leto izida: |
2010 |
Tipologija: |
1.01 - Izvirni znanstveni članek |
Organizacija: |
UM FS - Fakulteta za strojništvo |
UDK: |
519.17 |
COBISS: |
15616089
|
ISSN: |
0364-9024 |
Št. ogledov: |
282 |
Št. prenosov: |
28 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Neznan jezik |
Sekundarni naslov: |
NZ-pretoki v krepkem produktu grafov |
Sekundarni povzetek: |
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. |
Sekundarne ključne besede: |
matematika;teorija grafov;celoštevilski pretoki;krepki produkt;poti;cikli;nikjer ničelni pretok; |
URN: |
URN:SI:UM: |
Vrsta dela (COBISS): |
Delo ni kategorizirano |
Strani: |
str. 267-276 |
Letnik: |
Vol. 64 |
Zvezek: |
iss. 4 |
Čas izdaje: |
2010 |
ID: |
1475137 |