|
Обмежене розширення графаКажуть, що сімейство графів має обме́жене розши́рення, якщо всі його мінори обмеженої глибини є розрідженими графами. Багато природних сімейств розріджених графів мають обмежене розширення. Близька, але сильніша властивість, поліноміа́льне розши́рення, еквівалентне існуванню теорем розбиття для цих сімейств. Сімейства з цими властивостями мають ефективні алгоритми для задач, у числі яких пошук ізоморфного підграфа і перевірка моделей для теорії першого порядку для графів. Визначення та еквівалентні описиМінор глибини t графа G визначається як граф, утворений із G стягуванням набору підграфів радіуса t, які не мають спільних вершин, і видаленням решти вершин. Сімейство графів має обмежене розширення, якщо існує функція f, така, що для будь-якого мінора глибини t графа зі сімейства відношення числа ребер до числа вершин не перевищує f(t)[1]. Інше визначення класів обмеженого розширення — всі мінори обмеженої глибини мають хроматичне число, обмежене деякою функцією від t[1], або задане сімейство має обмежене значення топологічного параметра. Таким параметром є інваріант графа, монотонний відносно операції взяття підграфа, такий, що значення параметра може змінюватися тільки контрольованим способом, коли граф ділиться, і з обмеженості значення параметра випливає, що граф має обмежену виродженість[2]. Поліноміальне розширення та теореми про розбиттяСтрогіше поняття — поліноміальне розширення, що означає, що функція f, що використовується для обмеження щільності ребер мінорів обмеженої глибини, поліноміальна . Якщо сімейство графів, що успадковується, задовольняє теоремі про розбиття, яка стверджує, що будь-який граф з n вершинами в сімействі може бути розбитий на дві частини, що містять не більше n /2 вершин, шляхом видалення O (n c) вершин для деякої константи c < 1, це сімейство обов'язково має поліноміальне розширення. Назад — графи з поліноміальним розширенням мають теореми із сублінійним сепаратором [3] . Класи графів з обмеженим розширеннямОскільки існує зв'язок між сепараторами та розширенням, будь-яке замкнуте за мінорами сімейство графів, включно зі сімейством планарних графів, має поліноміальне розширення. Те саме стосується 1-планарних графів, і, загальніше, графів, які можна вкласти в поверхні обмеженого роду з обмеженою кількістю перетинів на ребро, так само, як і струнні графи без біклік, оскільки для них є теореми про сепаратори, схожі на теореми для планарних графів[4][5][6]. У евклідових просторах вищих розмірностей графи перетинів систем куль із властивістю, що будь-яка точка простору покрита обмеженим числом куль, також задовольняють теоремам про розбиття[7], звідки випливає існування поліноміального розширення. Хоча графи обмеженої книжкової ширини не містять лінійних сепараторів[8], вони також мають обмежене розширення[9]. До класу графів з обмеженим розширенням входять графи обмеженого степеня[10], випадкові графи обмеженого середнього степеня в моделі Ердеша — Реньї[11] та графи з обмеженим числом черг[2][12]. Алгоритмічні застосуванняПримірник задачі ізоморфізму підграфа, в якій метою є пошук графа обмеженого розміру, що є підграфом більшого графа, розмір якого не обмежений, можна розв'язати за лінійний час, якщо більший граф належить до сімейства графів з обмеженим розширенням. Те ж саме стосується пошуку клік фіксованого розміру, пошуку домінівних множин фіксованого розміру, або, загальнішого випадку, перевірки властивостей, які можна виразити формулою обмеженого розміру в логіці графів[en] першого порядку[13][14]. Для графів із поліноміальним розширенням існують схеми наближення до поліноміального часу для задачі про покриття множини, задачі про максимальну незалежну множину, задачі про домінівну множину та деяких інших пов'язаних задач оптимізації[15]. Примітки
Література
|