Çekirdek (grafik teorisi) - Core (graph theory)

Olarak matematiksel alanında grafik teorisi , bir çekirdek , bir davranışını tanımlayan bir kavramdır grafik göre grafik homomorfizmalar .

Tanım

Her homomorfizma bir izomorfizm ise , grafik bir çekirdektir , yani . ${\görüntüleme stili C}$${\ Displaystyle f:C\to C}$${\görüntüleme stili C}$

Bir grafiğin çekirdeği , öyle bir grafiktir ki ${\görüntüleme stili G}$${\görüntüleme stili C}$

1. Bir homomorfizması gelen söz konusudur için ,${\görüntüleme stili G}$${\görüntüleme stili C}$
2. oradan bir homomorfizması var için ve${\görüntüleme stili C}$${\görüntüleme stili G}$
3. ${\görüntüleme stili C}$ Bu özellik ile minimaldir.

İki grafiğin, izomorfik çekirdekleri varsa, homomorfizma eşdeğeri veya homo eşdeğeri olduğu söylenir.

Örnekler

• Herhangi bir tam grafik bir çekirdektir.
• Tek uzunlukta bir döngü kendi çekirdeğidir.
• Eşit uzunluktaki her iki döngüde ve daha genel olarak her iki ikili grafikte homo-eşdeğerdir. Bu grafikler, her çekirdek iki tepe tam grafiktir K ₂ .

Özellikleri

Her grafiğin izomorfizme kadar benzersiz olarak belirlenmiş bir çekirdeği vardır . Bir grafiktir çekirdek G her zaman olduğu kaynaklı alt grafiğinin bölgesinin G . If ve sonra grafikler ve mutlaka homomorfik olarak eşdeğerdir . ${\ Displaystyle G\'den H'ye}$${\ Displaystyle H\'den G'ye}$${\görüntüleme stili G}$${\görüntüleme stili H}$

hesaplama karmaşıklığı

Bu ise NP-tam bir grafiktir kendi öz olup olmadığını test etmek için bir grafiktir uygun bir alt grafiği için bir homomorfizması sahip olup olmadığını test etmek ve ko-NP-tam (yani böyle bir homomorfizması var olup olmadığını) ( Hell & Nešetřil 1992 ).

Referanslar

• Godsil, Chris ve Royle, Gordon . Cebirsel Grafik Teorisi. Matematik Lisansüstü Metinleri, Cilt. 207. Springer-Verlag, New York, 2001. Bölüm 6 bölüm 2.
• Cehennem, Pavol ; Nešetřil, Jaroslav (1992), "Bir grafiğin çekirdeği", Discrete Mathematics , 109 (1–3): 117–126, doi : 10.1016/0012-365X(92)90282-K , MR  1192374.
• Neşetil, Jaroslav ; Ossona de Mendez, Patrice (2012), "Önerme 3.5", Sparsity: Graphs, Structures and Algorithms , Algorithms and Combinatorics, 28 , Heidelberg: Springer, s. 43, doi : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR  2920058.