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.

Obtížnost: Středně těžká úloha
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze