Все-шлях опуклістю (з анг. All-path convexity) називають опуклий графовий простір, що породжений інтервальною функцією , що будь-якій парі різних вершин графа ставить у відповідність всі прості ланцюги між ними, тому будь-яка все-шлях опукла множина є геодетично та монофонічно опуклою. Вперше представлена у роботіSampathkumar, E. «Convex sets in a graph.» Indian J. pure appl. Math 15.10 (1984): 1065—1071. та пізніше проаналізована у праці F.~Protti and J. V. C.~Thompson, All-path convexity: combinatorial and complexity aspects, preprint,{arXiv:2303.18029}.
Характеристики все-шлях опуклих множин Характеристика з праціF.~Protti and J. V. C.~Thompson, All-path convexity: combinatorial and complexity aspects, preprint, arXiv:2303.18029 «All-path convexity: combinatorial and complexity aspects»:
є AP-опуклою тоді i тільки тоді, коли , або для кожного зв’язної компоненти , що , існує тільки одна сусідня вершина з .
Також існує інша характеристики все-шлях опуклих множин, що пов'язує цю опуклість із графами блоків:
Множина є все-шлях опуклою тоді і тільки тоді, коли є блоком або зв'язним об'єднанням блоків.
Щоби сформулювати третій критерій AP-опуклих множин, введемо посилення одного класичного означення з метричної теорії графів. А саме, нехай множина вершин у зв'язному графі та . Воротами для у називається вершина така, що для кожної вершини , деякий найкоротший шлях від до містить .
Якщо в попередньому означенні посилити умову до "будь-який найкоротший шлях від до a містить ", отримаємо означення сильних воріт для у .
Тоді третя характеристика є наступною:
Множина є AP -опуклою тоді і тільки тоді, коли кожна вершина має сильні ворота в .
Властивості Опуклою геометрією все-шлях опуклості є дерево. Часова складність алгоритму визначення того чи множина є все-шлях опуклою є лінійною відносно . Часова складність знаходження опуклої оболонки множини є лінійною відносно . Часова складність знаходження є лінійною відносно .
Див. також Теорія графів Граф (математика) Векторний простір Топологічний простір Опукла геометрія Опукла множина Топологічний простір Опуклий графовий простір
Примітки