Oblázkové grafy - Graph pebbling - Wikipedia

Oblázkové grafy je matematický hra hrál na a graf s nulovým nebo více oblázky na každém z nich vrcholy. „Hra“ se skládá ze série oblázkových tahů. Oblázkový pohyb v grafu spočívá ve výběru vrcholu s alespoň dvěma oblázky, odstranění dvou oblázků z něj a přidání jednoho k sousednímu vrcholu (druhý odstraněný oblázek je vyřazen ze hry). π (G), oblázkové číslo grafu G, je nejnižší přirozené číslo n který splňuje následující podmínku:

Vzhledem k jakémukoli cílovému nebo kořenovému vrcholu v grafu a jakékoli počáteční konfiguraci n oblázky v grafu, je možné po sérii oblázkových tahů dosáhnout nové konfigurace, ve které má určený kořenový vrchol jeden nebo více oblázků.

Například na grafu se 2 vrcholy a 1 hranou, která je spojuje, je oblázkové číslo 2. Bez ohledu na to, jak jsou tyto dva oblázky umístěny na vrcholech grafu, je vždy možné přesunout oblázek na libovolný vrchol v grafu. Jednou z ústředních otázek oblázkování grafů je hodnota π (G) pro daný graf G.

Mezi další témata v pebblingu patří oblázkové obálky, optimální oblázky, oblázkové obálky nadvlády, hranice a prahové hodnoty pro čísla oblázků, hluboké grafy a další.

π (G) - oblázkové číslo grafu

Hru oblázků nejprve navrhli Lagarias a Saks jako nástroj pro řešení konkrétního problému v teorie čísel. V roce 1989 F.R.K. Chung představil koncept v literatuře^[1] a definoval oblázkové číslo, π (G).

Oblázkové číslo pro a kompletní graf na n vrcholy lze snadno ověřit n: Kdybychom měli (n - 1) oblázky, které se dají do grafu, pak bychom mohli dát jeden oblázek na každý vrchol kromě cíle. Protože žádný vrchol nemá dva nebo více oblázků, nejsou možné žádné pohyby, takže je nemožné umístit oblázek na cíl. Oblázkové číslo tedy musí být větší než n - 1. Dáno n oblázky, existují dva možné případy. Pokud má každý vrchol jeden oblázek, nejsou nutné žádné pohyby. Pokud je jakýkoli vrchol holý, alespoň jeden další vrchol musí mít na sobě dva oblázky a jeden pohyb oblázků umožňuje přidání oblázku k jakémukoli cílovému vrcholu v celém grafu.^[1]

π (G) pro rodiny grafů

Oblázkové číslo je známé pro následující rodiny grafů:

• ${ displaystyle pi (K_ {n}) , = , n}$, kde ${ displaystyle K_ {n}}$ je kompletní graf na n vrcholy.^[1]
• ${ displaystyle pi (P_ {n}) , = , 2 ^ {n-1}}$, kde ${ displaystyle P_ {n}}$ je graf cesty na n vrcholy.^[1]
• ${ displaystyle pi (W_ {n}) , = , n}$, kde ${ displaystyle W_ {n}}$ je graf kola na n vrcholy.

Grahamova oblázková domněnka

Nevyřešený problém v matematice: Je oblázkové číslo kartézského součinu grafů nanejvýš součinem oblázkového čísla grafů? (více nevyřešených úloh z matematiky)

Chung (1989) připsáno Ronald Graham s domněnkou, že oblázkové číslo a Kartézský součin grafů je nanejvýš rovna součinu oblázkových čísel faktorů ve výrobku.^[2] Toto začalo být známé jako Grahamova oblázková domněnka. Od roku 2019^{[Aktualizace]}, zůstává nevyřešen, i když jsou známy zvláštní případy.^[3]

γ (G) - číslo oblázkového obálky grafu

Crull et al. představil koncept krycího oblázku. γ (G), číslo oblázkového obálky grafu je minimální počet oblázků potřebných k tomu, aby z jakéhokoli počátečního uspořádání oblázků byl po sérii oblázkových tahů graf zakryt: na něm je alespoň jeden oblázek každý vrchol.^[4] Výsledek zvaný stohovací věta najde krycí oblázkové číslo pro libovolný graf.^[5][6]

Věta o stohování

Podle věty o stohování dojde k počáteční konfiguraci oblázků, která vyžaduje řešení většiny oblázků, když jsou všechny oblázky umístěny na jednom vrcholu. Na základě tohoto pozorování definujte

${ displaystyle s (v) = součet _ {u ve V (G)} 2 ^ {d (u, v)}}$

pro každý vrchol proti v G, kde d(u, proti) označuje vzdálenost od u na proti. Pak je krycí oblázkové číslo největší s(proti), který vede.

γ (G) pro rodiny grafů

Oblázkové číslo obalu je známé pro následující rodiny grafů:

• ${ displaystyle gamma (K_ {n}) , = , 2n-1}$, kde ${ displaystyle K_ {n}}$ je kompletní graf na n vrcholy.
• ${ displaystyle gamma (P_ {n}) , = , 2 ^ {n} -1}$, kde ${ displaystyle P_ {n}}$ je cesta na n vrcholy.
• ${ displaystyle gamma (W_ {n}) , = , 4n-9}$, kde ${ displaystyle W_ {n}}$ je graf kola na n vrcholy.^[7]

Viz také

• Oblázková hra
• Důkaz o prostoru

Reference

Další čtení