Abstrakty 2018

2. listopadu     Petr Kovář: Highly irregular supermagic graphs

(joint work with Michal Kravčenko, Matěj Krbeček, and Adam Silber)

Let G = (V, E) be a graph with m edges. A bijection f : F → { a, a+1, ..., a+m-1 } for some integer a is called a supermagic labeling of G if for every vertex v the sum of edge-labels of all edges adjacent to v is equal to the same integer k. The constant k is the \emph{magic constant} of f and any graph which admits a supermagic labeling is a supermagic graph. The concept of magic graphs (with arbitrary real labels) is one on the oldest labeling concepts. It originated by Sedláček in 1963. Supermagic labelings were introduced by Stewart in 1967.

Dozens of papers have been published on supermagic labelings, mostly providing constructions of supermagic labelings of a specific class of graphs as well as some necessary conditions for the graph to allow a supermagic labeling. The proofs are mostly constructive, usually providing a labeling technique for regular or almost regular graphs. Some supermagic graphs with different degrees were provided by Ivančo and Semaničová in 2005 or Ivančo and Polláková in 2012 and 2014. Recently we obtained a general construction of supermagic graphs with arbitrarily many different degrees. Today we present the result as well as some open problems this area.

Pozvánka v PDF


1. června     Dalibor Fronček: How close to being platonic can you get?

(joint work with Jiangyi Qiu)

A Platonic graph is a vertex-regular planar graph with all faces of the same size. It is well known that there exist exactly five such graphs: tetrahedron, octahedron, hexahedron, icosahedron, and dodecahedron. Recently, William Keith asked whether there exist nearly Platonic graphs that would differ from Platonic in just one face. That is, vertex-regular planar graphs with all faces except one having the same size. W. Keith, D. Kreher and the speaker then showed (or at least believed that they had shown) that no such graphs exist [1]. On the other hand, there are well known classes of 2-nearly Platonic graphs with exactly two exceptional faces, both of the same size. We will and ask (and partially answer) some questions about 2- and 3-nearly Platonic graphs. In other words, about vertex-regular planar graphs with exactly two or three exceptional faces.

[1] W. Keith, D. Froncek, D. Kreher, A note on nearly Platonic graphs, Australas. J. Combin. (2017), 86-103.

Pozvánka v PDF


5. května     Tom Raiman: Conditions for adding vertices to (k,g)-graphs

A (k,g)-graph is a k-regular graph of girth g. A (k,g)-graph of the smallest possible order is called a (k,g)-cage. The Cage Problem is the problem of finding such smallest graphs and their orders for all pairs k,g ≥ 3. This problem has been extensively studied since the 1960's when Erdös and Sachs proved the existence of infinitely many (k,g)-graphs for any pair (k,g). Their original upper bound on the order of cages has been later improved by Sauer. In each case, an order was found with the property that a (k,g)-graph exists for each admissible order larger than this bound. We present a different approach and study the properties of (k,g)-graphs that can be extended into larger (k,g)-graphs by adding vertices. This approach may potentially give rise to recursive constructions based on smaller graphs than those identified by Erdös, Sachs, and Sauer.

Pozvánka v PDF


Abstrakty 2017

8. listopadu     Dalibor Fronček: Some cycle products are more magic than others

A Cartesian product CmCn of two cycles Cm and Cn can be seen as a toroidal m × n grid with mn vertices of degree four and 2mn edges. We can bijectively label the edges, vertices, or both by consecutive positive integers 1, 2, . . . , s or by elements of an Abelian group Γ of order (where s is the number of labeled elements) and define the weight of an element (that is, an edge or a vertex) as the sum of labels of the adjacent and/or incident elements. When the weights of all elements in question are equal, we call the labeling magic (of some kind). When the weights are all different, the labeling is called antimagic. I will present some old and new results on various kinds of magic labelings of cycle products and pose several open questions. The results are based on collaboration with several co-authors, including Tereza Kovářová, Petr Kovář, Jack McKeown, James McKeown, Michael McKeown, and Yichen Wei.

Pozvánka v PDF


23. října     Michael Kubesa: Faktorizace kompletních grafů na kostry

Kostra grafu je souvislý faktor grafu G, který neobsahuje cykly. Nejdříve se seznámíme s pojmem semisurjektivní a bicyklická faktorizace kompletního grafu, uvedeme jednoduché nutné podmínky pro faktorizace z názvu přednášky. Pak objasníme pojmy symetrický ρ-labeling, blended labeling a swapping labeling, což jsou postačující podmínky pro semisurjektivní faktorizace kompletních grafů na kostry.

TATO PŘEDNÁŠKA je 2. PŘEDNÁŠKA trojpřednáškového cyklu a je určena doktorandům a výzkumníkům, kteří se zabývají problémy diskrétní matematiky.

