|
|
|
|
Výpočetní složitost Seidelova přepnutí grafů.
Seidelovo přepnutí je grafová operace, kterou zavedl holandský matematik J. J. Seidel v souvislosti se systémy ekviangulárních přímek. Seidelovo přepnutí vrcholu v v grafu G způsobí, že vrchol v bude sousedit s právě těmi vrcholy grafu G, se kterými předtím nesousedil (ostatní hrany zůstanou nezměněny). Řekneme, že grafy G a G' jsou ekvivalentní v přepnutí, pokud lze graf G pomocí přepnutí vrcholů upravit tak, aby byl izomorfní grafu G'. V přednášce se budeme zabývat vlastnostmi Seidelova přepnutí a také výpočetní složitostí souvisejících algoritmických otázek.