Sűrű gráf

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:

$D=\frac{2|E|}{|V|(|V|-1)}.$

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

$D=\frac{|E|}{|V|(|V|-1)}.$

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 Sablon:Harv.

Felső sűrűség

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áfok

Sablon:Harvtxt és Sablon:Harvtxt 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) 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, Sablon:Harvtxt 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ályok

Sablon:Harvtxt 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 Sablon:Harvtxt 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ádokSablon:Harv.

Kapcsolódó szócikkek

• Sűrű részgráf

Fordítás

• Sablon:Fordítás

Jegyzetek

• Paul E. Black, Sparse graph, from Dictionary of Algorithms and Data Structures, Paul E. Black (ed.), NIST. Retrieved on 29 September 2005.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation
• Sablon:Citation.
• Sablon:Citation
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.