Tiheä kaavio

Tiheä graafi  on graafi , jossa reunojen määrä on lähellä suurinta mahdollista täydelle graafille, jossa on useita pisteitä :

Graafia, jossa on pieni määrä reunoja, kutsutaan harvaksi graafiksi .

Yleisesti ottaen ero harvan ja tiheän graafin välillä on mielivaltainen ja riippuu kontekstista.

Suuntaamattomalle yksinkertaiselle graafille (reuna) [1] graafin tiheys, jossa on pistemäärä, määritellään sen reunojen lukumäärän suhteena kokonaisen graafin reunojen lukumäärään:

.

Reunojen maksimimäärä on yhtä suuri siten, että graafin maksimitiheys on 1 ( täydellisille graafille ) ja minimi on 0 - kytkemättömälle graafille [2] .

Upper Density

Ylempi tiheys  on graafitiheyden käsitteen laajennus äärellisistä graafisista äärettömiin. Intuitiivisesti äärettömässä graafissa on mielivaltaisen suuria äärellisiä aligraafia, joiden tiheys on pienempi kuin ylempi tiheys, eikä mielivaltaisen suuria äärellisiä aligraafia, joiden tiheys on suurempi kuin ylempi tiheys. Muodollisesti graafin G ylempi tiheys  on α:n arvojen infimumi siten, että G : n äärellisillä osagraafilla, joiden tiheys on suurempi kuin α, on rajallinen järjestys. Erdős-Stone-lauseen avulla voidaan osoittaa, että ylempi tiheys voi olla vain 1 tai yksi sekvenssin arvoista 0, 1/2, 2/3, 3/4, 4/5, … n /( n  + 1), ... (katso esimerkiksi Distel. Harjoitukset luvulle 7 [1] ).

Harva ja jäykkä kuvaaja

Shteinu [3] ja Teran [4] määrittelevät graafin ( k , l )-harvaksi, jos jollakin ei-tyhjällä aligraafilla, jossa on n kärkeä, on enintään kn  −  l reunaa, ja ( k , l )-tiukkaksi, jos se on ( k , l )-harva ja sillä on täsmälleen kn  −  l reunaa. Puut ovat siis täsmälleen (1,1)-tiukkoja graafisia, metsät täsmälleen (1,1)-harvoja graafeja ja graafit, joiden puisuus on k ,  ovat täsmälleen ( k , k )-harvoja graafeja. Pseudometsät  ovat täsmälleen (1,0)-harvoja kuvaajia, ja Laman-graafit , jotka esiintyvät jäykkyysteoriassa , ovat täsmälleen (2,3)-tiukkoja kuvaajia.

Myös muita graafiperheitä voidaan kuvata samalla tavalla. Esimerkiksi siitä tosiasiasta, että millä tahansa tasograafilla , jossa on n kärkeä, on enintään 3n  - 6 reunaa ja että mikä tahansa tasograafin aligraafi on tasomainen, seuraa, että tasograafit ovat (3,6)-harvoja graafeja. Jokainen (3,6)-harva graafi ei kuitenkaan ole tasomainen. Vastaavasti ulkotason graafit ovat (2,3)-harvoja ja tasomaiset kaksiosaiset graafit ovat (2,4)-harvoja.

Shteinu ja Teran osoittivat, että graafin ( k , l )-harva tarkistaminen voidaan tehdä polynomiajassa.

Harva ja tiheä graafien luokat

Ossona ja Nexetril [5] uskovat, että kun jaetaan harvaan/tiheään graafiin, on tarpeen ottaa huomioon äärettömiä graafiluokkia yksittäisten edustajien sijaan. He määrittelivät paikallisesti tiheät graafien luokat luokiksi, joille on olemassa kynnys t siten, että mikä tahansa täydellinen graafi näkyy t -alaosastona luokan graafin alagraafissa. Päinvastoin, jos tällaista kynnystä ei ole olemassa, luokan sanotaan olevan missään tiheä . Ossonin ja Nexetrilin julkaisussa [6] käsitellään lokalisoinnin tiheä/ei missään tiheä ominaisuuksia .

Muistiinpanot

  1. ↑ 1 2 Reinhard Distel. Graafiteoria. - Novosibirsk: Matematiikan instituutin kustantamo, 2002. - ISBN 5-86134-101-X .
  2. ↑ Thomas F. Coleman, Jorge J. More. Harvaiden Jacobian matriisien ja graafien väritysongelmien arviointi // SIAM Journal on Numerical Analysis. - 1983. - T. 20 , no. 1 . - S. 187-209 . - doi : 10.1137/0720013 .
  3. ↑ Audrey Lee, Ileana Strainu. Pebble pelialgoritmit ja harvat kaaviot // Diskreetti matematiikka. - 2008. - T. 308 , no. 8 . - S. 1425-1437 . - doi : 10.1016/j.disc.2007.07.104 .
  4. ↑ I. Streinu, L. Theran. Harvat hypergraafit ja kivipelialgoritmit // European Journal of Combinatorics . - 2009. - T. 30 , no. 8 . - S. 1944-1964 . - doi : 10.1016/j.ejc.2008.12.018 . — arXiv : math/0703921 .
  5. ↑ Patrice Ossona de Mendez, Jaroslav Nešetřil. Euroopan matematiikan kongressi. - European Mathematical Society, 2010. - S. 135-165 .
  6. ↑ Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparity: kaaviot, rakenteet ja algoritmit. - Heidelberg: Springer, 2012. - T. 28 . — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .

Kirjallisuus