Pozvánka v PDF


9. října     Michael Kubesa: Základy dekompozic a faktorizací kompletních a kompletních bipartitních grafů

Řekneme si, co je dekompozice a faktorizace grafů. Dále se zaměříme na postačující podmínky dekompozice a faktorizace kompletních a kompletních bipartitních grafů, které uvedeme ve formě tzv. labelingu. Budeme hovořit o graceful labelingu, ρ-labelingu a bipartitním ρ-labelingu. Budeme tedy hovořit jen o nejzákladnějších labelinzích týkajících se dekompozic a faktorizací. Kdo by se o nich chtěl dovědět více, doporučujeme: Joseph A. Gallian, A Dynamic Survey of Graph Labeling.

TATO PŘEDNÁŠKA je 1. PŘEDNÁŠKA trojpřednáškového cyklu a je určena především doktorandům, kteří se v rámci postgraduálního studia zabývají problémy diskrétní matematiky.

Pozvánka v PDF


3. října     Štefan Gyürki: Directed strongly regular graphs

Since the main objects of interest in algebraic graph theory are highly symmetric graphs, strongly regular graphs are playing a central role in this area. One of their possible generalization for directed graphs was given by Duval in 1988. A directed strongly regular graph (DSRG) with parameters (n, k, t, λ, μ) is a regular directed graph on vertices with valency k such that every vertex is incident with t undirected edges; the number of directed paths of length 2 directed from a vertex x to another vertex y is λ, if there is an arc from x to y and μ otherwise. In this talk we mention their basic properties and several constructions of such graphs

Pozvánka v PDF


27. června     Tom Raiman: Grafy geometrických designů (2)-([28,3,21])

(t)-([q^n,k,λ]) design na (n)-dimenzionálním vektorovém prostoru stupně (q) je množina (B) (k)-dimenzionálních podprostorů ((k)-podprostory), nazývané bloky, takové, že libovolný (t)-dimenzionální podprostor ((t)-podprostor) je podprostorem přesně (λ) bloků. Takový design označujeme jako ((V,B)). Je-li (t)-podprostor podprostorem (k)-podprostoru jsou tyto podprostory incidentní. Graf poté vyjadřuje incidenci mezi (k)- a (t)-podprostorem. Zaměříme se na grafy, které vzniknou z designu (2)-([28,3,21]).

Pozvánka v PDF


12. ledna     Dalibor Fronček: Decompositions of complete bipartite graphs into prisms revisited

A generalized prism, or more specifically an (0,j)-prism of order 2n (where n is even) is a cubic graph consisting of two cycles u0, u1, ..., un-1 and v0, v1, ..., vn-1 joined by two sets of spokes, namely u1v1, u3v3, ..., un-1vn-1 and u0vj, u2vj+2, ..., un-2vj-2. The question of factorization of complete bipartite graphs into (0,j)-prisms was completely settled by the author and S. Cichacz. Some partial results on decompositions of complete bipartite graphs have also been obtained by S. Cichacz, DF, and P. Kovar, and on decompositions of complete graphs S. Cichacz, S. Dib, and DF. The problem of decomposition of complete graphs into prisms of order 12 and 16 was completely solved by S. Cichacz, DF and M. Meszka. In June 2014 I presented what I had believed was a complete solution for the decomposition of complete bipartite graphs into (0,0)-prisms (that is, the usual prisms). In the same talk I mentioned my presentation in March 2014 in Boca Raton, Florida, where I had to admit that the results I had promised in my abstract were not covering any new cases, but rather just re-proved previously known results. This time, I will retract what I have retracted, and order what I have ordered.

Pozvánka v PDF


Abstrakty 2016

12. prosince     Robert Jajcay: Counting cycles in graphs with small excess

A (k,g)-cage is a k-regular graph of girth g that has the smallest number of vertices among all graphs with the parameters k and g. The orders of cages are bounded from below by the well-known Moore bounds, however, the exact orders are not known for the majority of cages. The excess of a cage is the difference between its order and the Moore bound, and a systematic study of the excesses of cages leads to improved lower bounds on their orders. We present some of the most recent improvements based on counting cycles.

Pozvánka v PDF


20. dubna     Wilfried Imrich: Symmetry breaking in graphs

In a graph, a set of vertices that is stabilized setwise by only the trivial automorphism is called a distinguishing set. Tom Tucker conjectured that every connected, infinite locally finite graph G has such a set if each nontrivial automorphism of G moves infinitely many vertices. The conjecture is know as the Infinite Motion Conjecture. It is still open despite the fact that numerous large classes of graphs have been shown to satisfy it.

