Rdzeń (teoria grafów) - Core (graph theory)

W matematycznej dziedzinie teorii grafów , o rdzeń jest pojęciem, które opisuje zachowanie wykresu względem homomorfizmów wykresu .

Definicja

Wykres jest rdzeniem, jeśli każdy homomorfizm jest izomorfizmem , czyli jest bijekcją wierzchołków . ${\displaystyle C}$${\ Displaystyle f: C \ do C}$${\displaystyle C}$

Rdzeń wykresu jest wykresem , tak że ${\ Displaystyle G}$${\displaystyle C}$

1. Istnieje homomorfizm od do ,${\ Displaystyle G}$${\displaystyle C}$
2. istnieje homomorfizm od do i${\displaystyle C}$${\ Displaystyle G}$
3. ${\displaystyle C}$ jest minimalny w przypadku tej właściwości.

Mówi się, że dwa grafy są równoważne homomorfizmowi lub ekwiwalentowi hom, jeśli mają izomorficzne rdzenie.

Przykłady

• Każdy kompletny wykres jest rdzeniem.
• Cykl o długości nieparzystej jest jego własny rdzeń.
• Co dwa cykle o parzystej długości, a ogólniej co dwa grafy dwudzielne są równoważne hom. Rdzeniem każdego z tych grafów jest dwuwierzchołkowy kompletny graf K ₂ .

Nieruchomości

Każdy graf ma rdzeń, który jest określany jednoznacznie, aż do izomorfizmu . Rdzeń grafu G zawsze jest indukowana subgraph z G . Jeśli i wtedy wykresy i są z konieczności homomorficznie równoważne . ${\ Displaystyle G \ do H}$${\ Displaystyle H \ do G}$${\ Displaystyle G}$${\ Displaystyle H}$

Złożoność obliczeniowa

To jest NP-zupełny , aby sprawdzić, czy wykres ma homomorfizm do prawidłowego podgrafu i co-NP-zupełny, aby sprawdzić, czy wykres jest jego własny rdzeń (czyli czy nie istnieje taki homomorfizm) ( Piekło & Nešetřil 1992 ).

Bibliografia

• Godsil, Chris i Royle, Gordon . Teoria grafów algebraicznych. Teksty magisterskie z matematyki, t. 207. Springer-Verlag, Nowy Jork, 2001. Rozdział 6 sekcja 2.
• Piekło, Pawle ; Nešetřil, Jaroslav (1992), "Rdzeń wykresu", Matematyka dyskretna , 109 (1-3): 117-126, doi : 10.1016/0012-365X (92) 90282-K , MR  1192374.
• Nešetřil, Jarosław ; Ossona de Mendez, Patrice (2012), „Propozycja 3.5”, Rzadkość: wykresy, struktury i algorytmy , Algorytmy i kombinatoryka, 28 , Heidelberg: Springer, s. 43, doi : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR  2920058.