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

Шаблон:Move Шаблон:Без інтервікі

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

Характеристики все-шлях опуклих множин

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

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

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

Множина $S$ є все-шлях опуклою тоді і тільки тоді, коли $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$ .

Властивості

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

Див. також

Примітки

Шаблон:Reflist

Шаблон:Бібліоінформація

↑ 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

[1] Sampathkumar, E. «Convex sets in a graph.» Indian J. pure appl. Math 15.10 (1984): 1065—1071.

[2] F.~Protti and J. V. C.~Thompson, All-path convexity: combinatorial and complexity aspects, preprint,{arXiv:2303.18029}

[3] F.~Protti and J. V. C.~Thompson, All-path convexity: combinatorial and complexity aspects, preprint, arXiv:2303.18029

[1]

[2]

[3]

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

Зміст

Характеристики все-шлях опуклих множин

Властивості

Див. також

Примітки

Навігаційне меню

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

Характеристики все-шлях опуклих множин

Властивості

Див. також

Примітки

Навігаційне меню

Пошук