Grafikon dimenzió

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. március 5-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A gráf dimenziója a legkisebb n egész szám , amelynél létezik a gráf "klasszikus reprezentációja" egy egységnyi élhosszúságú n dimenziójú euklideszi térben .

A klasszikus ábrázolásban minden csúcsnak külön kell lennie, de az élek metszhetik egymást [1] .

A G gráf dimenzióját így írjuk fel . $\dim G$

Például a Petersen-gráf megrajzolható egység élekkel -ben, de nem -ben , így a mérete 2 (lásd a jobb oldali ábrát). $E^{2}$ $E^{1}$

A koncepciót 1965-ben Erdős Pál , Frank Harari és William Tutt javasolta [2] . Általánosítja az egységnyi távolság grafikon fogalmát 2-nél nagyobb méretekre.

Példák

Teljes grafikon

A legrosszabb esetben minden csúcspár össze van kötve, ami egy teljes gráfot eredményez .

Egy teljes gráf bemerítéséhez egységnyi hosszúságú élekkel, szükségünk van egy dimenziójú euklideszi térre [3] . Például szüksége van egy kétdimenziós térre a merítéshez (egyenlő oldalú háromszög) és egy háromdimenziós térre a bemerítéshez ( egy szabályos tetraéder ), amint az a jobb oldalon látható. $K_n$ $n-1$ $K_{3}$ $K_{4}$

\dim K_{n}=n-1

Más szóval, egy teljes gráf dimenziója megegyezik egy azonos számú csúcsú szimplex dimenziójával.

Teljes kétrészes gráfok

Az összes csillag mérete 2, amint az a bal oldali ábrán látható . Azoknál a csillagoknál, amelyeknél m egyenlő 1 vagy 2, elegendő az 1-es méret. ${\displaystyle K_{m,1))$ $m\geqslant 3$

Egy teljes bipartit gráf a jobb oldali ábrán látható módon rajzolható meg úgy, hogy egynél kisebb sugarú körön m csúcsot helyezünk el, a másik két pont a kör síkjának mindkét oldalán, megfelelő távolságra helyezkedik el. 2-es dimenzióval rendelkezik, mivel a síkra rombuszként rajzolható. $K_{m,2}$ $m\geqslant 3$ $K_{2,2}$

A teljes kétrészes gráf dimenziója és esetén egyenlő 4-gyel. $K_{{m,n}}$ $m\geqslant 3$ $n\geqslant 3$

Bizonyíték

Annak bemutatására, hogy a 4 dimenziós tér elegendő, mint az előző esetben, köröket használunk.

Jelöljük a 4-dimenziós tér koordinátáit . Az egyik csúcshalmazt tetszőlegesen a körre helyezzük , ahol , a másikat pedig tetszőlegesen a körre . Látjuk, hogy az első halmazból származó bármely csúcs és a második halmaz bármely csúcsa közötti távolság . $w,x,y,z$ $w^{2}+x^{2}=a,y=0,z=0$ $0<a<1$ $y^{2}+z^{2}=1-a,w=0,x=0$ ${\sqrt {w^{2}+x^{2}+y^{2}+z^{2}}}={\sqrt {a+1-a}}=1$

Megmutathatjuk azt is, hogy a részgráf nem teszi lehetővé az ilyen ábrázolást 4-nél kisebb dimenzióban: $K_{{3,3}}$

Ha létezik ilyen ábrázolás, akkor a három pont , és a középponttal rendelkező egységgömbön fekszik . Hasonlóképpen, egységgömbökön fekszenek központokkal és . Az első két gömbnek egy körben, egy pontban kell metszenie, vagy egyáltalán nem metszik egymást. Három különböző pont elhelyezéséhez fel kell tételeznünk, hogy a metszéspont egy kör. Vagy ez a kör teljesen a harmadik egységgömbön fekszik, ami azt jelenti, hogy a harmadik gömb egybeesik az első kettő közül az egyikkel, így , és nem mind különböznek egymástól. Ha a körök nem egy körben metszik egymást, akkor legfeljebb két pontban metszik a harmadik gömböt, és ez nem elég három pont elrendezéséhez , és . $A_{1}$ $A_{2}$ $A_{3}$ $B_1$ $B_{2}$ $B_{3}$ $A_{1}$ $A_{2}$ $A_{3}$ $B_1$ $B_{2}$ $B_{3}$ $A_{1}$ $A_{2}$ $A_{3}$

Végül is:

\dim K_{m,n}=1,2,3,4

, m és n értékétől függően .

