У математиці граф називається щільним, якщо кількість його ребер близька до максимальної. На противагу, граф з малою кількістю ребер називається розрідженим. Різниця між щільним і розпливчатим графом розмита, і залежить від контексту.
Для неорієнтованих (простих) графів густина визначається як:
Для орієнтованих графів:
де E — кількість ребер, а V — кількість вершин графу. Максимальна кількість ребер для неорієнтованого графу , тому максимальна густина дорівнює 1 (для повних графів), а мінімальна густина дорівнює 0 (Coleman та Moré, 1983).
Верхня щільність
Верхня щільність — розширення поняття щільності для графів нескінченої розмірності. Інтуїтивно зрозуміло, що нескінчений граф містить скінченні підграфи довільної величини з будь-якою щільністю, що менша за верхню щільність нескінченого графу. Також інтуїтивно зрозуміло, що нескінчений граф не містить підграфів (скінченних) зі щільністю, вищою за його верхню щільність. Формально кажучи, верхня щільність графу G — це точна нижня межа таких значень α, що скінченні підграфи G зі щільністю α мають мають обмежений порядок. Використовуючи теорему Ердьоша-Стоуна, можна показати, що верхня щільність може бути або 1, або одним зі значень послідовності 0, 1/2, 2/3, 3/4, 4/5, … n/(n + 1), …
Розріджені і тугі графи
Згідно з Lee та Streinu, (2008) та Streinu та Theran, (2009), граф є -розрідженим, якщо кожен непорожній підграф з n ребрами має щонайбільше ребер, і -тугим, якщо він є -розрідженим і має точно ребер. Таким чином, дерева є точно -тугими графами, ліси — точно -розрідженими, а графи з деревністю є точно -розрідженими графами. Псевдоліси є точно -розрідженими, а Графи Ламана (це поняття зустрічається, наприклад, у теорії жорсткості) є точно -тугими графами.
Інші сім'ї графів, що не характеризуються такою якістю, як розрідженість, також може бути описано подібним чином. Наприклад, будь-який планарний граф з ребрами має щонайбільше ребер, і що будь-який підграф планарного графу також є планарним. З цього витікає, що планарні графи є -розрідженими. Але не кожен -розріджений граф є планарним. Аналогічно, зовніпланарні графи є -розрідженими, а планарні двочасткові графи — -розрідженими.
Штрейну і Теран показують, що перевірка -розрідженості може бути виконана за поліноміальний час, якщо і — цілі числа, і .
Примітки
Джерела
- Diestel, Reinhard (2005), Graph Theory, [en], Springer-Verlag, ISBN , OCLC 181535575 (англ.)
- Lee, Audrey; Streinu, Ileana (2008), Pebble game algorithms and sparse graphs, Discrete Mathematics, 308 (8): 1425—1437, doi:10.1016/j.disc.2007.07.104, MR 2392060 (англ.)
- Streinu, I.; Theran, L. (2009), Sparse hypergraphs and pebble game algorithms, [en], 30 (8): 1944—1964, arXiv:math/0703921, doi:10.1016/j.ejc.2008.12.018 (англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U matematici graf nazivayetsya shilnim yaksho kilkist jogo reber blizka do maksimalnoyi Na protivagu graf z maloyu kilkistyu reber nazivayetsya rozridzhenim Riznicya mizh shilnim i rozplivchatim grafom rozmita i zalezhit vid kontekstu Dlya neoriyentovanih prostih grafiv gustina viznachayetsya yak D 2 E V V 1 displaystyle D frac 2 E V V 1 Dlya oriyentovanih grafiv D E V V 1 displaystyle D frac E V V 1 de E kilkist reber a V kilkist vershin grafu Maksimalna kilkist reber dlya neoriyentovanogo grafu V V 1 2 displaystyle V V 1 2 tomu maksimalna gustina dorivnyuye 1 dlya povnih grafiv a minimalna gustina dorivnyuye 0 Coleman ta More 1983 Verhnya shilnistVerhnya shilnist rozshirennya ponyattya shilnosti dlya grafiv neskinchenoyi rozmirnosti Intuyitivno zrozumilo sho neskinchenij graf mistit skinchenni pidgrafi dovilnoyi velichini z bud yakoyu shilnistyu sho mensha za verhnyu shilnist neskinchenogo grafu Takozh intuyitivno zrozumilo sho neskinchenij graf ne mistit pidgrafiv skinchennih zi shilnistyu vishoyu za jogo verhnyu shilnist Formalno kazhuchi verhnya shilnist grafu G ce tochna nizhnya mezha takih znachen a sho skinchenni pidgrafi G zi shilnistyu a mayut mayut obmezhenij poryadok Vikoristovuyuchi teoremu Erdosha Stouna mozhna pokazati sho verhnya shilnist mozhe buti abo 1 abo odnim zi znachen poslidovnosti 0 1 2 2 3 3 4 4 5 n n 1 Rozridzheni i tugi grafiZgidno z Lee ta Streinu 2008 ta Streinu ta Theran 2009 graf ye k l displaystyle k l rozridzhenim yaksho kozhen neporozhnij pidgraf z n rebrami maye shonajbilshe k n l displaystyle kn l reber i k l displaystyle k l tugim yaksho vin ye k l displaystyle k l rozridzhenim i maye tochno k n l displaystyle kn l reber Takim chinom dereva ye tochno 1 1 displaystyle 1 1 tugimi grafami lisi tochno 1 1 displaystyle 1 1 rozridzhenimi a grafi z derevnistyu k displaystyle k ye tochno k k displaystyle k k rozridzhenimi grafami Psevdolisi ye tochno 1 0 displaystyle 1 0 rozridzhenimi a Grafi Lamana ce ponyattya zustrichayetsya napriklad u teoriyi zhorstkosti ye tochno 2 3 displaystyle 2 3 tugimi grafami Inshi sim yi grafiv sho ne harakterizuyutsya takoyu yakistyu yak rozridzhenist takozh mozhe buti opisano podibnim chinom Napriklad bud yakij planarnij graf z n displaystyle n rebrami maye shonajbilshe 3 n 6 displaystyle 3n 6 reber i sho bud yakij pidgraf planarnogo grafu takozh ye planarnim Z cogo vitikaye sho planarni grafi ye 3 6 displaystyle 3 6 rozridzhenimi Ale ne kozhen 3 6 displaystyle 3 6 rozridzhenij graf ye planarnim Analogichno zovniplanarni grafi ye 2 3 displaystyle 2 3 rozridzhenimi a planarni dvochastkovi grafi 2 4 displaystyle 2 4 rozridzhenimi Shtrejnu i Teran pokazuyut sho perevirka k l displaystyle k l rozridzhenosti mozhe buti vikonana za polinomialnij chas yaksho k displaystyle k i l displaystyle l cili chisla i 0 l lt 2 k displaystyle 0 leq l lt 2k PrimitkiDiestel 2005 DzherelaDiestel Reinhard 2005 Graph Theory en Springer Verlag ISBN 3 540 26183 4 OCLC 181535575 angl Lee Audrey Streinu Ileana 2008 Pebble game algorithms and sparse graphs Discrete Mathematics 308 8 1425 1437 doi 10 1016 j disc 2007 07 104 MR 2392060 angl Streinu I Theran L 2009 Sparse hypergraphs and pebble game algorithms en 30 8 1944 1964 arXiv math 0703921 doi 10 1016 j ejc 2008 12 018 angl