Щільний граф

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Розріджений граф)
Перейти до навігації Перейти до пошуку

У математиці граф називається щільним, якщо кількість його ребер близька до максимальної. На противагу, граф з малою кількістю ребер називається розрідженим. Різниця між щільним і розпливчатим графом розмита, і залежить від контексту.

Для неорієнтованих простих графів густина визначається як:

Для орієнтованих графів:

де E — кількість ребер, а V — кількість вершин графу. Максимальна кількість ребер для неорієнтованого графу , тому максимальна густина дорівнює 1 (для повних графів), а мінімальна густина дорівнює 0 (Coleman та Moré, 1983).

Верхня щільність[ред. | ред. код]

Верхня щільність — розширення поняття щільності для графів нескінченої розмірності. Інтуїтивно зрозуміло, що нескінчений граф містить скінченні підграфи довільної величини з будь-якою щільністю, що менша за верхню щільність нескінченого графу. Також інтуїтивно зрозуміло, що нескінчений граф не містить підграфів (скінченних) зі щільністю, вищою за його верхню щільність. Формально кажучи, верхня щільність графу G — це точна нижня межа таких значень α, що скінченні підграфи G зі щільністю α мають мають обмежений порядок. Використовуючи теорему Ердьоша-Стоуна, можна показати, що верхня щільність може бути або 1, або одним зі значень послідовності 0, 1/2, 2/3, 3/4, 4/5, … n/(n + 1), …[1]

Розріджені і тугі графи[ред. | ред. код]

Згідно з Lee та Streinu, (2008) та Streinu та Theran, (2009), граф є -розрідженим, якщо кожен непорожній підграф з n ребрами має щонайбільше ребер, і -тугим, якщо він є -розрідженим і має точно ребер. Таким чином, дерева є точно -тугими графами, ліси — точно -розрідженими, а графи з деревністю є точно -розрідженими графами. Псевдоліси є точно -розрідженими, а Графи Ламана (це поняття зустрічається, наприклад, у теорії жорсткості) є точно -тугими графами.

Інші сім'ї графів, що не характеризуються такою якістю, як розрідженість, також може бути описано подібним чином. Наприклад, будь-який планарний граф з ребрами має щонайбільше ребер, і що будь-який підграф планарного графу також є планарним. З цього витікає, що планарні графи є -розрідженими. Але не кожен -розріджений граф є планарним. Аналогічно, зовніпланарні графи є -розрідженими, а планарні двочасткові графи — -розрідженими.

Штрейну і Теран показують, що перевірка -розрідженості може бути виконана за поліноміальний час, якщо і  — цілі числа, і .

Примітки[ред. | ред. код]

Джерела[ред. | ред. код]

  • Diestel, Reinhard (2005). Graph Theory. Graduate Texts in Mathematics[en]. Springer-Verlag. ISBN 3-540-26183-4. 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. European Journal of Combinatorics[en]. 30 (8): 1944–1964. arXiv:math/0703921. doi:10.1016/j.ejc.2008.12.018.  (англ.)