Tæt graf

En tæt graf  er en graf , hvor antallet af kanter er tæt på det maksimalt mulige for en komplet graf med antallet af hjørner :

En graf, der har et lille antal kanter, kaldes en sparsom graf .

Generelt set er forskellen mellem en sparsom og en tæt graf vilkårlig og afhænger af konteksten.

For en urettet simpel graf (kant) [1] er tætheden af ​​en graf med antallet af hjørner defineret som forholdet mellem antallet af dens kanter og antallet af kanter på hele grafen:

.

Det maksimale antal kanter er det samme , så den maksimale graftæthed er 1 (for komplette grafer ) og minimum er 0 - for en usammenhængende graf [2] .

Øvre tæthed

Øvre tæthed  er en udvidelse af begrebet graftæthed fra endelige til uendelige grafer. Intuitivt har en uendelig graf vilkårligt store endelige undergrafer med en hvilken som helst tæthed, der er mindre end den øvre tæthed, og ingen vilkårligt store endelige undergrafer med en densitet, der er større end den øvre tæthed. Formelt er den øvre tæthed af en graf G  et infimum af værdier af α, således at endelige undergrafer af G med en tæthed større end α har afgrænset rækkefølge. Ved hjælp af Erdős-Stone-sætningen , kan det vises, at den øvre tæthed kun kan være 1 eller en af ​​værdierne af sekvensen 0, 1/2, 2/3, 3/4, 4/5, … n /( n  + 1), ... (se f.eks. Distel. Øvelser til kapitel 7 [1] ).

Sparsomme og stive grafer

Shteinu [3] og Teran [4] definerer en graf som ( k , l )-sparsom, hvis en ikke-tom subgraf med n toppunkter højst har kn  −  l kanter, og som ( k , l )-tæt, hvis den er ( k , l )-sparsom og har nøjagtig kn  −  l kanter. Træer er således præcis (1,1)-tætte grafer, skove er nøjagtigt (1,1)-sparsomme grafer, og grafer med træhed k  er nøjagtigt ( k , k )-sparsomme grafer. Pseudoskove  er nøjagtigt (1,0)-sparsomme grafer, og Laman-grafer , der optræder i teorien om stivhed er nøjagtigt (2,3)-tætte grafer.

Andre familier af grafer kan også beskrives på lignende måde. For eksempel, af det faktum, at enhver plan graf med n toppunkter højst har 3n  - 6 kanter, og at enhver undergraf af en plan graf er plan, følger det, at plane grafer er (3,6)-sparsomme grafer. Imidlertid vil ikke hver (3,6)-spare graf være plan. Tilsvarende er ydre planære grafer (2,3)-sparsomme og plane todelte grafer er (2,4)-sparsomme.

Shteinu og Teran viste, at kontrol af, om en graf er ( k , l )-sparsom, kan udføres i polynomisk tid.

Sparsomme og tætte klasser af grafer

Ossona og Nexetril [5] mener, at når man opdeler i sparsomme/tætte grafer, er det nødvendigt at overveje uendelige klasser af grafer, frem for individuelle repræsentanter. De definerede lokalt tætte klasser af grafer som klasser, for hvilke der er en tærskel t , således at enhver komplet graf vises som et t -underafsnit i en grafundergraf i klassen. Omvendt, hvis en sådan tærskel ikke eksisterer, siges klassen ikke at være tæt . Egenskaberne ved lokalisering tæt/intetsteds tæt er diskuteret i papiret af Osson og Nexetril [6] .

Noter

  1. ↑ 1 2 Reinhard Distel. Grafteori. - Novosibirsk: Matematisk Instituts Forlag, 2002. - ISBN 5-86134-101-X .
  2. ↑ Thomas F. Coleman, Jorge J. More. Estimering af sparsomme jakobianske matricer og graffarveproblemer // SIAM Journal on Numerical Analysis. - 1983. - T. 20 , no. 1 . - S. 187-209 . - doi : 10.1137/0720013 .
  3. ↑ Audrey Lee, Ileana Strainu. Pebble spil algoritmer og sparsomme grafer // Diskret matematik. - 2008. - T. 308 , no. 8 . - S. 1425-1437 . - doi : 10.1016/j.disc.2007.07.104 .
  4. ↑ I. Streinu, L. Theran. Sparsomme hypergrafer og småstenspilsalgoritmer // European Journal of Combinatorics . - 2009. - T. 30 , no. 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 og algoritmer. - Heidelberg: Springer, 2012. - T. 28 . — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .

Litteratur