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 (Coleman & Moré 1983).

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

(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) 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ályok

(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ócikkek

• Sűrű részgráf

Fordítá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 és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Paul E. Black, Sparse graph, from Dictionary of Algorithms and Data Structures, Paul E. Black (ed.), NIST. Retrieved on 29 September 2005.
• Coleman, Thomas F. & Moré, Jorge J. (1983), "Estimation of sparse Jacobian matrices and graph coloring Problems", SIAM Journal on Numerical Analysis 20 (1): 187–209, DOI 10.1137/0720013.
• Diestel, Reinhard (2005), Graph Theory, Graduate Texts in Mathematics, Springer-Verlag, ISBN 3-540-26183-4, OCLC 181535575.
• Lee, Audrey & Streinu, Ileana (2008), "Pebble game algorithms and sparse graphs", Discrete Mathematics 308 (8): 1425–1437, DOI 10.1016/j.disc.2007.07.104.
• Nash-Williams, C. St. J. A. (1964), "Decomposition of finite graphs into forests", Journal of the London Mathematical Society 39 (1): 12, DOI 10.1112/jlms/s1-39.1.12
• Preiss, first (1998), Data Structures and Algorithms with Object-Oriented Design Patterns in C++, John Wiley & Sons, ISBN 0-471-24134-2.
• Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2010), From Sparse Graphs to Nowhere Dense Structures: Decompositions, Independence, Dualities and Limits, European Mathematical Society, pp. 135–165
• Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, vol. 28, Algorithms and Combinatorics, Heidelberg: Springer, ISBN 978-3-642-27874-7, DOI 10.1007/978-3-642-27875-4.
• Streinu, I. & Theran, L. (2009), "Sparse hypergraphs and pebble game algorithms", European Journal of Combinatorics 30 (8): 1944–1964, DOI 10.1016/j.ejc.2008.12.018.
• Telle, Jan Arne & Villanger, Yngve (2012), "FPT algorithms for domination in biclique-free graphs", in Epstein, Leah & Ferragina, Paolo, Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings, vol. 7501, Lecture Notes in Computer Science, Springer, pp. 802–812, DOI 10.1007/978-3-642-33090-2_69.