A lap 2017. január 28., 10:52-kori változata szerkesztés Syp (vitalap \| szerkesztései) járőrök 89 988 szerkesztés Új oldal, tartalma: „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 maxi…”		A lap 2017. február 2., 01:38-kori változata szerkesztés visszavonás Tudor987 (vitalap \| szerkesztései) járőrök, megerősített szerkesztők 69 449 szerkesztés Nincs szerkesztési összefoglaló Újabb szerkesztés →
11. sor: ==Ritka és éles gráfok== {{harvtxt\|Lee\|Streinu\|2008}} és {{harvtxt\|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)''<ref>az „éles” szó itt a matematikai zsargonban használt éles, tovább már nem javítható eredményre utal</ref> pedig (''k'',''l'')-ritka és pontosan ''kn'' − ''l'' éllel rendelkezik. Így a [[fa (gráfelmélet)\|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ő komponens]]enké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áf]]jai 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áf]]ok legfeljebb 3''n'' − 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áf]]ok (2,3)-ritkák és a [[páros gráf\|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'' < 2''k''. 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ág (gráfelmélet)\|degeneráltsága]] vagy [[arboricitás]]a korlátos. Precízebben kimondva, {{harvtxt\|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. 34. sor: {{jegyzetek}} * Paul E. Black, [https://xlinux.nist.gov/dads/HTML/sparsegraph.html Sparse graph], from ''Dictionary of Algorithms and Data Structures,'' Paul E. Black (ed.), [[National Institute of Standards and Technology\|NIST]]. Retrieved on 29 September 2005. * {{citation \| first1 = Thomas F. \| last1 = Coleman \| first2 = Jorge J. \| last2 = Moré \| year = 1983 \| title = Estimation of sparse Jacobian matrices and graph coloring Problems \| journal = SIAM Journal on Numerical Analysis \| volume = 20 \| pages = 187–209 \| doi = 10.1137/0720013 \| issue = 1 }}. <!-- feel free to replace with a better reference for "graph density" --> {{citation\|first=Reinhard\|last=Diestel\|title=Graph Theory\|publisher=Springer-Verlag\|series=[[Graduate Texts in Mathematics]]\|year=2005\|isbn=3-540-26183-4\|oclc=181535575}}. {{citation 49. sor: {{citation\|first=C. St. J. A.\|last=Nash-Williams\|authorlink=Crispin Nash-Williams\|title=Decomposition of finite graphs into forests\|journal=[[Journal of the London Mathematical Society]]\|volume=39\|issue=1\|year=1964\|pages=12\|doi=10.1112/jlms/s1-39.1.12\|mr=0161333}} {{Citation \| last=Preiss\|given=first\| title=Data Structures and Algorithms with Object-Oriented Design Patterns in C++ \| publisher=John Wiley & Sons \|year=1998 \| isbn=0-471-24134-2}}. * {{citation \| first2 = Patrice \| last2 = Ossona de Mendez\|\| authorlink2=Patrice Ossona de Mendez \| first1 = Jaroslav \| last1 = Nešetřil \| authorlink1=Jaroslav Nešetřil\| year = 2010 \| title = From Sparse Graphs to Nowhere Dense Structures: Decompositions, Independence, Dualities and Limits\| booktitle = European Congress of Mathematics\| publisher = European Mathematical Society \| pages=135–165}} {{citation \| last1 = Nešetřil \| first1 = Jaroslav \| author1-link = Jaroslav Nešetřil 62. sor: \| volume = 28 \| year = 2012}}. {{citation\|first1=I.\|last1=Streinu\|author1-link=Ileana Streinu\|first2=L.\|last2=Theran\|year=2009\|title=Sparse hypergraphs and pebble game algorithms\|journal=[[European Journal of Combinatorics]]\|volume=30\|issue=8\|pages=1944–1964\|doi=10.1016/j.ejc.2008.12.018\|arxiv=math/0703921 }}. *{{citation \| last1 = Telle \| first1 = Jan Arne

„Sűrű gráf” változatai közötti eltérés