Hustý graf

Hustý graf  je graf , ve kterém se počet hran blíží maximu možného pro úplný graf s počtem vrcholů :

Graf, který má malý počet hran, se nazývá řídký graf .

Obecně řečeno, rozdíl mezi řídkým a hustým grafem je libovolný a závisí na kontextu.

Pro neorientovaný jednoduchý graf (hranu) [1] , je hustota grafu s počtem vrcholů definována jako poměr počtu jeho hran k počtu hran úplného grafu:

.

Maximální počet hran je stejný , takže maximální hustota grafu je 1 (u úplných grafů ) a minimum je 0 - pro nesouvislý graf [2] .

Horní hustota

Horní hustota  je rozšířením konceptu hustoty grafu z konečných na nekonečné grafy. Intuitivně má nekonečný graf libovolně velké konečné podgrafy s jakoukoli hustotou menší než horní hustota a žádné libovolně velké konečné podgrafy s hustotou větší než horní hustota. Formálně je horní hustota grafu G  infimem hodnot α tak, že konečné podgrafy G s hustotou větší než α mají ohraničené pořadí. Pomocí Erdősovy-Stoneovy věty lze ukázat, že horní hustota může být pouze 1 nebo jedna z hodnot posloupnosti 0, 1/2, 2/3, 3/4, 4/5, … n /( n  + 1), ... (viz např. Distel. Cvičení ke kapitole 7 [1] ).

Řídké a tuhé grafy

Shteinu [3] a Teran [4] definují graf jako ( k , l )-řídký, pokud má jakýkoli neprázdný podgraf s n vrcholy nejvýše kn  −  l hran, a jako ( k , l )-těsný, pokud je ( k , l )-řídký a má přesně kn  −  l hran. Stromy jsou tedy přesně (1,1)-těsné grafy, lesy jsou přesně (1,1)-řídké grafy a grafy se stromovitostí k  jsou přesně ( k , k )-řídké grafy. Pseudolesy  jsou přesně (1,0)-řídké grafy a Lamanovy grafy, které se objevují v teorii rigidity , jsou přesně (2,3)-těsné grafy.

Podobně lze popsat i další rodiny grafů. Například ze skutečnosti, že každý rovinný graf s n vrcholy má nejvýše 3n  - 6 hran a že každý podgraf rovinného grafu je rovinný, vyplývá, že rovinné grafy jsou (3,6)-řídké grafy. Ne každý (3,6)-řídký graf však bude rovinný. Podobně vnější rovinné grafy jsou (2,3)-řídké a planární bipartitní grafy jsou (2,4)-řídké.

Shteinu a Teran ukázali, že kontrolu, zda je graf ( k , l )-řídký, lze provést v polynomiálním čase.

Řídké a husté třídy grafů

Ossona a Nexetril [5] se domnívají, že při dělení na řídké/husté grafy je nutné uvažovat spíše o nekonečných třídách grafů než o jednotlivých zástupcích. Definovali lokálně husté třídy grafů jako třídy, pro které existuje práh t , takže jakýkoli úplný graf se objeví jako t -podsekce v podgrafu grafu třídy. Naopak, pokud takový práh neexistuje, říká se, že třída není nikde hustá . Vlastnosti lokalizace dense/nowhere dense jsou diskutovány v článku Ossona a Nexetrila [6] .

Poznámky

  1. ↑ 1 2 Reinhard Distel. Teorie grafů. - Novosibirsk: Nakladatelství Ústavu matematiky, 2002. - ISBN 5-86134-101-X .
  2. ↑ Thomas F. Coleman, Jorge J. More. Odhad řídkých jakobiánských matic a vybarvování grafů Problémy // SIAM Journal on Numerical Analysis. - 1983. - T. 20 , no. 1 . - S. 187-209 . - doi : 10.1137/0720013 .
  3. ↑ Audrey Lee, Ileana Strainu. Oblázkové herní algoritmy a řídké grafy // Diskrétní matematika. - 2008. - T. 308 , č.p. 8 . - S. 1425-1437 . - doi : 10.1016/j.disc.2007.07.104 .
  4. ↑ I. Streinu, L. Theran. Řídké hypergrafy a oblázkové herní algoritmy // 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. Evropský matematický kongres. - European Mathematical Society, 2010. - S. 135-165 .
  6. ↑ Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparita: Grafy, struktury a algoritmy. - Heidelberg: Springer, 2012. - T. 28 . — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .

Literatura