A matematika, azon belül a gráfelmélet területén egy sűrű gráf alatt olyan gráfot értünk, melyben az élek száma közel áll az élek maximális lehetséges számához. Ennek az ellentéte, a ritka gráf a viszonylag kevés éllel rendelkező gráf. A sűrű és ritka gráfok közötti különbségtétel önkényes, a szövegkörnyezettől függhet.

Irányítatlan egyszerű gráfokon egy gráf sűrűsége a következővel egyezik meg:

Irányított egyszerű gráfok sűrűsége pedig így határozható meg:

ahol E a gráf éleinek, V a csúcsainak a száma. Irányítatlan gráfban az élek maximális száma ½ |V| (|V|−1), tehát a maximális sűrűség 1 (a teljes gráfok esetében), a minimális pedig 0 (Coleman & Moré 1983).

Felső sűrűségSzerkesztés

A felső sűrűség a gráfsűrűség fogalmának kiterjesztése véges gráfokról végtelen gráfokra. Intuitív megközelítésben egy végtelen gráfnak lehetnek a felső sűrűségénél kisebb sűrűségű, tetszőlegesen nagy véges részgráfjai, de nem lehetnek a felső sűrűségnél nagyobb sűrűségű, tetszőlegesen nagy véges részgráfjai. Formálisan, egy G gráf felső sűrűsége azon α értékek infimuma, melyekre G α sűrűségű véges részgráfjai korlátos számú csúccsal rendelkezhetnek. Az Erdős–Stone-tétel segítségével megmutatható, hogy a felső sűrűség értéke vagy 1, vagy a szuperpartikuláris arányok valamelyike: 0, 1/2, 2/3, 3/4, 4/5, ... n/(n + 1), ... (lásd pl. Diestel, p. 189).

Ritka és éles gráfokSzerkesztés

(Lee & Streinu 2008) és (Streinu & Theran 2009) definíciója szerint egy (k,l)-ritka gráf (sparse graph) minden nem üres részgráfjának n csúcsa között legfeljebb kn − l él húzódik, a (k,l)-éles gráf (tight graph)[1] pedig (k,l)-ritka és pontosan kn − l éllel rendelkezik. Így a fák az (1,1)-éles gráfokkal egyeznek meg, az erdők az (1,1)-ritka gráfok, a k arboricitású gráfok pedig a (k,k)-ritka gráfok. A pszeudoerdők (az összefüggő komponensenként legfeljebb 1 körrel rendelkező irányítatlan gráfok) az (1,0)-ritka gráfokkal egyeznek meg, a merevségelmélet Laman-gráfjai pedig a (2,3)-éles gráfokkal.

Más, a ritkaságukkal nem jellemezhető gráfcsaládokról is tehetők hasonló kijelentések. Például az n csúcsú síkgráfok legfeljebb 3n − 6 éllel rendelkeznek, és bármely síkgráf részgráfjai is síkgráf – ebből a két kijelentésből következik, hogy a síkgráfok (3,6)-ritka gráfok. Nem igaz viszont, hogy bármely (3,6)-ritka gráf síkgráf lenne. Hasonlóan kijelenthető, hogy a külsíkgráfok (2,3)-ritkák és a páros síkgráfok (2,4)-ritkák.

Streinu és Theran igazolta, hogy a (k,l)-ritkaságra való tesztelés polinom időben elvégezhető, ha k és l olyan egész számok, melyekre 0 ≤ l < 2k.

Ha egy gráfcsalád esetén létezik olyan k és l, melyekre a családbéli gráfok (k,l)-ritkák, akkor a gráfok degeneráltsága vagy arboricitása korlátos. Precízebben kimondva, (Nash-Williams 1964) eredményéből következik, hogy a legfeljebb a arboricitású gráfok éppen az (a,a)-ritka gráfok; a legfeljebb d degeneráltságú gráfok pedig éppen a ((d + 1)/2,1)-ritka gráfok.

Ritka és sűrű gráfosztályokSzerkesztés

(Nešetřil & Ossona de Mendez 2010) arra jutott, hogy a ritkaság/sűrűség dichotómia miatt szükséges egyes gráfok helyett végtelen gráfosztályokat tekintetbe venni. Úgy definiálták a valahol sűrű (somewhere dense) gráfosztályt, mint azokat a gráfosztályokat, melyekben létezik t küszöbérték, melyre minden teljes gráf megjelenik az osztály egy gráfjának t-felosztásaként. Ha ilyen küszöbérték nem létezik, a gráfosztály sehol sem sűrű (nowhere dense). A sehol sem sűrű és valahol sűrű gráfosztályok dichotómiáját (Nešetřil & Ossona de Mendez 2012) elemzik.

A korlátos degeneráltságú gráfok és a sehol sem sűrű gráfok mind beletartoznak a biklikkmentes gráfok osztályába, melyek a teljes páros gráfot részgráfként nem tartalmazó gráfcsaládok(Telle & Villanger 2012).

Kapcsolódó szócikkekSzerkesztés

FordításSzerkesztés

  • Ez a szócikk részben vagy egészben a Dense graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. az „éles” szó itt a matematikai zsargonban használt éles, tovább már nem javítható eredményre utal