Користувач:Whatislove Haponenko/Чернетка

Опуклий графовий простір^[1] у математиці називається пара об'єктів $(G,C)$ , де $G$ є графом, а $C$ є опуклістю або ж сім'єю підмножин графа $G$ що слідує пеним аксіомам. Елементи $C$ називають опуклими множинами.

Найвідомішими графовими опуклостями є геодетична опуклість^[2] та монофонічна опуклість^[3].

Опукла теорія графів може використовуватись для розв'язку задач комп'ютерного зору, задачі поширення інфекції^[4].

Історія ред.

Класичнi концепцiї теорiї опуклих структур отримали багато уваги в першiй половинi 20-го столiття. Проте, з розвитком теорiї, поняття опуклостi почали розглядати в бiльш широкому сенсi, не прив’язуючись до векторних просторiв. Аксіоматична формалізація поняття опуклого простору була представлена Ван де Велем у книзі "Theory of convex structure". Там же був означений і графоий опуклий простір. Пізніше це спровокувало зріст досліджень даної теми та знаходження великої кількості різних графових опуклостей. Найпопулярнішими та найбільш досліджуваними є геодетична опуклість^[5] та монофонічна опуклість^[6].

Означення ред.

Сім'я підмножин $C$ множини $X$ називається опуклістю на множині $X$ , якщо виконуються наступні аксіоми:

Порожня множина $\varnothing$ та сам $X$ входять в $C$ .
$C$ закрита відносно перетинів.
$C$ закрита відносно вкладених об'єднань.

Тоді пару $(X,C)$ називають опуклим простором, а елементи $C$ — опуклими множинами.

Графовим опуклим простором є пара $(G,C)$ , де $G$ є зв'язним графом з множиною вершин $V$ , яка в парі з $C$ є опуклим простором,що задовольняє попередні аксіоми.

Зазначимо, що графовий опуклий простір часто сприймають як простір породжений інтервальним простором. Покладемо на множині $X$ функцію $I\colon X\times X\to 2^{X}$ , що має наступні властивості:

Для будь-яких двох елементів $a,b\in X$ справджується $a,b\in I(a,b)$ .
Функція є симетричною $I(a,b)=I(b,a)$ .

Тоді $I$ називають інтервальним оператором на $X$ , a $I(a,b)$ є "інтервалом" між $a$ та $b$ . Пару $(X,I)$ називають інтервальним простором і він природнім чином породжує опуклість $C$ на $X$ . Так, підмножину $C$ ми називаємо опуклою тільки тоді, коли $I(x,y)\subseteq C$ для всіх $a,b\in C$ .

Див. також ред.

Примітки ред.

↑ van de Vel, M. L. J. Theory of convex structures. North-Holland Math. Library, 50 North-Holland Publishing Co., Amsterdam, 1993. xvi+540 pp. ISBN:0-444-81505-8
↑ Everett, Martin G., and Stephen B. Seidman. "The hull number of a graph." Discrete Mathematics 57.3 (1985): 217-223.
↑ Dourado, Mitre C., Fábio Protti, and Jayme L. Szwarcfiter. "Complexity results related to monophonic convexity." Discrete Applied Mathematics 158.12 (2010): 1268-1274.
↑ Van Mieghem, Piet, Jasmina Omic, and Robert Kooij. "Virus spread in networks." IEEE/ACM Transactions On Networking 17.1 (2008): 1-14.
↑ Farber, Martin, and Robert E. Jamison. "On local convexity in graphs." Discrete Mathematics 66.3 (1987): 231-247.
↑ Duchet, Pierre. "Convex sets in graphs, II. Minimal path convexity." Journal of Combinatorial Theory, Series B 44.3 (1988): 307-316.

[1] van de Vel, M. L. J. Theory of convex structures. North-Holland Math. Library, 50 North-Holland Publishing Co., Amsterdam, 1993. xvi+540 pp. ISBN:0-444-81505-8

[2] Everett, Martin G., and Stephen B. Seidman. "The hull number of a graph." Discrete Mathematics 57.3 (1985): 217-223.

[3] Dourado, Mitre C., Fábio Protti, and Jayme L. Szwarcfiter. "Complexity results related to monophonic convexity." Discrete Applied Mathematics 158.12 (2010): 1268-1274.

[4] Van Mieghem, Piet, Jasmina Omic, and Robert Kooij. "Virus spread in networks." IEEE/ACM Transactions On Networking 17.1 (2008): 1-14.

[5] Farber, Martin, and Robert E. Jamison. "On local convexity in graphs." Discrete Mathematics 66.3 (1987): 231-247.

[6] Duchet, Pierre. "Convex sets in graphs, II. Minimal path convexity." Journal of Combinatorial Theory, Series B 44.3 (1988): 307-316.

[1]

[2]

[3]

[4]

[5]

[6]