In finite graphs distinguishing sets, if they exist, can be very small in comparison to the size of the graph, and in infinite graphs such sets can be finite. If they are not finite, their density can be zero. This talk presents classes of graphs that have distinguishing sets of zero density. Moreover, it is shown that the Infinite Motion Conjecture is true for cubic graphs.

Pozvánka v PDF


12. dubna     Tom Raiman: Faktorizace grafů na pulce

Faktorizace kompletních grafů představuje klasický problém nejen z teorie grafů, ale i teorie designů. Toto téma je zkoumáno od 60. let 20. století. Co se týče faktorizace kompletních grafů byly známy pouze zřejmé výsledky (faktorizace na hamiltonovské cesty a dvojhvězdy). V poslední době byly nalezeny třídy koster, které faktorizují a které ne. Mezi ně patří některé housenky a langusty. Momentálně jsou zkoumány faktorizace kompletních grafů na unicyklické grafy zvané pulci. Unicykly lze faktorizovat pouze kompletní grafy s lichým počtem vrcholů, tzn. K2n+1. Pro faktorizace kompletních grafů na pulce používáme modifikované metody faktorizací kompletních grafů na kostry. Zejména smíšené ohodnocení pro n liché a přepínací ohodnocení pro n sudé. Nyní je výzkum veden pro n liché, protože smíšené ohodnocení je jednodušší.

Pozvánka v PDF


25. ledna     Tomáš Gavenčiak: Hry na grafech

Seznámení s hrami na četníky a lupiče zaměřené na geometrické grafy (jako jsou třeba rovinné, intervalové či křivkové) a se zajímavými výsledky poslední doby.

Hry na četníky a lupiče mají mnohem blíže k abstraktním deskovým hrám a (snad trochu překvapivě) k strukturální a výpočetní složitosti, než k aplikované bezpečnosti, a jsou elegantní kapitolou (už tak hravé) teorie kombinatorických her.

Pozvánka v PDF


5. ledna     Dalibor Fronček: Group distance magic labelings of hypercubes and Cartesian products of cycles

Let G be a graph with n vertices and f a bijection f:V(G) -> {1,2,...,n}. We define the weight of vertex x as the sum of the labels of its neighbors, that is, w(x)=∑_{xy∈E(G)}f(y).

When all vertices have the same weight, say w(x)=m for every x, then f is called distance magic labeling and G is a distance magic graph.

However, it turns out that this type of magic labeling is very restrictive and consequently even many classes of vertex transitive graphs are not distance magic.

As an example, we prove that for d≡0,1,3 mod 4 the hypercube Q_d with 2^d vertices is not distance magic. On the other hand, we disprove a conjecture by Acharya, Rao, Singh and Parameswaran, who believed that hypercubes are not distance magic except Q_2 and present a distance magic labeling for Q_6. This was recently generalized by Gregor and Kovar who found a distance magic labeling for of Q_d for any d≡2 mod 4.

Such negative results then rise a question whether it would not be more natural to perform the addition in Z_n rather than in Z. Graphs that satisfy the above definition with the provision that the addition is performed in Z_n will be called Z_n-distance magic.

To support this idea, we show some examples of graphs that are not distance magic yet are Z_n-distance magic. We show that when we perform addition Z_{2^d} rather than in Z, then Q_d is Z_{2^d}-distance magic if and only if d is even.

We present some results on Γ-distance magic labelings of products of cycles and pose several open problems.

Pozvánka v PDF


Abstrakty 2014

6. listopadu     Kateřina Volná, Matěj Krbeček: Arboricita, Orientace planárního grafu

První část semináře bude věnována arboricitě grafu. Kateřina Volná zavede pojem arboricity, neboli stromovitosti, kterou lze využít při hledání nejmenšího odchozího stupně vrcholu v grafu. Uvede jednotlivé druhy arboricity a také souvislost s chromatickým číslem grafu. Závěr prezentace je pak věnován algoritmům a jejich složitosti.

Druhá část seminář bude o 3-bounded orientaci v planárním grafu. Matěj Krbeček se bude věnovat problematice d-bounded orientace, konkrétně 3-bounded a jejímu nalezení v planárních grafech. Nadefinujeme základní pojmy a zmíníme věty týkající se dané problematiky. Popíšeme si algoritmus s lineární složitostí, který využívá tzv. reducibilních vrcholů.

Pozvánka v PDF


30. října     Jiří Fiala: Hledání Hamiltonovských cest v intervalových grafech

V přednášce se budeme zabývat problémem, zdali lze množinu reálných intervalů uspořádat do posloupnosti tak, že každé dva po sobě následující intervaly mají neprázdný průnik. Pro tento problém bude představen algoritmus a s jeho pomocí se ukáže, že jistá zřejmá nutná podmínka pro existenci takového uspořádání je zároveň i postačující.

