Dimenze (teorie grafů) - Dimension (graph theory)

v matematika, a to zejména v teorie grafů, rozměr grafu je nejmenší celé číslo $n$ taková, že existuje "klasická reprezentace" grafu v Euklidovský prostor dimenze $n$ přičemž všechny hrany mají jednotkovou délku.

V klasickém zobrazení musí být vrcholy odlišné body, ale hrany se mohou navzájem protínat.^[1]

Dimenze grafu $G$ je psáno: ${ displaystyle dim G}$ .

Například Petersenův graf lze nakreslit hranami jednotek v ${ displaystyle E ^ {2}}$ , ale ne v ${ displaystyle E ^ {1}}$ : jeho rozměr je tedy 2 (viz obrázek vpravo).

Tento koncept představil v roce 1965 Paul Erdős, Frank Harary a William Tutte.^[2] Zobecňuje koncept graf jednotkové vzdálenosti do více než 2 rozměrů.

Příklady

Se 4 stejně rozmístěnými body potřebujeme 3 rozměry.

Kompletní graf

V nejhorším případě je každá dvojice vrcholů spojena a dává a kompletní graf.

Na ponořit celý graf ${ displaystyle K_ {n}}$ protože všechny hrany mají jednotkovou délku, potřebujeme euklidovský prostor dimenze ${ displaystyle n-1}$ .^[3] Například ponoření trvá dvě dimenze ${ displaystyle K_ {3}}$ (rovnostranný trojúhelník) a tři ponořit ${ displaystyle K_ {4}}$ (pravidelný čtyřstěn), jak je znázorněno vpravo.

{ displaystyle dim K_ {n} = n-1}

Jinými slovy, rozměr celého grafu je stejný jako rozměr celého grafu simplexní se stejným počtem vrcholů.

Kompletní bipartitní graf

{ displaystyle K_ {4,2}}

nakreslené v euklidovském 3-prostoru.

Kompletní bipartitní grafy

A hvězdný graf nakreslen v rovině s hranami jednotkové délky.

Všechno hvězdné grafy ${ displaystyle K_ {m, 1}}$ , pro ${ displaystyle m geq 3}$ , mají rozměr 2, jak je znázorněno na obrázku vlevo. Hvězdné grafy s $m$ rovné 1 nebo 2 vyžaduje pouze rozměr 1.

Rozměr a kompletní bipartitní graf ${ displaystyle K_ {m, 2}}$ , pro ${ displaystyle m geq 3}$ , lze nakreslit jako na obrázku vpravo umístěním $m$ vrcholy na kružnici, jejíž poloměr je menší než jednotka, a další dva vrcholy na každé straně roviny kružnice ve vhodné vzdálenosti od ní. ${ displaystyle K_ {2,2}}$ má rozměr 2, protože může být nakreslen jako jednotkový kosočtverec v rovině.

Teorém — Dimenze obecného úplného bipartitního grafu ${ displaystyle K_ {m, n}}$ , pro ${ displaystyle m geq 3}$ a ${ displaystyle n geq 3}$ , je 4.

Důkaz

Abychom ukázali, že 4prostor je dostačující, stejně jako v předchozím případě, použijeme kružnice.

