Št. zadetkov: 18
Video in druga učna gradiva
Oznake:
mathematics;graph theory
Products of graphs allow a rather compressed coding from the data structure point of view and often transparent graphical representations. Graphs that differ little from products in the sense that addition or deletion of a small number of edges turns them into a product offer similar advantages.
Leto:
2005
Vir:
videolectures.net
Izvirni znanstveni članek
Oznake:
matematika;teorija grafov;razlikovalno število;grafovski avtomorfizem;produkti grafov;mathematics;graph theory;distingushing number;graph automorphism;products of graphs;
Razlikovalno število ▫$D(G)$▫ grafa je najmanjše celo število ▫$d$▫, za katero obstaja taka ▫$d$▫-označitev točk grafa ▫$G$▫, da je ne ohranja noben avtomorfizem grafa ▫$G$▫. Dokažemo, da je razlikovalno število kvadrata in višjih potenc povezanega grafa ▫$G \ne K_2, K_3$▫, glede na kartezični produ ...
Leto:
2006
Vir:
Pedagoška fakulteta (UM PEF)
Izvirni znanstveni članek
Oznake:
matematika;teorija grafov;kartezični produkt grafov;linearni algoritem;razcep;mathematics;graph theory;Cartesian product graphs;linear algorithm;decomposition;
We present an algorithm that determines the prime factors of connected graphs with respect to the Cartesian product in linear time and space. This improves a result of Aurenhammer et al. [Cartesian graph factorization at logarithmic cost per edge, Comput. Complexity 2 (1992) 331-349], who compute th ...
Leto:
2007
Vir:
Fakulteta za elektrotehniko, računalništvo in informatiko (UM FERI)
Ni določena
Oznake:
teorija grafov;medianski grafi;neskočni grafi;vozliščno-tranzitivni grafi;graph theory;median graphs;infinite graphs;vertex-transitive graphs;
V članku obravnavamo neskončne, lokalno končne, vozliščno-tranzitivne medianske grafe. Pokazano je, da končnost ▫$\Theta$▫-razredov takih grafov ne zagotavlja končnosti blokov. Bloki pa postanejo neskončni, če nadalje nobeno končno zaporedje ▫$\Theta$▫-kontrakcij ne naredi novih prereznih vozlišč. D ...
Leto:
2008
Vir:
Fakulteta za naravoslovje in matematiko (UM FNM)
Izvirni znanstveni članek
Oznake:
matematika;teorija grafov;drevo;izometrična vložitev;mrežna vložitev;delna kocka;mathematics;graph theory;lattice embedding;isometric embedding;partial cube;tree;
Predstavljen je algoritem časovno linearne zahtevnosti, ki na izometričen način vloži dano drevo ▫$T$▫ v celoštevilsko mrežo najmanjše možne dimenzije in omogoča izračun mrežnih koordinat vozlišč drevesa ▫$T$▫ v optimalnem času.
Leto:
2009
Vir:
Fakulteta za naravoslovje in matematiko (UM FNM)
Izvirni znanstveni članek
Oznake:
teorija grafov;medianski grafi;neskočni grafi;vozliščno-tranzitivni grafi;graph theory;median graphs;infinite graphs;vertex-transitive graphs;
V članku obravnavamo neskončne, lokalno končne, vozliščno-tranzitivne medianske grafe. Pokazano je, da končnost ▫$\Theta$▫-razredov takih grafov ne zagotavlja končnosti blokov. Bloki pa postanejo neskončni, če nadalje nobeno končno zaporedje ▫$\Theta$▫-kontrakcij ne naredi novih prereznih vozlišč. D ...
Leto:
2009
Vir:
Fakulteta za naravoslovje in matematiko (UM FNM)
Kratki znanstveni prispevek
Oznake:
matematika;teorija grafov;kartezični produkt;problem rekonstrukcije;sestavljeni grafi;ne zaključna dela;mathematics;graph theory;reconstruction problem;Cartesian product;composite graphs;
Po Ulamovi domnevi je mogoče vsak končen graf ▫$G$▫ rekonstruirati iz množice vseh podgrafov ▫$G$▫ brez ene točke. Znano je, da je mogoče rekonstruirati kartezične produkte. Obravnavan je soroden problem, imenovan šibka rekonstrukcija. Dokazano je, da je mogoče odločiti, ali se da dani graf ▫$H$▫ do ...
Leto:
2001
Vir:
Pedagoška fakulteta (UM PEF)
Objavljeni znanstveni prispevek na konferenci
Oznake:
matematika;teorija grafov;razlikovalno število;polni grafi;kartezični produkt grafov;ne zaključna dela;mathematics;graph theory;distingushing number;complete graphs;Cartesian product;
Razlikovalno število ▫$D(G)$▫ grafa ▫$G$▫ je najmanjše število ▫$d$▫, tako da ▫$G$▫ premore označitev z ▫$d$▫ oznakami, ki jo ohranja le trivialni avtomorfizem. Dokažemo, da lahko kartezične produkte relativno tujih grafov, katerih velikosti se ne razlikujejo preveč, razlikujemo z majhnim številom b ...
Leto:
2008
Vir:
Fakulteta za naravoslovje in matematiko (UM FNM)
Izvirni znanstveni članek
Oznake:
matematika;teorija grafov;izometrične vložitve;delne kocke;drevesa;ekspanzija;medianski grafi;avtomorfizmi grafov;grupe avtomorfizmov;odstranljivi grafi;mathematics;graph theory;Isometric embeddings;partial cubes;expansion procedures;trees;median graphs;graph automorphisms;automorphism groups;dismantlable graphs;
Drevesom podobni podgrafi hiperkock predstavljajo posplošitev medianskih grafov. Tako kot medianski grafi podedujejo veliko lastnosti dreves, toda lahko vsebujejo večje razrede grafov, ki jih morda lahko hitreje prepoznamo kot medianske grafe. V članku proučujemo strukturo drevesom podobnih delnih k ...
Leto:
2003
Vir:
Fakulteta za elektrotehniko, računalništvo in informatiko (UM FERI)
Izvirni znanstveni članek
Oznake:
matematika;teorija grafov;kartezični produkt;problem rekonstrukcije;sestavljeni grafi;mathematics;graph theory;reconstruction problem;Cartesian product;composite graphs;
Po Ulamovi domnevi je mogoče vsak končen graf ▫$G$▫ rekonstruirati iz množice vseh podgrafov ▫$G$▫ brez ene točke. Znano je, da je mogoče rekonstruirati kartezične produkte. Obravnavan je soroden problem, imenovan šibka rekonstrukcija. Dokazano je, da je mogoče odločiti, ali se da dani graf ▫$H$▫ do ...
Leto:
2003
Vir:
Pedagoška fakulteta (UM PEF)