Jinými slovy, buď daná posloupnost existuje, pak ji lze nalézt a ověřit patřičné vlastnosti; nebo neexistuje a i v tomto případě lze relativně snadno nalézt argument proč ani existovat nemůže. To je jeden z mála případů, kdy má obecně výpočetně těžký problém stručné důkazy pro případy kladných i záporných odpovědí.

Přednáška je určená široké veřejnosti, žádné odborné znalosti z kombinatoriky ani výpočetní složitosti nejsou nutné k porozumění tématu.

Pozvánka v PDF


20. června     Dalibor Fronček: Decompositions of complete bipartite graphs into prisms

A generalized prism, or more specifically an (0,j)-prism of order 2n (where n is even) is a cubic graph consisting of two cycles u_0,u_1,...,u_{n-1} and v_0,v_1,..,v_{n-1} joined by two sets of spokes, namely u_1 v_1, u_3 v_3,...,u_{n-1}v_{n-1} and u_0 v_j, u_2 v_{j+2},...,u_{n-2}v_{j-2}.

The question of factorization of complete bipartite graphs into (0,j)-prisms was completely settled by the author and S. Cichacz. Some partial results on decompositions of complete bipartite graphs and complete graphs have also been obtained by them and P. Kovar and S. Dib, respectively. The problem of decomposition of complete graphs into prisms of order 12 and 16 was completely solved by the author with S. Cichacz and M. Meszka and presented at IWONT 2012.

We will present a complete solution for the decomposition of complete bipartite graphs into (0,0)-prisms (that is, the usual prisms).

Pozvánka v PDF


2. června     Michael Kubesa: 15 školaček podruhé, Kirkmanovy trojúhelníkové systémy (KTS) vyšších řádů

V první přednášce bude dokončen výklad k rho- a bipartitnímu rho-ohodnocení. Dále bude vyřešen problém 15 školaček pomocí faktorizace kompletního grafu. Ukážeme, že touto metodou jsme schopni vytvořit KTS(15). Ve druhé části bude předvedena rekurzivní konstrukce KTS(6n+3), je-li n větší než 2.

Pozvánka v PDF


26. května     Michael Kubesa: Problém 15 školaček aneb Kirkmanovy trojúhelníkové systémy (KTS)

15 školaček v internátní škole se má procházet každý den po trojicích v pěti řadách. Naplánujte jejich rozdělení do trojic na každý den v týdnu (7 dnů) tak, že každá dvojice se v rámci trojic potká právě jednou. Ukážeme si řešení tohoto úkolu, přičemž ozřejmíme souvislost mezi tvorbou seskupitelných designů a faktorizací kompletních grafů. Čili si ukážeme konstrukci KTS pro 9 a 15 prvků. Konstrukce KTS vyšších řádů budou uvedeny v další přednášce.

Pozvánka v PDF


21. května     Tereza Kovářová, Kateřina Volná: Teorie designů (část 4)

Teorie designů je matematická disciplína na pomezí kombinatoriky, teorie grafů a teorie množin. Zkoumá systémy podmnožin s předepsanými parametry. Aplikace teorie designů najdeme především v plánování (organizace experimentů s mnoha nezávislými parametry, plánování sportovních turnajů) nebo při rozkladů grafů na podgrafy. Ve čtvrtém z řady seminářů, koncipovaném především pro studenty předmětu Metody diskrétní matematiky, si ukážeme konstrukce Balanced Tournament Designu v souvislosti s aplikací tohoto designu při vytváření rozpisu turnaje s speciálním požadavkem na umístění zápasů.

Pozvánka v PDF


25. dubna     Petr Kovář: Teorie designů (část 3)

Teorie designů je matematická disciplína na pomezí kombinatoriky, teorie grafů a teorie množin. Zkoumá systémy podmnožin s předepsanými parametry. Aplikace teorie designů najdeme především v plánování (organizace experimentů s mnoha nezávislými parametry, plánování sportovních turnajů) nebo při rozkladů grafů na podgrafy. Ve třetím z řady seminářů, koncipovaném především pro studenty předmětu Metody diskrétní matematiky, se budeme věnovat konstrukcím Steinerovských systémů trojic.

Pozvánka v PDF


24. dubna     Róbert Jajcay: Symmetric cages (Symetrické klietky)

A (k,g)-cage is a smallest k-regular graph of girth g. Finding a (k,g)-cage for given parameters k and g is thus an optimization problem in which one looks for an extremal graph in an infinite search space of all k-regular graphs of girth g. The search for cages started in earnest in the 1960's, but turned out to be too hard in general, and has only recently been revived due to the introduction of algebraic and topological methods in the area. In our talk, we present an overview of the contributions stemming of the use of Cayley and vertex-transitive graphs as well as some recent results concerning the restriction of the original cage problem to these two classes of symmetric graphs. The talk is aimed at general mathematical audience including students.