Označení souřadnic 4prostoru pomocí ${ displaystyle w, x, y, z}$ , uspořádáme jednu sadu vrcholů libovolně na kružnici danou ${ displaystyle w ^ {2} + x ^ {2} = a, y = 0, z = 0}$ kde ${ displaystyle 0$ , a druhá množina libovolně na kruhu ${ displaystyle y ^ {2} + z ^ {2} = 1-a, w = 0, x = 0}$ . Pak vidíme, že vzdálenost mezi jakýmkoli vrcholem v jedné sadě a jakýmkoli vrcholem v druhé sadě je ${ displaystyle { sqrt {w ^ {2} + x ^ {2} + y ^ {2} + z ^ {2}}} = { sqrt {a + 1-a}} = 1}$ .

Můžeme také ukázat, že podgraf ${ displaystyle K_ {3,3}}$ nepřipouští takové zobrazení v prostoru dimenze menším než 3:

Pokud takové zobrazení existuje, pak tři body ${ displaystyle A_ {1}}$ , ${ displaystyle A_ {2}}$ a ${ displaystyle A_ {3}}$ leží na jednotkové kouli se středem ${ displaystyle B_ {1}}$ . Podobně leží na jednotkových koulích se středy ${ displaystyle B_ {2}}$ a ${ displaystyle B_ {3}}$ . První dvě koule se musí protínat v kruhu, v bodě nebo vůbec; přizpůsobit tři odlišné body ${ displaystyle A_ {1}}$ , ${ displaystyle A_ {2}}$ a ${ displaystyle A_ {3}}$ , musíme předpokládat kruh. Buď tento kruh leží zcela na sféře třetí jednotky, z čehož vyplývá, že se třetí koule shoduje s jednou z ostatních dvou, takže ${ displaystyle B_ {1}}$ , ${ displaystyle B_ {2}}$ a ${ displaystyle B_ {3}}$ nejsou všechny odlišné; nebo ne, takže jeho průsečík s třetí sférou není větší než dva body, což je nedostatečné pro umístění ${ displaystyle A_ {1}}$ , ${ displaystyle A_ {2}}$ a ${ displaystyle A_ {3}}$ .

Shrnout:

{ displaystyle dim K_ {m, n} = 1,2,3 { text {nebo}} 4}

, v závislosti na hodnotách

m

a

n

.

Rozměr a chromatické číslo

Teorém — Dimenze libovolného grafu $G$ je vždy menší nebo rovno dvojnásobku jeho chromatické číslo:

{ displaystyle dim G leq 2 , chi (G)}

Důkaz

Tento důkaz také používá kruhy.

Píšeme $n$ pro chromatický počet $G$ a přiřadit celá čísla ${ displaystyle (1..n)}$ do $n$ barvy. v ${ displaystyle 2n}$ -dimenzionální euklidovský prostor s vyznačenými rozměry ${ displaystyle x_ {1}, x_ {2}, .. x_ {2n}}$ , uspořádáme všechny barevné vrcholy $n$ libovolně na kružnici danou ${ displaystyle x_ {2n-2} ^ {2} + x_ {2n-1} ^ {2} = 1/2, quad x_ {i} | (i neq 2 {n-2}, i neq 2 {n-1}) = 0}$ .

Pak vzdálenost od vrcholu barvy $str$ na vrchol barvy $q$ darováno ${ displaystyle { sqrt {x_ {2p-2} ^ {2} + x_ {2p-1} ^ {2} + x_ {2q-2} ^ {2} + x_ {2q-1} ^ {2} }} = { sqrt {1/2 + 1/2}} = 1}$ .

Euklidovská dimenze

Graf kola s odstraněným jedním paprskem má rozměr 2.

Stejné kolo má euklidovský rozměr 3.

Výše uvedená definice dimenze grafu říká, že minimální $n$ zastoupení:

pokud dva vrcholy $G$ jsou spojeny hranou, musí být od sebe vzdáleny;
dva vrcholy v jednotkové vzdálenosti od sebe však nemusí být nutně spojeny hranou.

Někteří autoři tuto definici odmítají. V roce 1991 navrhl jinou definici Alexander Soifer, za to, co nazval Euklidovská dimenze grafu.^[4] Dříve, v roce 1980, Paul Erdős a Miklós Simonovits už to navrhl se jménem věrný rozměr.^[5] Podle této definice je minimální $n$ reprezentace je taková, že dva vrcholy grafu jsou spojeny kdyby a jen kdyby jejich reprezentace jsou ve vzdálenosti 1.

Následující obrázky ukazují rozdíl mezi těmito definicemi v případě a graf kola s centrálním vrcholem a šesti periferními vrcholy, přičemž jeden paprsek byl odstraněn. Jeho reprezentace v rovině umožňuje dva vrcholy ve vzdálenosti 1, ale nejsou spojeny.

Tuto dimenzi píšeme jako ${ displaystyle operatorname {Edim} G}$ . Nikdy to není menší než dimenze definovaná výše:

{ displaystyle dim G leq operatorname {Upravit} G}

Euklidovská dimenze a maximální stupeň

Paul Erdős a Miklós Simonovits v roce 1980 prokázali následující výsledek:^[5]

Teorém — Euklidovská dimenze grafu $G$ není více než dvojnásobek jeho maxima stupeň plus jedna:

{ displaystyle operatorname {Edim} G leq 2 , Delta (G) +1}

Výpočetní složitost

to je NP-tvrdé a konkrétněji kompletní pro existenciální teorie skutečností, aby se otestovalo, zda dimenze nebo euklidovská dimenze daného grafu je nanejvýš danou hodnotou. Problém zůstává těžký i při testování, zda je dimenze nebo euklidovská dimenze dvě.^[6]

Reference

^ Někteří matematici to přísně považují za „ponoření „, ale mnoho teoretiků grafů, včetně Erdőse, Hararyho a Tutté, používá tento výraz“vkládání ".
^ Erdős, P .; Harary, F .; Tutte, W. T. (1965). „O dimenzi grafu“ (PDF). Mathematika. 12 (2): 118–122. doi:10.1112 / s0025579300005222.
^ Kavangh, Ryan. „Průzkumy dimenzionality grafů“ (PDF). Citováno 16. srpna 2018.
^ Soifer, Alexander (2009). Matematická omalovánka. Springer. ISBN 978-0-387-74640-1.
^ ^A ^b Erdős, P .; Simonovits, M. (1980). Msgstr "Na chromatickém počtu geometrických grafů". Ars Comb. (9): 229–246.
^ Schaefer, Marcus (2013), „Realizovatelnost grafů a vazeb“, in Pach, János (vyd.), Třicet esejů o teorii geometrických grafů, Springer, str. 461–482, CiteSeerX 10.1.1.220.9651, doi:10.1007/978-1-4614-0110-0_24, ISBN 978-1-4614-0109-4.

[1] Někteří matematici to přísně považují za „ponoření „, ale mnoho teoretiků grafů, včetně Erdőse, Hararyho a Tutté, používá tento výraz“vkládání ".

[2] Erdős, P .; Harary, F .; Tutte, W. T. (1965). „O dimenzi grafu“ (PDF). Mathematika. 12 (2): 118–122. doi:10.1112 / s0025579300005222.

[3] Kavangh, Ryan. „Průzkumy dimenzionality grafů“ (PDF). Citováno 16. srpna 2018.

[4] Soifer, Alexander (2009). Matematická omalovánka. Springer. ISBN 978-0-387-74640-1.

[esi-5] A ^b Erdős, P .; Simonovits, M. (1980). Msgstr "Na chromatickém počtu geometrických grafů". Ars Comb. (9): 229–246.

[6] Schaefer, Marcus (2013), „Realizovatelnost grafů a vazeb“, in Pach, János (vyd.), Třicet esejů o teorii geometrických grafů, Springer, str. 461–482, CiteSeerX 10.1.1.220.9651, doi:10.1007/978-1-4614-0110-0_24, ISBN 978-1-4614-0109-4.

[1]

[2]

[3]

[4]

[5]

[6]