Опуклий графовий простір

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

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

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

Історія

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

Означення

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

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

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

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

Зазначимо, що графовий опуклий простір часто сприймають як простір породжений інтервальним простором. Покладемо на множині $X$ функцію $I: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$.

Див. також

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