Grafic dens

Un grafic dens  este un grafic în care numărul de muchii este aproape de maximul posibil pentru un grafic complet cu numărul de vârfuri :

Un grafic care are un număr mic de muchii se numește grafic rar .

În general, diferența dintre un grafic rar și unul dens este arbitrară și depinde de context.

Pentru un grafic simplu nedirecționat (margine) [1] , densitatea unui grafic cu numărul de vârfuri este definită ca raportul dintre numărul muchiilor sale și numărul de muchii ale graficului complet:

.

Numărul maxim de muchii este egal , astfel încât densitatea maximă a graficului este 1 (pentru graficele complete ) iar minimul este 0 - pentru un grafic neconectat [2] .

Densitate superioară

Densitatea superioară  este o extensie a conceptului de densitate grafică de la grafice finite la infinite. Intuitiv, un graf infinit are subgrafe finite arbitrar mari cu orice densitate mai mică decât densitatea superioară și nu există subgrafe finite arbitrar mari cu o densitate mai mare decât densitatea superioară. Formal, densitatea superioară a unui grafic G  este o infimă a valorilor lui α, astfel încât subgrafele finite ale lui G cu o densitate mai mare decât α au ordin mărginit. Folosind teorema Erdős-Stone , se poate demonstra că densitatea superioară poate fi doar 1 sau una dintre valorile secvenței 0, 1/2, 2/3, 3/4, 4/5, … n /( n  + 1), ... (vezi, de exemplu, Distel. Exerciții pentru capitolul 7 [1] ).

Grafice rare și rigide

Shteinu [3] și Teran [4] definesc un grafic ca ( k , l )-spars dacă orice subgraf nevid cu n vârfuri are cel mult kn  -  l muchii și ca ( k , l )-strâns dacă este ( k , l )-rar și are exact kn  −  l muchii. Astfel, copacii sunt grafice exact (1,1)-strânse, pădurile sunt grafice exact (1,1)-sparse, iar graficele cu arboreitate k  sunt exact ( k , k )-grafice rare. Pseudopădurile  sunt grafice exact (1,0)-sparse, iar graficele Laman care apar în teoria rigidității sunt grafice exact (2,3)-strânse.

În mod similar pot fi descrise și alte familii de grafice. De exemplu, din faptul că orice graf plan cu n vârfuri are cel mult 3n  - 6 muchii și că orice subgraf al unui graf plan este plan, rezultă că grafurile plane sunt grafuri (3,6)-sparse. Cu toate acestea, nu fiecare grafic (3,6)-spars va fi plan. În mod similar, graficele planare sunt (2,3)-sparse, iar graficele bipartite plane sunt (2,4)-sparse.

Shteinu și Teran au arătat că verificarea dacă un grafic este ( k , l )-spars se poate face în timp polinomial.

Clase rare și dense de grafice

Ossona și Nexetril [5] consideră că atunci când se împart în grafice rare/dense, este necesar să se ia în considerare clase infinite de grafice, mai degrabă decât reprezentanții individuali. Ei au definit clase de grafice dense local ca clase pentru care există un prag t astfel încât orice grafic complet să apară ca o subsecțiune t într-un subgraf al clasei. În schimb, dacă un astfel de prag nu există, se spune că clasa nu este densă nicăieri . Proprietățile localizării dense/nicăieri dense sunt discutate în lucrarea lui Osson și Nexetril [6] .

Note

  1. ↑ 1 2 Reinhard Distel. Teoria grafurilor. - Novosibirsk: Editura Institutului de Matematică, 2002. - ISBN 5-86134-101-X .
  2. ↑ Thomas F. Coleman, Jorge J. More. Estimarea matricelor iacobiene rare și probleme de colorare a graficelor // SIAM Journal on Numerical Analysis. - 1983. - T. 20 , nr. 1 . - S. 187-209 . - doi : 10.1137/0720013 .
  3. ↑ Audrey Lee, Ileana Strainu. Algoritmi de joc Pebble și grafice rare // Matematică discretă. - 2008. - T. 308 , nr. 8 . - S. 1425-1437 . - doi : 10.1016/j.disc.2007.07.104 .
  4. ↑ I. Streinu, L. Theran. Hipergrafe rare și algoritmi de joc cu pietricele // 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. Congresul European de Matematică. - Societatea Europeană de Matematică, 2010. - S. 135-165 .
  6. ↑ Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparitate: grafice, structuri și algoritmi. - Heidelberg: Springer, 2012. - T. 28 . — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .

Literatură