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

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

Характеристики all-path опуклих множин

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

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

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

Множина $S$ є all-path опуклою тоді і тільки тоді, коли $S$ є блоком або зв'язним об'єднанням блоків.

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

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

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

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

Властивості

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

Див. також

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