Filtr seznamu úloh?
Zvolte požadované hodnoty úrovní a požadované štítky. V obsahu budou zobrazeny pouze úlohy mající jednu ze zvolených úrovní každé škály a alespoň jeden štítek. Pokud chcete filtrovat pouze podle některých škál nebo jen podle štítků, nechte ostatní skupiny prázdné.
Škály
Obtížnost
Štítky
Typ úlohy
«
«
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.