Grafik birleştirme - Graph amalgamation

İçinde grafik teorisi, bir grafik birleştirme iki grafik arasındaki bir ilişkidir (bir grafik diğerinin birleşimidir). Benzer ilişkiler şunları içerir alt grafikler ve küçükler. Birleşmeler, belirli bir yapıyı sağlam tutarken bir grafiği daha basit bir grafiğe indirgemek için bir yol sağlayabilir. Birleştirme daha sonra orijinal grafiğin özelliklerini anlaşılması daha kolay bir bağlamda incelemek için kullanılabilir. Uygulamalar arasında gömme,^[1] hesaplama cinsi dağılımı,^[2] ve Hamilton ayrışmaları.

Tanım

İzin Vermek ${ displaystyle G}$ ve ${ displaystyle H}$ aynı sayıda kenara sahip iki grafik olması ${ displaystyle G}$ daha fazla köşeye sahip ${ displaystyle H}$. O zaman diyoruz ki ${ displaystyle H}$ bir karışımıdır ${ displaystyle G}$ eğer varsa birebir örten ${ displaystyle phi: E (G) - E (H)}$ ve bir surjeksiyon ${ displaystyle psi: V (G) - V (H)}$ ve şu muhafaza:

• Eğer ${ displaystyle x}$, ${ displaystyle y}$ içinde iki köşe var ${ displaystyle G}$ nerede ${ displaystyle psi (x) neq psi (y)}$, ve ikisi ${ displaystyle x}$ ve ${ displaystyle y}$ kenardan bitişik ${ displaystyle e}$ içinde ${ displaystyle G}$, sonra ${ displaystyle psi (x)}$ ve ${ displaystyle psi (y)}$ kenardan bitişik ${ displaystyle phi (e)}$ içinde ${ displaystyle H}$.
• Eğer ${ displaystyle e}$ tepe noktasında bir döngüdür ${ displaystyle x , V (G)}$, sonra ${ displaystyle phi (e)}$ bir döngü ${ displaystyle psi (x) H içinde}$.
• Eğer ${ displaystyle e}$ katılır ${ displaystyle x, y , V (G)}$, nerede ${ displaystyle x neq y}$, fakat ${ displaystyle psi (x) = psi (y)}$, sonra ${ displaystyle phi (e)}$ bir döngü ${ displaystyle psi (x)}$.^[3]

Unutmayın ki ${ displaystyle G}$ bir grafik veya bir sahte yazı genellikle böyle olacaktır ${ displaystyle H}$ bir pseudograph.

Özellikleri

Kenar renkleri birleşme için değişmez. İki grafik arasındaki tüm kenarlar birbiriyle örtüştüğü için bu açıktır. Ancak, açık olmayabilecek şey şudur: ${ displaystyle G}$ bir tam grafik şeklinde ${ displaystyle K_ {2n + 1}}$ve bir Hamilton ayrışmasını ( Hamilton yolları, sonra bu kenarlar aynı zamanda bir Hamilton Ayrışımı oluşturur. ${ displaystyle H}$.

Misal

Şekil 1: Tüm grafiğin beş köşede bir birleşimi.

Şekil 1, bir ${ displaystyle K_ {5}}$. Kenar renklendirmesinin ve Hamilton Ayrışmasının değişmezliği açıkça görülebilir. İşlev ${ displaystyle phi}$ bir bijeksiyondur ve şekilde harflerle verilmiştir. İşlev ${ displaystyle psi}$ aşağıdaki tabloda verilmiştir.

${ displaystyle v , V (G)}$	${ displaystyle psi (v)}$
${ displaystyle v_ {1}}$	${ displaystyle u_ {2}}$
${ displaystyle v_ {2}}$	${ displaystyle u_ {2}}$
${ displaystyle v_ {3}}$	${ displaystyle u_ {1}}$
${ displaystyle v_ {4}}$	${ displaystyle u_ {3}}$
${ displaystyle v_ {5}}$	${ displaystyle u_ {2}}$

Hamilton ayrışmaları

Birleştirmelerin kullanılabileceği yollardan biri, 2 ile tam grafiklerin Hamilton Ayrışımlarını bulmaktır.n + 1 köşe.^[4] Buradaki fikir, bir grafik almak ve bunun kenar renklendirilmiş bir karışımını oluşturmaktır. ${ displaystyle n}$ renkler ve belirli özellikleri karşılar (ana hat Hamilton ayrışması olarak adlandırılır). Daha sonra, birleşmeyi 'tersine çevirebiliriz' ve ${ displaystyle K_ {2n + 1}}$ Hamilton Ayrışması ile renklendirilmiştir.

İçinde ^[3] Hilton, bunu yapmak için bir yöntemin yanı sıra tüm Hamilton Ayrıştırmalarını tekrar etmeden bulmak için bir yöntemin ana hatlarını çizmektedir. Yöntemler, (kabaca) bir Hamilton ayrışımının ana hatlarına sahip olsaydık, ona ilk olarak tüm grafiğin bir Hamilton ayrışımıyla başlayıp sonra onun için bir karışım bularak ulaşabileceğimizi belirten (kabaca) bir teoreme dayanır.

Notlar

Referanslar

• Bahmanyan, Amin; Rodger, Chris (2012), "Grafik Birleşmeleri Nedir?", Auburn Üniversitesi
• Hilton, A.J. W (1984), "Tam Grafiklerin Hamilton Ayrışımları, Kombinatoryal Teori Dergisi, B Serisi 36, 125–134
• Gross, Jonathan L .; Tucker, Thomas W. (1987), Topolojik Grafik Teorisi, Courier Dover Yayınları, 151
• Brüt, Jonathan L. (2011), "Kübik Dış Düzlemsel Grafiklerin Cins Dağılımları", Journal of Graph Algorithms and Applications, Cilt. 15, hayır. 2, s. 295–316