Pozvánka v PDF


11. dubna     Petr Kovář: Teorie designů (část 2)

Teorie designů je matematická disciplína na pomezí kombinatoriky, teorie grafů a teorie množin. Zkoumá systémy podmnožin s předepsanými parametry. Aplikace teorie designů najdeme především v plánování (organizace experimentů s mnoha nezávislými parametry, plánování sportovních turnajů) nebo při rozkladů grafů na podgrafy. V druhém z řady seminářů, koncipovaném především pro studenty předmětu Metody diskrétní matematiky, se budeme věnovat Steinerovským systémům trojic.

Pozvánka v PDF


4. dubna     Petr Kovář: Teorie designů (část 1)

Teorie designů je matematická disciplína na pomezí kombinatoriky, teorie grafů a teorie množin. Zkoumá systémy podmnožin s předepsanými parametry. Aplikace teorie designů najdeme především v plánování (organizace experimentů s mnoha nezávislými parametry, plánování sportovních turnajů) nebo při rozkladů grafů na podgrafy. V prvním z řady seminářů, koncipovaném především pro studenty předmětu Metody diskrétní matematiky, zavedeme základní pojmy a zformulujeme hlavní problém teorie designů.

Pozvánka v PDF


13. ledna     Tereza Kovářová: Handicapové grafy vyšších pravidelností

(spoluautor Petr Kovář)

Handicapové ohodnocení grafů má potenciál při sestavování neúplných turnajů ve kterých součet sil protihráčů každého týmu je tím větší čím silnější tým je. Na semináři byly dříve prezentovány výsledky týkající se konstrukcí handicapových ohodnocení 3-pravidelných a 5-pravidelných grafů. Jedním z nevyřešených problémů bylo nalezení handicapového ohodnocení pro grafy s vyšší pravidelností. V této navazující přednášce budou ukázány možnosti konstrukcí tohoto ohodnocení r-pravidelných grafů na n vrcholech, pro všechna přípustná r < n-10.

Pozvánka v PDF


Abstrakty 2013

13. prosince     Michael Kubesa: Orientace rovinných grafů

Chceme orientovat jednoduchý konečný rovinný graf tak, aby největší odchozí stupeň grafu byl co nejmenší. Tento problém souvisí s vhodnou paralelizací výpočtu v numerických úlohách.

Pozvánka v PDF


6. prosince     Pavla Hrušková: Několik vybraných aplikací spektrální teorie grafů

V úvodu přednášky se seznámíme s pojmem spektrum grafu. Spektrem grafu je myšlena množina vlastních čísel a vlastních vektorů grafu, který pro tyto účely reprezentujeme maticí. Jako vhodná maticová reprezentace se pro tyto účely používá nejčastěji matice sousednosti, případně Laplaceova matice. Ukážeme známá spektra některých vybraných typů grafů, konkrétně cesty a kartézského produktu dvou cest, což v numerické matematice odpovídá 1D, resp. 2D čtvercové síti.

V další části připomeneme aplikaci na využití spektra grafů pro důkaz neexistence faktorizace kompletního grafu pomocí 3 Petersenových grafů, pro který ale potřebujeme znalost kompletního spektra a dále se budeme zabývat aplikacemi využívající pouze část spektra (zpravidla vlastní vektory odpovídající několika největším, resp. nejmenším, vlastním číslům).

Nejdříve ukážeme nejběžnější použití vlastních vektorů Lapaceovy matice na spektrální dělení grafů poprvé zmíněné již Prof. Fiedlerem v 70. letech (první aplikace pochází z 80.-90.let). Dále ukážeme použití vlastních vektorů Laplaceovy matice pro nalezení optimální volby tzv. fixujících vrcholů používaných při řešení některých typů numerických úloh pomocí FETI metod, konkrétně úloh se semidefinitní maticí tuhosti. Obdobné myšlenky se uplatňují v obecných aplikacích typu (spektrální) kreslení grafů případně clusterování grafů. Jedna z nejznámnějších aplikací spektrální teorie grafů je Google ranking algoritmus používaný ve vyhledávacím enginu Googlu. Mnohé z těchto aplikací se v dnešní době s úspěchem používají také v různých sociálních sítích (clustering, eigenvector centrality apod.).

Pozvánka v PDF


26. listopadu     Tereza Kovářová: Postupy diskrétní matematiky při losování reálné sportovní soutěže

(spoluautorka Kateřina Volná)

