279 KB23 KB200820252016Boiko, TetianaCuno, JohannesImrich, WilfriedLehner, FlorianWoestijne, Christiaan van deštevilka:1letnik:11str. 1-9COBISSID:17836121ISSN:1855-3966URN:URN:NBN:SI:doc-O142F3WIenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaalgorithmsalgoritmifactorizationfaktorizacijagrafigraphsmonoidimonoidsThe Cartesian product of graphs with loops|We extend the definition of the Cartesian product to graphs with loops and show that the Sabidussi-Vizing unique factorization theorem for connected finite simple graphs still holds in this context for all connected finite graphs with at least one unlooped vertex. We also prove that this factorization can be computed in ?$O(m)$? time, where ?$m$? is the number of edges of the given graphDefinicijo kartezičnega produkta razširimo na grafe z zankami in pokažemo, da Sabidussi-Vizingov izrek o enolični faktorizaciji povezanih končnih enostavnih grafov še vedno velja v tem kontekstu za vse povezane končne grafe z najmanj enim vozliščem brez zanke. Pokažemo tudi, da lahko to faktorizacijo izračunamo v ?$O(m)$? časa, kjer je ?$m$? število povezav danega grafaTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije