| Abstrakt: | L(2, 1)-farbenie grafu je očíslovanie jeho vrcholov prirodzenými číslami tak, že čísla
susedných vrcholov sa líšia aspoň o 2 a čísla vrcholov vo vzdialenosti 2 sa líšia aspoň
o 1. Rozpätie L(2, 1) farbenia je najväčšie číslo, ktoré používa. Minimálne rozpätie
L(2, 1)-farbenia grafu G označujeme λ(G). Najlepší doterajší algoritmus na hľadanie
λ(G) na všeobecných grafoch má časovú zložitosť O ∗ (2.6488 n ).
V práci popisujeme metódy rozdelenia problému na menšie časti, pomocou ktorých vytvárame efektívnejšie algoritmy pre hľadanie λ(G). Vytvoríme algoritmus na
hľadanie rozpätia L(2, 1)-farbenia na planárnych grafoch v čase O ∗ (2.2 n+o(n) ) a v čase
O ∗ (2.613 n ) na grafoch s malým vrcholovým separátorom. Nakoniec popisujeme postup
generovania všetkých neoznačených minimálne 2-hranovo súvislých grafov. Experimentálne overujeme, že spomedzi 2-hranovo súvislých grafov majú najväčší počet kombinatorickej štruktúry, ktorá sa nazýva vlastný pár, práve kružnice.
|
|---|