Pro plánování amatérské soutěže ve sportovní střelbě, kdy se na různých střeleckých drahách utkají vždy dvojice střelců, je nutno uvážit:

  • počet účastníků soutěže,
  • omezení počtu střeleckých drah,
  • dostatečné, avšak nepříliš dlouhé přestávky mezi jednotlivými koly pro každého hráče,
  • pravidelné střídání drah a na každé dráze střídání pozice vlevo či vpravo.
V rámci přednášky bude ukázáno, jak lze pro sestavení rozpisu s výhodou využít nástrojů diskrétní matematiky, jako jsou rozklady kompletních grafů nebo latinské čtverce a další.

Pozvánka v PDF


22. listoadu     Michael Kubesa: Neplanarita grafu, Toky v sítích

Seminář bude didakticky zaměřen. Bude prodiskutováno použití Kuratowského věty k zjištění neplanarity grafu, užití Ford Fulkersonova algoritmu k vyhledání největšího toku a nejmenšího řezu v síti.

Pozvánka v PDF


8. listoadu     Petr Kovář: Hranová barvení grafů

Při paralelizaci numerického výpočtu vyvstala úloha, kterou je možno zformulovat v řeči teorie grafů: máme různě ohodnocené vrcholy a hledáme takové hranové ohodnocení, kdy hodnota přiřazená každé hraně odpovídá hodnotě jednoho koncového vrcholu. Ukážeme teoretické ohraničení počtu barev (myšlenku existenčního důkazu). Na tomto pracovním semináři uvedeme problém hledání konstruktivního důkazu, který by bylo možno použít pro rychlé nalezení takového ohodnocení.

Pozvánka v PDF


29. října     Michael Kubesa: Princip inkluze, exkluze a jeho nevhodné použití

V přednášce si ukážeme chybné použití principu inkluze a exkluze, chybu identifikujeme, rozebereme a ukážeme správné řešení.

Pozvánka v PDF


2. května     Pavla Kabelíková: Využití spektrálních vlastností grafů pro ověření (ne)existence faktorizací

Faktorizace grafu H na množinu hranově disjunktních navzájem izomorfních podgrafů G_1, G_2, ..., G_k je takový rozklad grafu H, kdy každá hrana grafu H patří do právě jednoho podgrafu G_i, každý podgraf G_i obsahuje všechny vrcholy původního grafu H a žádný vrchol není izolovaný. Problém nalezení faktorizace grafu na podgrafy je předpokládán za NP-úplný a pro některé třídy grafů je jeho NP-úplnost dokázána. K nalezení faktorizací některých tříd grafů se využívá různých grafových technik.

Vzhledem k tomu, že jsou podgrafy G_i izomorfní, jsou jejich matice podobné (ve smyslu algebraické podobnosti matic) a mají tedy stejné spektrum. K výpočtu spektra matic může být využita nějaká iterační metoda. V tomto pracovním semináři nejprve ukážeme s využitím znalosti spektra jednotlivých grafů, že kompletní graf na 10 vrcholech nemůže být faktorizován třemi Petersenovými grafy. Tento známý výsledek využivá velmi specifické struktury spektra Petersenova grafu a jeho vztahu ke spektru kompletního grafu. Cílem semináře bude pokus o aplikování této nebo obdobné konstrukce i na jiné typy grafů.

Pozvánka v PDF, prezentace v PDF, fotky


18. dubna     Přemysl Holub: Duhově souvislé grafy

Mějme dán hranově obarvený graf G. Řekneme, že G je duhově souvislý, jestliže každé dva vrcholy grafu jsou spojeny duhovou cestou (všechny hrany cesty mají rozdílné barvy). Nejmenší počet barev k potřebný k obarvení hran grafu G tak, aby G byl duhově souvislý, nazveme duhovou souvislostí grafu. Cílem přednášky bude seznámení se s tímto pojmem a některými známými výsledky z této oblasti.

Pozvánka v PDF. Prezentace v PDF.


28. března     Petr Kovář, Martin Kovář: Magická ohodnocení - otevřené problémy

Za posledního čtvrt roku se podařilo dotáhnout do konce důkazy některých výsledků, ale současně vyvstaly nové zajímavé otázky. Na ty nejzajímavější z nich upozorníme.

Pozvánka v PDF.


Abstrakty 2012

10. prosince     Pavel Jahoda: Množiny dokonalých rozdílů

Přednáška bude pojednávati o tom, kterak nalézti množinu dokonalých rozdílů (perfect difference set).

Pozvánka v PDF.


4. prosince     Pavel Jahoda: Co je konečné těleso?

