All-path опуклість

Цю сторінку запропоновано перейменувати на Все-шлях опуклість. Можливо, її поточна назва не відповідає нормам української мови або правилам іменування статей у Вікіпедії. Пояснення причин і обговорення — на сторінці Вікіпедія:Перейменування статей.

Ця стаття не має інтервікі-посилань. Ви можете допомогти проєкту, знайшовши та додавши посилання на назву цієї сторінки у відповідному їй елементі Вікіданих, або, якщо Ви впевнені що такий ще не існує, то можете сміливо створювати власний елемент поточної сторінки та заповнити в ньому відповідні властивості Вікіданих. (2 квітня 2024)

Все-шлях опуклістю (з анг. All-path convexity) називають опуклий графовий простір, що породжений інтервальною функцією ${\displaystyle I\colon V\times V\rightarrow 2^{V}}$, що будь-якій парі різних вершин графа ставить у відповідність всі прості ланцюги між ними, тому будь-яка все-шлях опукла множина є геодетично та монофонічно опуклою. Вперше представлена у роботі^[1] та пізніше проаналізована у праці ^[2].

Характеристика з праці^[3] «All-path convexity: combinatorial and complexity aspects»:

${\displaystyle S}$ є AP-опуклою тоді i тільки тоді, коли ${\displaystyle S=V}$ , або для кожного зв’язної компоненти ${\displaystyle G_{i}}$, що ${\displaystyle V(G_{i})\subset V(G-S)}$, існує тільки одна сусідня вершина з ${\displaystyle S}$.

Також існує інша характеристики все-шлях опуклих множин, що пов'язує цю опуклість із графами блоків:

Множина ${\displaystyle S}$ є все-шлях опуклою тоді і тільки тоді, коли ${\displaystyle S}$ є блоком або зв'язним об'єднанням блоків.

Щоби сформулювати третій критерій AP-опуклих множин, введемо посилення одного класичного означення з метричної теорії графів. А саме, нехай ${\displaystyle A\subset V(G)}$ множина вершин у зв'язному графі ${\displaystyle G}$ та ${\displaystyle x\in V(G)}$. Воротами для ${\displaystyle x}$ у ${\displaystyle A}$ називається вершина ${\displaystyle g\in A}$ така, що для кожної вершини ${\displaystyle a\in A}$, деякий найкоротший шлях від ${\displaystyle x}$ до ${\displaystyle a}$ містить ${\displaystyle g}$ .

Якщо в попередньому означенні посилити умову до "будь-який найкоротший шлях від ${\displaystyle x}$ до a містить ${\displaystyle g}$ ", отримаємо означення сильних воріт для ${\displaystyle x}$ у ${\displaystyle A}$.

Тоді третя характеристика є наступною:

Множина ${\displaystyle S}$ є AP -опуклою тоді і тільки тоді, коли кожна вершина ${\displaystyle x\in V(G)}$ має сильні ворота в ${\displaystyle S}$ .

• Опуклою геометрією все-шлях опуклості є дерево.
• Часова складність алгоритму визначення того чи множина ${\displaystyle A}$ є все-шлях опуклою є лінійною відносно ${\displaystyle |V(G)|+||E(G)||}$.
• Часова складність знаходження опуклої оболонки множини ${\displaystyle A}$ є лінійною відносно ${\displaystyle |V(G)|+||E(G)||}$.
• Часова складність знаходження ${\displaystyle I(A)}$ є лінійною відносно ${\displaystyle |V(G)|+||E(G)||}$.

• Теорія графів
• Граф (математика)
• Векторний простір
• Топологічний простір
• Опукла геометрія
• Опукла множина
• Топологічний простір
• Опуклий графовий простір