Щільний граф
Плотний граф— граф, у якому число ребер E близьке до максимально можливого у повного графа з числом V вершин:
E = V (V − 1) 2 . >.>
Граф, що має невелике число ребер, прийнято називатирозрідженим графом.
Взагалі, різниця між розрідженим і щільним графом умовна і залежить від контексту.
Для неорієнтованого простого графа (реберна) [1]щільність графаз числом вершин V визначається як відношення числа його ребер E до ребер повного графа:
D = 2 EV (V − 1) >> .
Максимальне число ребер дорівнює E = V ( V − 1 ) 2 , >,> так що максимальна густина графа дорівнює 1 (для повних графів) і мінімальна дорівнює 0 - для незв'язаного графа [2] .
Зміст
Верхня щільність- це розширення поняття щільності графа з кінцевих графів на нескінченні. Інтуїтивно зрозуміло, що нескінченний граф має довільно великі кінцеві підграфи з будь-якою щільністю, меншою верхньої щільності, і не має довільно великих кінцевих підграф з щільністю, більшої верхньої щільності. Формально верхня щільність графаG— це нижня грань таких значень α, що кінцеві підграфи графаGіз щільністю більше α мають обмежений порядок. Використовуючи теорему Ердеша-Стоуна [en] можна показати, що верхня щільність може бути лише 1 або одним із значень послідовності 0, 1/2, 2/3, 3/4, 4/5, …n/ (n+ 1), … (див., наприклад, Дистель. Вправи до розділу 7 [1] ).
Штрейну [3] і Теран [4] визначають граф як (k,l)-розріджений, якщо будь-який непустий підграф зnвершинами має максимумkn−lребер, і як (k,l)-тугий, якщо він (k,l)-розріджений і має точноkn−lребер. Такимчином дерева в точності (1,1)-тугі графи, ліси - в точності (1,1)-розріджені графи, а графи з деревністю [en]k- в точності (k,k)-розріджені графи. Псевдолеса [en] - це точно (1,0)-розріджені графи, а Ламанові графи, що з'являються в теорії жорсткості [en] , це в точності (2,3)-тугі графи.
Інші сімейства графів також можуть бути описані таким чином. Наприклад, з того, що будь-який планарний граф зnвершинами має максимум 3n— 6 ребра, і що будь-який підграф планарного графа є планарним, що планарні графи є (3,6 )-розрідженими графами. Однак не всякий (3,6)-розріджений граф буде планарним. Аналогічно, зовнішньопланарні графи є (2,3)-розрідженими та планарні дводольні графи є (2,4)-розрідженими.
Штрейну і Теран показали, що перевірка є граф (k,l)-розрідженим, може бути виконана за поліноміальний час.
Оссона і Нешетрил [5] вважають, що з розподілі на розріджені/щільні графи необхідно розглядати нескінченні класи графів, а чи не окремих представників. Вони визначилимісцями щільнікласи графів як класи, для яких існує такий порігt, що будь-який повний граф з'являється якt-підрозділ у підграфі графів класу. І навпаки, якщо такий поріг не існує, клас називається ніде не щільним. Властивості поділу на місцями щільні/ніде не щільні обговорюється у статті Оссона та Нешетріл [6] .