Co je to těleso? Co je konečné těleso? Existují vůbec? Kolik může mít prvků? Jak nějaké zkonstruovat? Proč by měl být polynom použitý při konstrukci konečného tělesa ireducibilní? Dostanu pro různé ireducibilní polynomy při konstrukci konečného tělesa různá konečná tělesa? Kolik různých těles s daným počtem prvků existuje? Trápí Vás alespoň jedna z těchto otázek? Přijďte!

Pozvánka v PDF.


27. listopadu     Petr Kovář: Využití rozkladů grafů na husté podgrafy při paralelní implementaci BEM

spoluautoři: D. Lukáš, T. Kovářová a M. Kravčenko

Naším úkolem bude rozdělit n2 bloků Bij rozsáhlé matice do n skupin tak, aby v každé skupině byly bloky s co nejmenším počtem různých indexů. Ukážeme jaká jsou teoretická omezení pro tento minimální počet indexů při pevně zvoleném počtu n a ukážeme, že pro nekonečně mnoho různých hodnot umíme tohoto optima dosáhnout. Důkaz je konstruktivní, vychází z rozkladů kompletních grafů na husté podgrafy a umožní pro vybrané hodnoty n optimálně implementovat úlohu z minulé přednášky. Na závěr zmíníme několik zobecnění, která umožní dosáhnout počtu různých indexů blízkých optimální hodnotě i pro další hodnoty n, pro které neexistuje optimální řešení.

Pozvánka v PDF.


19. listopadu     Dalibor Lukáš: Paralelní metoda hraničních prvků pomocí cyklické dekompozice grafů

spolu s P. Kovářem, T. Kovářovou, M. Mertou a M. Kravčenkem

Metoda hraničních prvků je numerická metoda pro řešení okrajových úloh některých parciálních diferenciální rovnic. Metoda vede na soustavu lineárních rovnic s plnou maticí, jejíž řádky i sloupce odpovídají prvkům triangulace 3d výpočetní oblasti. Při paralelním sestavení řídké aproximace této matice chceme distribuovat triangulaci tak, aby výpočet spotřeboval minimum času i paměti. Ukazuje se, že pro jisté počty procesorů taková optima dostaneme pomocí cyklické dekompozice úplných grafů.

V přednášce pro ilustraci odvodíme hraniční formulaci Dirichletovy úlohy pro Laplaceovu rovnici v 1 dimenzi. Pro analogickou úlohu ve více dimenzích napíšeme vzorce pro výpočet prvků plné matice a popíšeme její řídkou aproximaci. Konečně formulujeme požadavky na její optimální paralelizaci a ukážeme, že některá optima máme díky cyklické dekompozici grafů.

Pozvánka v PDF.


12. listopadu     Michael Kubesa: T-faktorizace kompletních grafů

Mějme podgrafy G_1,G_2,...,G_s, kompletního grafu, které jsou všechny izomorfní s grafem G. Patří-li každá hrana kompletního grafu do přesně jednoho podgrafu G_i, pak jde o G-dekompozici kompletního grafu. Obsahují-li podgrafy G_i všechny vrcholy kompletního grafu a žádný vrchol není v G_i izolovaný, pak G-dekompozici nazýváme G-faktorizací. My se v přednášce zaměříme na G-faktorizace, kdy G je strom (souvislý graf bez cyklů). Protože G je strom, označíme jej T. V T-faktorizaci kompletního grafu je tedy každý podgraf T_i stromem a obsahuje všechny vrcholy kompletního grafu, Takovým podgrafům budeme říkat kostry kompletního grafu. Snadno lze ukázat, že T-faktorizaci lze provést pouze pro kompletní grafy se sudým počtem vrcholů, a že v T nesmí být žádnývrchol vyššího stupně než-li n, má-li kompletní graf 2n vrcholů. Postačující podmínkou pro T-faktorizaci kompletního grafu K_{2n}, je-li n liché, je smíšené ohodnocení kostry T, které je založeno na existenci rho-ohodnocení a bipartitního rho-ohodnocení, o nichž jsme vyprávěl minule. A právě o smíšeném ohodnoceníbude hovor.

Pozvánka v PDF.


5. listopadu     Michael Kubesa: G-dekompozice kompletních grafů

Mějme podgrafy G_1,G_2,...,G_s, kompletního grafu, které jsou všechny izomorfní s grafem G. Patří-li každá hrana kompletního grafu do přesně jednoho podgrafu G_i, pak jde o G-dekompozici kompletního grafu. Postačující podmínkou pro G-dekompozici kompletního grafu K_{2n+1} jsou alpha-ohodnocení, beta-ohodnocení a rho-ohodnocení grafu G s n hranami. A právě o těchto ohodnoceních a bipartitním rho-ohodnocení bude hovor.

Pozvánka v PDF.


