Число нахилів графа

Матеріал з testwiki
Перейти до навігації Перейти до пошуку
Малюнок графа Петерсена з числом нахилів 3

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

Повні графи

Хоча близькі задачі комбінаторної геометрії вивчали й раніше (Скотт у 1970 і Джемісон у 1984), задачу визначення числа нахилів графа поставили Вейд і ЧуШаблон:Sfn, показавши, що число нахилів графа з n вершинами повного графа Kn дорівнює рівно n. Малюнок графа з таким числом нахилів можна отримати, розташувавши вершини графа в кутах правильного многокутника.

Зв'язок зі степенем графа

Зрозуміло, що число нахилів графа з найбільшим степенем d не менше ⌈d/2⌉, оскільки максимум два інцидентні ребра вершини степеня d можуть лежати на одній прямій (мати один нахил). Точніше, число нахилів не менше лінійної деревності графа, оскільки ребра одного нахилу мають утворювати лінійний ліс, а лінійна деревність, у свою чергу, не менша ніж ⌈d/2⌉.

Існують графи з найбільшим степенем 5, що мають довільно велике число нахилів[1]. Однак будь-який граф із найбільшим степенем 3 має не більше чотирьох нахилів[2]. Результат Вейда і Чу (Шаблон:Harvtxt) для повного графа K4 показує, що ця межа точна. Не будь-який набір із чотирьох нахилів підходить для малювання всіх графів степеня 3 — набір нахилів підходить для малювання тоді й лише тоді, коли вони є нахилами сторін та діагоналей паралелограма. Зокрема, будь-який граф степеня 3 можна намалювати так, що його ребра або паралельні осям, або паралельні основним діагоналям цілочисельної ґраткиШаблон:Sfn. Невідомо, чи обмежене число нахилів графів з найбільшим степенем 4Шаблон:Sfn.

Метод Кезега, Паха та ПалвелдіШаблон:Sfn комбінування пакування кіл і дерева квадрантів для отримання обмеженого числа нахилів для планарних графів з обмеженим степенем

Планарні графи

Як показали Кезег, Пах і Палвелді (Шаблон:Harvtxt), будь-який планарний граф має плоский малюнок у вигляді прямих відрізків, у якому число різних нахилів є функцією від степеня графа. Їхнє доведення ґрунтується на побудові Малиця і Папакостаса (Шаблон:Harvtxt) для обмеження кутової роздільності планарних графів як функції степеня. Степінь обмежують доповненням графа до максимального планарного графа без збільшення його степеня більш ніж на сталий множник, а потім застосовують теорема про упаковку кіл для подання цього розширеного графа як набору кіл, що дотикаються між собою. Якщо степінь початкового графа обмежено, відношення радіусів суміжних кіл у пакуванні буде також обмеженимШаблон:Sfn, звідки, у свою чергу, випливає, що застосування дерева квадрантів для всіх вершин графа в точці всередині кола дає нахили, які є відношеннями малих цілих чисел. Число різних нахилів, що отримується при цій побудові, є експонентою від степеня графа.

Складність

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

Перевірка, чи можна зобратити планарний граф планарним малюнком із числом нахилів 2, також є NP-повною задачеюШаблон:Sfn.

Примітки

Шаблон:Reflist

Література

Шаблон:Refbegin

Шаблон:Refend

  1. ↑ Довели незалежно Барат, Матоушек, Вуд (Шаблон:Harvtxt) і Пах, Палвелді (Шаблон:Harvtxt), коли розв'язували задачу, яку поставив Дуймович, Судерман і Шарір (Шаблон:Harvtxt). Див. теореми 5.1 і 5.2 у Паха і Шаріра (Шаблон:Harvtxt).
  2. ↑ Муккамала, Сегеді (Шаблон:Harvtxt), які покращили раніший результат Кезега, Палвелді, Тота (Шаблон:Harvtxt). Див. теорему 5.3 у Паха і Шаріра (Шаблон:Harvtxt).
Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Число_нахилів_графа&oldid=9768