Jak může vypadat centrum?
Úloha číslo: 4132
Zjistěte, které grafy mohou být centrem jiného grafu. Tedy, pro které grafy \(H\) existuje graf \(G\), že když \(C\) je množina vrcholů, které patří do centra \(G\), potom indukovaný podgraf \(G\) na množině \(C\) je izomorfní s \(H\)?
Centrum obecného grafu je podobně jako ve stromu tvořeno vrcholy s minimální výstředností.
Řešení
Je-li \(H\) úplný, stačí vzít \(G=H\).
Jinak k \(H\) přidáme dvě nové hrany \((u,v)\) a \((u’,v’)\) a spojíme vrcholy \(u\) a \(u’\) se všemi vrcholy z \(H\). Výsledný graf \(G\) obsahuje \(H\) jako indukovaný podgraf.
Vrcholy \(H\) mají výstřednost 2, vrcholy \(u\) a \(u’\) mají výstřednost 3, a vrcholy \(v\) a \(v’\) mají výstřednost 4.
Odpověď
Každý neprázdný graf může tvořit centrum grafu.
