Loading AI tools
З Вікіпедії, вільної енциклопедії
У математиці граф називається щільним, якщо кількість його ребер близька до максимальної. На противагу, граф з малою кількістю ребер називається розрідженим. Різниця між щільним і розпливчатим графом розмита, і залежить від контексту.
Для неорієнтованих простих графів щільність визначається як:
Для орієнтованих графів:
де 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 ребрами має щонайбільше ребер, і -тугим, якщо він є -розрідженим і має точно ребер. Таким чином, дерева є точно -тугими графами, ліси — точно -розрідженими, а графи з деревністю є точно -розрідженими графами. Псевдоліси є точно -розрідженими, а Графи Ламана (це поняття зустрічається, наприклад, у теорії жорсткості) є точно -тугими графами.
Інші сім'ї графів, що не характеризуються такою якістю, як розрідженість, також може бути описано подібним чином. Наприклад, будь-який планарний граф з ребрами має щонайбільше ребер, і що будь-який підграф планарного графа також є планарним. З цього витікає, що планарні графи є -розрідженими. Але не кожен -розріджений граф є планарним. Аналогічно, зовніпланарні графи є -розрідженими, а планарні двочасткові графи — -розрідженими.
Штрейну і Теран показують, що перевірка -розрідженості може бути виконана за поліноміальний час, якщо і — цілі числа, і .
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.