Arboricita - Arboricity

The arboricita z neorientovaný graf je minimální počet lesy do kterého mohou být jeho hrany rozdělené. Ekvivalentně je to minimální počet překlenující lesy potřebné k pokrytí všech okrajů grafu. The Nash-Williamsova věta poskytuje nezbytné a dostatečné podmínky, když je graf k-borborický.

Příklad

Oddíl kompletní bipartitní graf K._4,4 do tří lesů, což ukazuje, že má arboricitu tři.

Obrázek ukazuje kompletní bipartitní graf K._4,4, s barvami označujícími rozdělení jeho okrajů do tří lesů. K._4,4 nelze rozdělit na méně lesů, protože jakýkoli les na jeho osmi vrcholech má nejvýše sedm okrajů, zatímco celkový graf má šestnáct okrajů, což je více než dvojnásobný počet okrajů v jednom lese. Proto arboricita K._4,4 je tři.

Arboricita jako měřítko hustoty

Arboricita grafu je měřítkem toho, jak hustý graf je: grafy s mnoha hranami mají vysokou arboricitu a grafy s vysokou arboricitou musí mít hustý podgraf.

Podrobněji, protože každý les n-vrcholů má maximálně n-1 hran, je arboricita grafu s n vrcholy am hranami alespoň ${ Displaystyle lceil m / (n-1) rceil}$. Navíc podgrafy žádného grafu nemohou mít arboricitu větší než samotný graf, nebo ekvivalentně arboricita grafu musí být alespoň maximální arboricitou kteréhokoli z jeho podgrafů. Nash-Williams dokázal, že tyto dvě skutečnosti lze kombinovat k charakterizaci arboricity: pokud necháme n_S a m_S označte počet vrcholů a hran libovolného podgrafu S daného grafu, pak se arboricita grafu rovná ${ displaystyle max _ {S} { lceil m_ {S} / (n_ {S} -1) rceil }.}$

Žádný rovinný graf s ${ displaystyle n}$ vrcholy má maximálně ${ displaystyle 3n-6}$ hrany, ze kterých podle Nash-Williamsova vzorce vyplývá, že rovinné grafy mají arboricitu nejvýše tři. Schnyder použil speciální rozklad rovinného grafu na tři lesy zvané a Schnyderovo dřevo najít a přímé vkládání jakéhokoli rovinného grafu do mřížky malé plochy.

Algoritmy

Arboricitu grafu lze vyjádřit jako speciální případ obecnější dělení matroidů problém, ve kterém si přejeme vyjádřit množinu prvků matroidu jako spojení malého počtu nezávislých množin. V důsledku toho lze arboricitu vypočítat pomocí algoritmu polynomiálního času (Gabow & Westermann 1992 ).

Související pojmy

The anarboricita grafu je maximální počet okrajových disjunktních neacyklických podgrafů, do kterých lze rozdělit okraje grafu.

The hvězdná arboricita grafu je velikost minimálního lesa, jehož každý strom je a hvězda (strom s maximálně jedním nelistovým uzlem), do kterého lze rozdělit okraje grafu. Pokud strom není samotnou hvězdou, jeho arboricita hvězd je dvě, což je patrné z rozdělení hran do dvou podmnožin v lichých a sudých vzdálenostech od kořene stromu. Proto je hvězdná arboricita libovolného grafu alespoň rovná arboricitě a nanejvýš rovná dvojnásobku arboricity.

The lineární arboricita grafu je minimální počet lineární lesy (kolekce cest), do kterých lze rozdělit okraje grafu. Lineární arboricita grafu úzce souvisí s jeho maximem stupeň a jeho číslo svahu.

The pseudoarboricita grafu je minimální počet pseudolesy do kterého lze rozdělit jeho okraje. Ekvivalentně je to maximální poměr hran k vrcholům v libovolném podgrafu grafu, zaokrouhlený na celé číslo nahoru. Stejně jako u arboricity má pseudoarboricita matroidovou strukturu, která umožňuje její efektivní výpočet (Gabow & Westermann 1992 ).

The tloušťka grafu je minimální počet rovinných podgrafů, do kterých lze rozdělit jeho okraje. Protože jakýkoli rovinný graf má arboricitu tři, tloušťka libovolného grafu je alespoň rovna třetině arboricity a nanejvýš rovná arboricitě.

The zvrhlost grafu je maximum indukované podgrafy grafu, minima stupeň vrcholu v podgrafu. Degenerace grafu s arboricitou ${ displaystyle a}$ je alespoň rovno ${ displaystyle a}$, a maximálně rovna ${ displaystyle 2a-1}$. Číslo zbarvení grafu, známé také jako jeho Szekeres-Wilfovo číslo (Szekeres & Wilf 1968 ) se vždy rovná jeho degeneraci plus 1 (Jensen & Toft 1995, str. 77f.).

The síla grafu je zlomková hodnota, jejíž celočíselná část udává maximální počet nesouvislých stromů, které lze vykreslit v grafu. Jedná se o problém balení, který je dvojitý s problémem krytí vyvolaným arboricitou. Tyto dva parametry studovaly společně Tutte a Nash-Williams.

The frakční arboricita je upřesnění arboricity, jak je definováno pro graf ${ displaystyle G}$ tak jako ${ displaystyle max {m_ {S} / (n_ {S} -1) střední S subseteq G }.}$ Jinými slovy, arboricita grafu je stropem frakční arboricity.

The (a, b) -rozložitelnost zobecňuje arboricitu. Graf je ${ displaystyle (a, b)}$-rozložitelné, pokud lze rozdělit jeho okraje ${ displaystyle a + 1}$ množiny, z nichž každá vyvolává les, kromě jedné, která vyvolává graf s maximálním stupněm ${ displaystyle b}$. Graf s arboricitou ${ displaystyle a}$ je ${ displaystyle (a, 0)}$-rozložitelné.

The číslo stromu je minimální počet stromů pokrývajících okraje grafu.

Zvláštní vzhled

Arboricita se objevuje v Goldberg – Seymourova domněnka.

Reference