30. října     Petr Kovář: Hledání handicapových labelingů grafů se sudou pravidelností

Prezentovali jsme známé výsledky týkající se nutných podmínek existence handicapových ohodnocení pravidelných grafů. Zmínili jsme otevřené problémy v této oblasti.

Pozvánka v PDF.


22. října     Tereza Kovářová: Konstrukce 3- a 5-pravidelných handicapových grafů

Prezentovali jsme známé výsledky týkající se konstrukcí 3- a 5-pravidelných handicapových grafů. Zformulovali jsme další směr výzkumu.

Pozvánka v PDF.


8. října     Petr Kovář: Nutné podmínky existence handicapových grafů

Prezentovali jsme známé výsledky týkající se nutných podmínek existence handicapových ohodnocení pravidelných grafů. Zmínili jsme otevřené problémy v této oblasti.

Pozvánka v PDF.


1. října     Petr Kovář: Neúplné turnaje a magická ohodnocení pravidelných grafů

V přednášce shrneme přehled témat, kterým se můžeme věnovat v rámci semináře DiMaS.

Pozvánka v PDF.


Abstrakty 2011

21. dubna     Michael Kubesa: Grafová ohodnocení a jejich použití při rozkladech kompletních a bipartitních kompletních grafů

Mějme vzajemně izomorfní pografy $G_1,G_2,... ,G_m$ grafu $H$ (platí tedy G_1\cong G_2\cong \dots \cong G_m \cong G). Jestliže každá hrana grafu $H$ je obsažena v přesně jednom podgrafu $G_i$, $i\in\{1,2,\dot ,m\}$, pak hovoříme o $G$-rozkladu (dekompozici) grafu $H$. Pokud graf $G$ s $n$ hranami umožňuje tzv. graciózní nebo $\rho$-ohodnocení, pak existuje $G$-rozklad kompletního grafu $K_{2n+1}$ a jestliže má $G$ tzv. bipartitní $\rho$-ohodnocení, pak existuje $G$-rozklad kompletního bipartitního grafu $K_{n,n}$.

Pozvánka v PDF.


Abstrakty 2009

16. prosince     Roman Kužel: Nelineární iterační metody pro výpočet kritického čísla a hustoty neutronového toku aktivní zóny jaderných reaktorů typu VVER

Přednáška bude věnována problematice řešení difuzního modelu transportu neutronů pro reaktory s kazetami se šestiúhelníkovým průřezem. Zaměříme se především na rychlé nelineární iterační algoritmy založené na hrubosíťovém výpočtu a metodě příčných integrací.

Pozvánka v PDF.


15. prosince     Roman Čada: Diskrétní matematika v optimalizaci palivových vsázek jaderného reaktoru

Přednáška bude zaměřena po nezbytném fyzikálním úvodu na matematické metody řešení úlohy optimalizace palivových vsázek v jaderných reaktorech. Ačkoli se ve své podstatě jedná o úlohu nelineární kombinatorické optimalizace, používané metody zahrnují kombinaci přístupů založených na spojité a diskrétní nelineární optimalizaci, stochastických metodách a konceptech užívaných v diskrétní matematice.

Pozvánka v PDF.


9. prosince     Martin Knor: Polomerovo Moorovské grafy a digrafy

Graf (digraf) je polomerovo Moorovský ak má pri danom polomere s a maximálnom stupni t maximálny možný počet vrcholov a jeho priemer je nanajvýš s+1. Je známe, že pre každé s a t existuje polomerovo Moorovský digraf daného stupňa a polomeru. Pre grafy je analogický problém otvorený. Polomerovo Moorovské grafy sú známé pre každý stupeň t pri polomeroch 1 a 2 a pre niekolko malých stupňov pri polomere 3.

Pozvánka v PDF.


1. prosince     Petr Kovář: Simpsonovi a matematika

V oblíbeném televizním seriálu najdeme celou řadu momentů, ve kterých se objeví základní i moderní matematické pojmy. V přednášce na několik takových míst upozorníme. Současně naznačíme některé hlubší souvislosti.
Přednáška může být zajímavá nejen pro studenty, ale i pro vyučující (motivace ve výuce).
Kalkulačky s sebou!!!

Pozvánka v PDF.


25. května     S. Arumugam: Min-Max and Max-Min Graph Saturation Parameters

A talk on hereditary property concerning subsets of the vertex set of a graph G. In this talk a brief survey of results on certain parameters for various graph theoretic properties is given.

Pozvánka v PDF.



Od roku 2009 jsou abstrakty připravovány pouze v PDF formátu.

Staší abstrakty najdete pouze v anglické verzi.

Send an email to the organizers kontakty Poslední úpravy: 01.11.2018