У теорії графів інтервальна розмірність графа — це інваріант графа, введений Фредом С. Робертсом у 1969 році.
Інтервальна розмірність графа — це мінімальна розмірність, в якій заданий граф можна подати у вигляді графа перетинів гіперпрямокутників (тобто багатовимірних прямокутних паралелепіпедів) з паралельними осям ребрами. Тобто має існувати відповідність один-до-одного між вершинами графа та множиною гіперпрямокутників, таких, що прямокутники перетинаються тоді й лише тоді, коли існує ребро, яке з'єднує відповідні вершини.
Приклади На рисунку показано граф із шістьма вершинами і подання цього графа у вигляді графа перетинів (звичайних двовимірних) прямокутників. Цей граф можна подати у вигляді графа перетинів прямокутників меншої розмірності (в даному випадку — відрізків), так що інтервальна розмірність графа дорівнює двом.
Робертс показав, що граф з 2n вершинами, утворений видаленням досконалого парування з повного графа з 2n вершинами, має інтервальну розмірність рівно n — будь-яку пару нез'єднаних вершин слід подати у вигляді гіперпрямокутників, які мають бути розділені у відмінному від іншої пари вимірі. Подання цього графа у вигляді гіперпрямокутників з розмірністю рівно n можна знайти потовщенням кожної з 2n граней n-вимірного гіперкуба до гіперпрямокутника. Тому такі графи почали називати графами РобертсаНаприклад, див. статті Чандрана, Френсіса і Сівадасана (), Чандрана і Сівадасана ., хоча вони відоміші як графи вечірки і їх можна трактувати також як графи Турана T(2n,n).
Зв'язок з іншими класами графів Граф має інтервальну розмірність не більше одиниці тоді і тільки тоді, коли він є інтервальним графом. Інтервальна розмірність довільного графа G — це найменше число інтервальних графів з тією ж множиною вершин (що і G), таких, що перетин множин ребер інтервальних графів дає G. Інтервальна розмірність будь-якого зовніпланарного графа не перевищує двох, а будь-якого планарного графа — трьох.
Якщо двочастковий граф має інтервальну розмірність два, його можна подати у вигляді графа перетинів паралельних осям відрізків на площині.
Алгоритмічні результати Багато задач на графах можна розв'язати або апроксимувати ефективніше на графах з обмеженою інтервальною розмірністю. Наприклад, задачу про найбільшу кліку для графів з обмеженою інтервальною розмірністю можна розв'язати за поліноміальний час Чандран, Френсіс і Сівадасан () зауважили, що це випливає з факту, що ці графи мають поліноміальне число максимальних клік. Явне подання у вигляді перетину гіперпрямокутників не вимагає перерахування всіх максимальних клік.. Для деяких інших задач на графах ефективний розв'язок або апроксимацію можна знайти, якщо існує подання у вигляді перетину гіпербагатогранників малої розмірностіДив., наприклад, статті і щодо апроксимації найбільшої незалежної множини для графів перетинів прямокутників, і з обговоренням складності апроксимації цих задач для більших розмірностей. .
Однак знаходження таких подань може виявитися складним — перевірка, чи не перевершує інтервальна розмірність заданого графа деякої наперед заданої величини K, є NP-повною задачею, навіть для K = 2Коззенс () показав, що обчислення інтервальної розмірності графа є NP-повною задачею. Яннакакіс () показав, що навіть перевірка, чи не перевищує інтервальна розмірність величини 3, є NP-складною. Нарешті, Краточвіл () показав, що розпізнавання інтервальної розмірності = 2 є NP-складною задачею.. Чандран, Френсіс і Сівадасан описали алгоритми знаходження подань довільних графів у вигляді графа перетинів гіперпрямокутників з розмірністю в межах логарифмічного множника найбільшого степеня графа. Цей результат дає верхню межу інтервальної розмірності графа.
Попри труднощі для природних параметрів, інтервальна розмірність графа є , якщо параметризацію проводити за числом вершинного покриття вхідного графа.
Примітки
Література