Sűrű grafikon

A sűrű gráf  olyan gráf , amelyben az élek száma megközelíti a csúcsok számával rendelkező teljes gráf lehetséges maximumát :

A kevés éllel rendelkező gráfot ritka gráfnak nevezzük .

Általánosságban elmondható, hogy a ritka és a sűrű gráf közötti különbség tetszőleges, és a kontextustól függ.

Egy irányítatlan egyszerű gráf (él) [1] esetén a csúcsok számát tartalmazó gráf sűrűségét az élei számának a teljes gráf éleinek számához viszonyított arányaként határozzuk meg :

.

Az élek maximális száma egyenlő úgy, hogy a maximális gráfsűrűség 1 ( teljes gráfok esetén ), a minimális pedig 0 - egy nem kapcsolódó gráf esetén [2] .

Felső sűrűség

A felső sűrűség  a gráfsűrűség fogalmának kiterjesztése véges gráfokról végtelen gráfokra. Intuitív módon egy végtelen gráfnak tetszőlegesen nagy véges részgráfjai vannak, amelyek sűrűsége kisebb, mint a felső sűrűség, és nincsenek tetszőlegesen nagy véges részgráfjai, amelyek sűrűsége nagyobb, mint a felső sűrűség. Formálisan a G  gráf felső sűrűsége az α értékeinek infimuma , így G véges részgráfjai, amelyek sűrűsége nagyobb, mint α, korlátos sorrendű. Az Erdős-Stone tétel segítségével kimutatható, hogy a felső sűrűség csak 1, vagy a sorozat értékeinek egyike lehet 0, 1/2, 2/3, 3/4, 4/5, … n /( n  + 1), ... (lásd például a Distel. Gyakorlatok a 7. fejezethez [1] ).

Ritka és merev grafikonok

Shteinu [3] és Teran [4] egy gráfot ( k , l )-ritkanak definiál, ha bármely n csúcsú nem üres részgráfnak legfeljebb kn  −  l éle van, és ( k , l )-szorosnak, ha az ( k , l )-ritka és pontosan kn  −  l élekkel rendelkezik. Így a fák pontosan (1,1)-szoros gráfok, az erdők pontosan (1,1)-ritka gráfok, a k fásságú gráfok  pedig pontosan ( k , k )-ritka gráfok. Az álerdők  pontosan (1,0)-ritka gráfok, a merevségelméletben megjelenő Lámán-gráfok pedig pontosan (2,3)-szoros gráfok.

Más gráfcsaládok is leírhatók hasonló módon. Például abból, hogy minden n csúcsú síkgráfnak legfeljebb 3n  - 6 éle van, és egy síkgráf bármely részgráfja síkbeli, ebből következik, hogy a síkgráfok (3,6)-ritka gráfok. Azonban nem minden (3,6) ritka gráf lesz síkbeli. Hasonlóképpen, a külső síkbeli gráfok (2,3)-ritkaak, a síkbeli kétrészes gráfok pedig (2,4)-ritkások.

Shteinu és Teran megmutatta, hogy egy gráf ( k , l )-ritka-e polinomiális időben is ellenőrizhető.

A gráfok ritka és sűrű osztályai

Ossona és Nexetril [5] úgy véli, hogy a ritka/sűrű gráfokra való felosztáskor a gráfok végtelen osztályait kell figyelembe venni, nem pedig az egyes reprezentánsokat. A gráfok lokálisan sűrű osztályait olyan osztályokként határozták meg, amelyekre van egy t küszöbérték , így bármely teljes gráf t -alszakaszként jelenik meg az osztály gráf részgráfjában. Ezzel szemben, ha nem létezik ilyen küszöb, akkor az osztályról azt mondják , hogy sehol sem sűrű . A sűrű/sehol sem sűrű lokalizáció tulajdonságait Osson és Nexetril [6] tárgyalja .

Jegyzetek

  1. ↑ 1 2 Reinhard Distel. Gráfelmélet. - Novoszibirszk: A Matematikai Intézet kiadója, 2002. - ISBN 5-86134-101-X .
  2. ↑ Thomas F. Coleman, Jorge J. More. Ritka Jacobi-mátrixok és gráfszínezési problémák becslése // SIAM Journal on Numerical Analysis. - 1983. - T. 20 , sz. 1 . - S. 187-209 . - doi : 10.1137/0720013 .
  3. ↑ Audrey Lee, Ileana Strainu. Kavicsjáték-algoritmusok és ritka gráfok // Diszkrét matematika. - 2008. - T. 308 , sz. 8 . - S. 1425-1437 . - doi : 10.1016/j.disc.2007.07.104 .
  4. ↑ I. Streinu, L. Theran. Ritka hipergráfok és kavicsos játékalgoritmusok // European Journal of Combinatorics . - 2009. - T. 30 , sz. 8 . - S. 1944-1964 . - doi : 10.1016/j.ejc.2008.12.018 . — arXiv : math/0703921 .
  5. ↑ Patrice Ossona de Mendez, Jaroslav Nešetřil. Európai Matematikai Kongresszus. - Európai Matematikai Társaság, 2010. - S. 135-165 .
  6. ↑ Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparitás: grafikonok, struktúrák és algoritmusok. - Heidelberg: Springer, 2012. - T. 28 . — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .

Irodalom