Tät graf

En tät graf  är en graf där antalet kanter är nära det maximala möjliga för en komplett graf med antalet hörn :

En graf som har ett litet antal kanter kallas en gles graf .

Generellt sett är skillnaden mellan en gles och en tät graf godtycklig och beror på sammanhanget.

För en oriktad enkel graf (kant) [1] definieras densiteten för en graf med antalet hörn som förhållandet mellan antalet kanter och antalet kanter på hela grafen:

.

Det maximala antalet kanter är lika så att den maximala grafdensiteten är 1 (för kompletta grafer ) och minimum är 0 - för en obunden graf [2] .

Övre densitet

Övre densitet  är en förlängning av konceptet grafdensitet från finita till oändliga grafer. Intuitivt har en oändlig graf godtyckligt stora finita subgrafer med vilken densitet som helst som är mindre än den övre densiteten, och inga godtyckligt stora finita subgrafer med en densitet som är större än den övre densiteten. Formellt är den övre densiteten för en graf G  ett infimum av värden på α så att ändliga subgrafer av G med en densitet större än α har en begränsad ordning. Med hjälp av Erdős-Stone-satsen , kan det visas att den övre densiteten endast kan vara 1 eller ett av värdena för sekvensen 0, 1/2, 2/3, 3/4, 4/5, … n /( n  + 1), ... (se till exempel Distel. Övningar för kapitel 7 [1] ).

Glesa och styva grafer

Shteinu [3] och Teran [4] definierar en graf som ( k , l )-gles om någon icke-tom subgraf med n hörn har högst kn  −  l kanter, och som ( k , l )-tät om den är ( k , l )-gles och har exakt kn  −  l kanter. Träd är alltså exakt (1,1)-snäva grafer, skogar är exakt (1,1)-glesa grafer, och grafer med trädighet k  är exakt ( k , k )-glesa grafer. Pseudoskogar  är exakt (1,0)-glesa grafer, och Laman-grafer som förekommer i styvhetsteorin är exakt (2,3)-snäva grafer.

Andra graffamiljer kan också beskrivas på liknande sätt. Till exempel, av det faktum att varje plan graf med n hörn har högst 3n  - 6 kanter, och att varje subgraf i en plan graf är plan, följer att plana grafer är (3,6)-glesa grafer. Emellertid kommer inte alla (3,6)-glesa grafer att vara plana. På liknande sätt är ytterplanära grafer (2,3)-glesa och plana tvådelade grafer är (2,4)-glesa.

Shteinu och Teran visade att kontroll av om en graf är ( k , l )-gles kan göras i polynomtid.

Glesa och täta klasser av grafer

Ossona och Nexetril [5] menar att när man delar upp i glesa/täta grafer är det nödvändigt att överväga oändliga klasser av grafer, snarare än enskilda representanter. De definierade lokalt täta klasser av grafer som klasser för vilka det finns ett tröskelvärde t så att varje komplett graf visas som ett t -underavsnitt i en grafundergraf för klassen. Omvänt, om ett sådant tröskelvärde inte finns, sägs klassen inte vara tät . Egenskaperna för lokalisering tät/nowhere dense diskuteras i artikeln av Osson och Nexetril [6] .

Anteckningar

  1. ↑ 1 2 Reinhard Distel. Grafteori. - Novosibirsk: Matematikinstitutets förlag, 2002. - ISBN 5-86134-101-X .
  2. ↑ Thomas F. Coleman, Jorge J. More. Uppskattning av glesa jakobianska matriser och graffärgningsproblem // SIAM Journal on Numerical Analysis. - 1983. - T. 20 , nr. 1 . - S. 187-209 . - doi : 10.1137/0720013 .
  3. ↑ Audrey Lee, Ileana Strainu. Pebble-spelalgoritmer och glesa grafer // Diskret matematik. - 2008. - T. 308 , nr. 8 . - S. 1425-1437 . - doi : 10.1016/j.disc.2007.07.104 .
  4. ↑ I. Streinu, L. Theran. Sparsamma hypergrafer och stenspelsalgoritmer // European Journal of Combinatorics . - 2009. - T. 30 , nr. 8 . - S. 1944-1964 . - doi : 10.1016/j.ejc.2008.12.018 . — arXiv : math/0703921 .
  5. ↑ Patrice Ossona de Mendez, Jaroslav Nešetřil. European Congress of Mathematics. - European Mathematical Society, 2010. - S. 135-165 .
  6. ↑ Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparity: Grafer, strukturer och algoritmer. - Heidelberg: Springer, 2012. - T. 28 . — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .

Litteratur