Méret és kromatikus szám

A G gráf mérete mindig kisebb vagy egyenlő a kromatikus szám kétszeresével :

\dim G\leqslant 2\,\chi (G)

Bizonyíték

Ez a bizonyítás köröket használ.

Jelölje n -nel a G gráf kromatikus számát, és rendeljen egész számot n színhez . A dimenziós euklideszi térben, amelynek méreteit jelöli , az összes n színű csúcsot tetszőlegesen elhelyezzük az által adott körön . $(1..n)$ $2n$ ${\displaystyle x_{1},x_{2},..x_{2n))$ $x_{2n-2}^{2}+x_{2n-1}^{2}=1/2,\quad x_{i}|(i\neq 2{n-2},i\neq 2{n-1})=0$

Ekkor a p szín csúcsától a q szín csúcsáig mért távolságot a képlet adja meg . ${\sqrt {x_{2p-2}^{2}+x_{2p-1}^{2}+x_{2q-2}^{2}+x_{2q-1}^{2} }}={\sqrt {1/2+1/2}}=1$

Euklideszi dimenzió

A gráfdimenzió fent megadott definíciója az n - minimális ábrázolásra vonatkozik:

ha a G gráf két csúcsát él köti össze, akkor egy távolságra kell lenniük;
azonban két, egy távolságra lévő csúcsot nem kell éllel összekötni.

Ezt a meghatározást egyes szerzők elutasítják. Egy másik definíciót javasolt 1991-ben Alexander Soifer , amelyet a gráf euklideszi dimenziójának nevez [4] . Ezt megelőzően, 1980-ban Erdős Pal és Szymonowicz Miklós már javasolta ugyanazt a definíciót, amelyet valódi dimenziónak neveztek [5] . E definíció szerint n -minimális reprezentáció az, amelyben két gráfcsúcs akkor és csak akkor kapcsolódik egymáshoz, ha az ábrázolásuk 1 távolságra van.

A szemközti ábra mutatja a különbséget ezek között a meghatározások között egy olyan kerék esetében, amelynek központi csúcsa és hat periférikus csúcsa van, egy küllővel. A gráf síkbeli ábrázolása lehetővé teszi, hogy két csúcs 1 távolságra legyen, de nincsenek összekapcsolva.

Az euklideszi távolságot így írjuk . Soha nem kisebb, mint a fent meghatározott távolság: $\operatorname {Edim} G$

\dim G\leqslant \operátornév {Edim} G

Euklideszi méret és maximális fok

Erdős Pál és Simonovich Miklós 1980-ban a következő eredményt bizonyították [5] :

A G gráf euklideszi dimenziója legfeljebb kétszerese a maximális teljesítményének + 1:

\operatorname {Edim} G\leqslant 2\,\Delta (G)+1

Számítási összetettség

A probléma NP-nehéz , pontosabban a valós számok egzisztenciális elmélete számára teljes annak meghatározása, hogy egy adott értékű gráf dimenziója vagy euklideszi dimenziója nagyobb-e vagy sem. A probléma még annak ellenőrzése is nehéz, hogy a dimenzió vagy az euklideszi dimenzió egyenlő-e kettővel [6] .

Jegyzetek

↑ Egyes matematikusok ezt " beágyazásnak " tartják, de sok gráfelméleti szakember, köztük Erdős, Harari és Tatta is használta a " beágyazás " kifejezést.
↑ Erdős, Harary, Tutte, 1965 , p. 118–122.
↑ Kavangh, Ryan Feltárások a gráfok dimenzióiról . Letöltve: 2018. augusztus 16. (határozatlan)
↑ Soifer, 2009 .
↑ 1 2 Erdős, Simonovits, 1980 , p. 229–246.
↑ Schaefer, 2013 , p. 461–482.

Irodalom

Erdős P., Harary F., Tutte WT Egy gráf dimenziójáról // Mathematika. - 1965. - T. 12 . - doi : 10.1112/s0025579300005222 .
Sándor Soifer. A matematikai kifestőkönyv. - Springer, 2009. - ISBN 978-0-387-74640-1 .
Erdős P., Simonovits M. A geometriai gráfok kromatikus számáról // Ars Comb.. - 1980. - Issue. 9 . – S. 229–246 .
Marcus Schäfer. Gráfok és kapcsolatok megvalósíthatósága // Thirty Essays on Geometric Graph Theory / Pach János. - Springer, 2013. - S. 461-482. - doi : 10.1007/978-1-4614-0110-0_24 .