Tät graf

I matematik är en tät graf en graf där antalet kanter är nära det maximala antalet kanter (där varje par av hörn är sammankopplade med en kant). Motsatsen, en graf med bara ett fåtal kanter, är en gles graf . Skillnaden mellan vad som utgör en tät eller gles graf är dåligt definierad och beror på sammanhanget.

Grafdensiteten för $enkla E |$ grafer definieras som förhållandet mellan antalet kanter | med hänsyn till maximalt möjliga kanter.

För oriktade enkla grafer är grafdensiteten:

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

För riktade , enkla grafer är de maximalt möjliga kanterna dubbelt så stora som för oriktade grafer (eftersom det finns två riktningar till en kant) så tätheten är:

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

där $E$ är antalet kanter och $V$ är antalet hörn i grafen. Det maximala antalet kanter för en oriktad graf är ${\displaystyle {\binom {|V|}{2}}={\frac {|V|(|V|-1)}{2}}} , så$ den maximala densiteten är 1 (för fullständiga grafer ) och den minimala densiteten är 0 ( Coleman & Moré 1983) .

Övre densitet

Övre densitet är en förlängning av konceptet med grafdensitet som definierats ovan från finita grafer till oändliga grafer. Intuitivt har en oändlig graf godtyckligt stora finita subgrafer med vilken densitet som helst som är mindre än dess övre densitet, och har inte godtyckligt stora finita subgrafer med densitet som är större än dess övre densitet. Formellt är den övre densiteten för en graf $G$ det infimum av värdena α så att de finita subgraferna av $G$ med densiteten α har ett begränsat antal hörn. Det kan visas med hjälp av Erdős–Stone-satsen att den övre densiteten endast kan vara 1 eller ett av de superpartikulära förhållandena $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} 0, 1 / 2 , 2 / 3 , 3 / 4 , 4 / 5 , … n / n + 1$ (se t.ex. Diestel, upplaga 5, s. 189).

Glesa och snäva grafer

Lee & Streinu (2008) och Streinu & Theran (2009) definierar en graf som $(k, l)$ -gles om varje icke-tom subgraf med $n$ hörn har högst $kn - l$ kanter, och $(k, l)$ -tät om den är $(k, l)$ -gles och har exakt $kn - l$ kanter. Träd är alltså exakt de $(1,1)$ -snäva graferna, skogar är exakt de $(1,1)$ -glesa graferna, och grafer med arboricitet $k$ är exakt de $(k, k)$ -glesa graferna. Pseudoskogar är exakt de $(1,0)$ -glesa graferna, och Laman-graferna som uppstår i stelhetsteorin är exakt de $(2,3)$ -snäva graferna.

Andra graffamiljer som inte kännetecknas av sin gleshet kan också beskrivas på detta sätt. Till exempel faktumet att en plan graf med $n$ hörn har högst $3 n - 6$ kanter (förutom grafer med färre än 3 hörn), och att varje subgraf i en plan graf är plan, innebär tillsammans att de plana graferna är ( $3) ,6)$ -gles. Dock är inte varje $(3,6)$ -gles graf plan. På liknande sätt är ytterplanära grafer $(2,3)$ -glesa och plana tvådelade grafer är $(2,4)$ -glesa.

Streinu och Theran visar att testning av $(k, l)$ -sparsitet kan utföras i polynomtid när $k$ och $l$ är heltal och $0 \leq l < 2 k$ .

För en graffamilj är förekomsten av $k$ och $l$ så att graferna i familjen alla $(k, l)$ -glesa är ekvivalent med att graferna i familjen har gränsad degeneration eller har gränsad arboricitet . Mer exakt följer det av ett resultat av Nash-Williams (1964) att graferna för arboricitet som mest a $är$ exakt de $(a, a)$ -glesa graferna. På liknande sätt är graferna för degeneration som mest $d$ exakt de $(d +1 / 2, 1)$ -glesa graferna.

Glesa och täta klasser av grafer

Nešetřil & Ossona de Mendez (2010) ansåg att sparsitet/densitetsdikotomi gör det nödvändigt att överväga oändliga grafklasser istället för enskilda grafinstanser. De definierade någonstans täta grafklasser som de klasser av grafer för vilka det finns ett tröskelvärde t så att varje komplett graf visas som en t -underavdelning i en subgraf av en graf i klassen. Tvärtom, om en sådan tröskel inte finns, är klassen ingenstans tät . Egenskaper för den nowhere dense vs somewhere dense dikotomi diskuteras i Nešetřil & Ossona de Mendez (2012) .

Klasserna av grafer med avgränsad degeneration och av ingenstans täta grafer ingår båda i de biclique-fria graferna , graffamiljer som exkluderar någon komplett tvådelad graf som subgraf ( Telle & Villanger 2012 ).

Se även

Paul E. Black, Sparse graph , från Dictionary of Algorithms and Data Structures, Paul E. Black (red.), NIST . Hämtad 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, arXiv : math/0702129 , doi : 10.1016/j.disc.2007 . .0107 . 9MR .
Nash-Williams, C. St. JA (1964), "Decomposition of finite graphs into forests", Journal of the London Mathematical Society , 39 (1): 12, doi : 10.1112/jlms/s1-39.1.12 , MR 0161333
Preiss, först (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), "Från Sparse Graphs to Nowhere Dense Structures: Decompositions, Independence, Dualities and Limits", European Congress of Mathematics , European Mathematical Society, s. 135–165
Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, doi : 10.1007/978-3-642-27875-4 , hdl : 10338.dmlcz/143192 , ISBN 978-3-642-27874-7 , MR 5 292000 .
Streinu, I. ; Theran, L. (2009), "Sparse hypergraphs and pebble game algorithms", European Journal of Combinatorics , 30 (8): 1944–1964, arXiv : math/0703921 , doi : 10.1016/j.ejc.2008.12 .
Telle, Jan Arne; Villanger, Yngve (2012), "FPT algorithms for domination in biclique-free graphs", i Epstein, Leah; Ferragina, Paolo (red.), Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenien, 10–12 september 2012, Proceedings , Lecture Notes in Computer Science , vol. 7501, Springer, s. 802–812, doi : 10.1007/978-3-642-33090-2_69 .