Sloučení grafu - Graph amalgamation

v teorie grafů, a sloučení grafů je vztah mezi dvěma grafy (jeden graf je sloučením jiného). Podobné vztahy zahrnují podgrafy a nezletilí. Sloučení může poskytnout způsob, jak zredukovat graf na jednodušší graf a přitom zachovat neporušenou určitou strukturu. Sloučení lze poté použít ke studiu vlastností původního grafu ve srozumitelnějším kontextu. Mezi aplikace patří vkládání,^[1] distribuce výpočetního rodu,^[2] a Hamiltonovské rozklady.

Definice

Nechat ${ displaystyle G}$ a ${ displaystyle H}$ být dva grafy se stejným počtem hran, kde ${ displaystyle G}$ má více vrcholů než ${ displaystyle H}$. Pak to říkáme ${ displaystyle H}$ je sloučením ${ displaystyle G}$ pokud existuje bijekce ${ displaystyle phi: E (G) až E (H)}$ a a surjection ${ displaystyle psi: V (G) až V (H)}$ a následující blokování:

• Li ${ displaystyle x}$, ${ displaystyle y}$ jsou dva vrcholy ${ displaystyle G}$ kde ${ displaystyle psi (x) neq psi (y)}$a obojí ${ displaystyle x}$ a ${ displaystyle y}$ sousedí s hranou ${ displaystyle e}$ v ${ displaystyle G}$, pak ${ displaystyle psi (x)}$ a ${ displaystyle psi (y)}$ sousedí s hranou ${ displaystyle phi (e)}$ v ${ displaystyle H}$.
• Li ${ displaystyle e}$ je smyčka na vrcholu ${ displaystyle x ve V (G)}$, pak ${ displaystyle phi (e)}$ je smyčka ${ displaystyle psi (x) v H}$.
• Li ${ displaystyle e}$ připojí se ${ displaystyle x, y ve V (G)}$, kde ${ displaystyle x neq y}$, ale ${ displaystyle psi (x) = psi (y)}$, pak ${ displaystyle phi (e)}$ je smyčka ${ displaystyle psi (x)}$.^[3]

Všimněte si, že zatímco ${ displaystyle G}$ může to být graf nebo a pseudograf, obvykle tomu tak bude ${ displaystyle H}$ je pseudograf.

Vlastnosti

Barvení hran jsou invariantní ke sloučení. To je zřejmé, protože všechny hrany mezi dvěma grafy jsou navzájem v bijekci. Co však nemusí být zřejmé, je, že pokud ${ displaystyle G}$ je kompletní graf formuláře ${ displaystyle K_ {2n + 1}}$a obarvíme hrany tak, abychom určili hamiltonovský rozklad (rozklad na Hamiltonovské cesty, pak tyto hrany také tvoří Hamiltoniánský rozklad v ${ displaystyle H}$.

Příklad

OBRÁZEK ​​1: Sloučení celého grafu na pěti vrcholech.

Obrázek 1 ilustruje sloučení ${ displaystyle K_ {5}}$. Invariance zbarvení hran a Hamiltonovského rozkladu je jasně vidět. Funkce ${ displaystyle phi}$ je bijekce a na obrázku je uvedena jako písmena. Funkce ${ displaystyle psi}$ je uveden v tabulce níže.

${ displaystyle v 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}}$

Hamiltonovské rozklady

Jedním ze způsobů, jak lze sloučení použít, je najít Hamiltonovské dekompozice úplných grafů s 2n + 1 vrcholy.^[4] Myšlenkou je vzít graf a vytvořit jeho sloučení, které je zbarveno hranami ${ displaystyle n}$ barvy a splňuje určité vlastnosti (tzv. obrys Hamiltonovského rozkladu). Poté můžeme sloučení „zvrátit“ a je nám ponecháno ${ displaystyle K_ {2n + 1}}$ zabarvený v hamiltonovském rozkladu.

v ^[3] Hilton nastiňuje způsob, jak toho dosáhnout, a také způsob, jak najít všechny hamiltonovské rozklady bez opakování. Metody se spoléhají na teorém, který poskytuje a který (zhruba) uvádí, že pokud máme obrys hamiltonovského rozkladu, mohli bychom k němu dospět tak, že nejprve začneme hamiltonovským rozkladem celého grafu a poté pro něj najdeme sloučení.

Poznámky

Reference

• Bahmanian, Amin; Rodger, Chris (2012), „Co jsou to Amalgamace grafů?“, Auburn University
• Hilton, A. J. W (1984), "Hamiltonovské rozklady kompletních grafů, Journal of Combinatorial Theory, Série B 36, 125–134
• Gross, Jonathan L .; Tucker, Thomas W. (1987), topologická teorie grafů, Publikace Courier Dover, 151
• Gross, Jonathan L. (2011), "Rodové distribuce kubických vnějších rovinných grafů", Journal of Graph Algorithms and Applications, Sv. 15, č. 2, s. 295–316