Core (teorie grafů) - Core (graph theory) - Wikipedia

V matematický pole teorie grafů, a jádro je pojem, který popisuje chování a graf s ohledem na homomorfismy grafů.

Definice

Graf ${ displaystyle C}$ je jádro pokud každý homomorfismus ${ displaystyle f: C až C}$ je izomorfismus, tj. je to bijekce vrcholů ${ displaystyle C}$.

A jádro grafu ${ displaystyle G}$ je graf ${ displaystyle C}$ takhle

1. Existuje homomorfismus z ${ displaystyle G}$ na ${ displaystyle C}$,
2. existuje homomorfismus z ${ displaystyle C}$ na ${ displaystyle G}$, a
3. ${ displaystyle C}$ je u této vlastnosti minimální.

Dva grafy se považují za ekvivalent homomorfismu nebo homekvivalent, pokud mají izomorfní jádra.

Příklady

• Žádný kompletní graf je jádro.
• A cyklus liché délky je jeho vlastní jádro.
• Každé dva cykly rovnoměrné délky a obecněji každé dva bipartitní grafy jsou homekvivalentní. Jádrem každého z těchto grafů je dvouvrcholový úplný graf K.₂.

Vlastnosti

Každý graf má jádro, které je určeno jedinečně, až izomorfismus. Jádro grafu G je vždy indukovaný podgraf z G. Li ${ displaystyle G až H}$ a ${ displaystyle H to G}$ pak grafy ${ displaystyle G}$ a ${ displaystyle H}$ jsou nutně homomorfně ekvivalentní.

Výpočetní složitost

to je NP-kompletní otestovat, zda má graf homomorfismus se správným podgrafem, a co-NP-complete otestovat, zda je graf jeho vlastním jádrem (tj. zda takový homomorfismus neexistuje) (Hell & Nešetřil 1992 ).

Reference

• Godsil, Chris, a Royle, Gordone. Algebraická teorie grafů. Postgraduální texty z matematiky, sv. 207. Springer-Verlag, New York, 2001. Kapitola 6 oddíl 2.
• Sakra, Pavol; Nešetřil, Jaroslav (1992), „Jádro grafu“, Diskrétní matematika, 109 (1–3): 117–126, doi:10.1016 / 0012-365X (92) 90282-K, PAN  1192374.
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), „Proposition 3.5“, Sparsity: Graphs, Structures, and AlgorithmsAlgoritmy a kombinatorika, 28, Heidelberg: Springer, str. 43, doi:10.1007/978-3-642-27875-4, ISBN  978-3-642-27874-7, PAN  2920058.