Товщина графа

У теорії графів товщина графа Шаблон:Mvar — це найменша кількість плоских підграфів, на які можна розкласти ребра графа Шаблон:Mvar. Тобто, якщо існує набір Шаблон:Mvar плоских графів, які мають однаковий набір вершин, поєднання яких дає граф Шаблон:Mvar, то товщина графа Шаблон:Mvar не більше Шаблон:MvarШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.

Таким чином, плоский граф має товщину 1. Графи з товщиною 2 називають двопланарними графами. Концепція товщини виникла в гіпотезі Френка Харарі 1962 року: будь-який граф з 9 вершинами або сам, або його доповнення, є непланарним. Задача еквівалентна визначенню, чи є повний граф Шаблон:Math біпланарним (він не біпланарний, так що гіпотеза істинна)Шаблон:Sfn. Всебічний огляд з теми товщини графа (станом на 1998 рік) написали Мутцель, Оденталь і Шарбродт.

Конкретні графи

Товщина повного графа з Шаблон:Mvar вершинами, Шаблон:Mvar, дорівнює

$\lfloor \frac{n+7}{6}\rfloor ,$

за винятком випадків Шаблон:Math, для яких товщина дорівнює трьомШаблон:SfnШаблон:Sfn.

За винятком кількох випадків, товщина повного двочасткового графа Шаблон:Mvar дорівнюєШаблон:SfnШаблон:Sfn

$\lceil \frac{ab}{2(a+b-2)}\rceil .$

Пов'язані задачі

Будь-який ліс є планарним, а будь-який планарний граф можна розкласти на три ліси або менше. Отже, товщина будь-якого графа Шаблон:Mvar не більша від деревності того ж графа (найменшої кількості лісів, на які граф можна розкласти) і не менша від деревності, поділеної на 3Шаблон:Sfn. Товщина графа Шаблон:Mvar пов'язана з іншим стандартним інваріантом, виродженістю, що визначається як максимум за всіма підграфами графа Шаблон:Mvar найменшого степеня підграфа. Якщо граф з Шаблон:Mvar вершинами має товщину Шаблон:Mvar то число його ребер не перевищує Шаблон:Math, звідки випливає, що виродженість не перевищує Шаблон:Math. З іншого боку, якщо виродженість графа дорівнює Шаблон:Mvar, його деревність і товщина не перевищують Шаблон:Mvar.

Товщина тісно пов'язана із задачею одночасного вкладенняШаблон:Sfn. Якщо два або більше планарних графів мають той самий набір вершин, то є можливість вкласти всі ці графи в площину з поданням ребер у вигляді кривих, так що всі вершини будуть мати ту саму позицію у всіх малюнках. Однак може виявитися, що побудова таких малюнків неможлива, якщо використовувати відрізки прямих.

Інший інваріант графів — прямолінійна товщина або геометрична товщина графа Шаблон:Mvar, підраховує найменшу кількість планарних графів, на які можна розкласти Шаблон:Mvar з обмеженням, що їх можна намалювати одночасно за допомогою відрізків. Книжкова товщина (або товщина книги) додає обмеження, що всі вершини мають лежати на згині (корінці книги), формуючи колову схему графа. Однак, на відміну від деревності та виродженості, між цими величинами немає прямого зв'язкуШаблон:Sfn.

Обчислювальна складність

Обчислення товщини заданого графа є NP-складною, а перевірка, що товщина не перевищує двох, є NP-повною задачеюШаблон:Sfn. Однак, зв'язок із деревністю дозволяє апроксимувати товщину з апроксимаційним коефіцієнтом 3 за поліноміальний час.

Література

• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття