Птолемеїв граф

Птолемеїв граф

Граф-смарагд (або 3-віяло) не Птолемеїв

Блоковий граф, різновид птолемеєвих графів

Три операції, за допомогою яких можна побудувати будь-який дистанційно-успадковуваний граф. Для птолемеєвих графів сусіди двійнят мають утворювати кліку, щоб запобігти побудові 4-циклу, показаного тут.

У теорії графів птолеме́їв граф — це неорієнтований граф, у якому відстані по найкоротшому шляху задовольняють нерівності Птолемея (грецького астронома і математика Птолемея). Птолемеєві графи — це точно графи, які одночасно є і хордальними, і дистанційно-успадковуваними. Ці графи включають блокові графи і є підкласом досконалих графів.

Опис

Граф є птолемеєвим тоді і тільки тоді, коли він задовольняє таким еквівалентним умовам:

• Відстані по найкоротшому шляху задовольняють нерівності Птолемея — для будь-яких чотирьох вершин u, v, w і x виконується нерівність d(u,v)d(w,x) + d(u,x)d(v,w) ≥ d(u,w)d(v,x) . Наприклад, граф-смарагд (3-віяло) на малюнку не є птолемеєвим, оскільки в цьому графі d(u,w)d(v,x) = 4 більше, ніж d(u,v)d(w,x) + d(u,x)d(v,w) = 3
• Для будь-яких перекривних максимальних клік їх перетин є сепаратором, який розділяє різницю цих двох клік. Для графу-смарагду на малюнку це не так: кліки uvy і wxy не розділяються їх перетином y оскільки існує ребро vw що з'єднує кліки.
• Будь-який цикл з k вершинами має щонайменше 3(k − 3)/2 діагоналей.
• Граф є і хордальним (будь-який цикл з довжиною, що перевищує три, має діагональ), і дистанційно-успадковуваним (будь-який зв'язний породжений підграф має ті ж відстані, що й весь граф). Граф-смарагд є хордальним, але не дистанційно-успадковуваним: у підграфі, породженому uvwx відстань від u до x дорівнює 3, що більше, ніж відстань між тими ж вершинами в повному графі. Оскільки як хордальні, так і дистанційно-успадковувані графи є досконалими, такими ж є і птолемеєві графи.
• Граф хордальний і не містить смарагдів — графів, утворених доданням двох неперетинних діагоналей у п'ятикутник.
• Граф є дистанційно-успадковуваним і не містить породжених 4-циклів.
• Граф можна побудувати з єдиної вершини послідовністю операцій, при яких додається нова вершина степеня 1 (висяча вершина) або дублюється наявна вершина (утворюючи близнюків або двійнят), з умовою, що операція подвоєння, в якій дублікат вершини не суміжний своїй парі (двійнята), тільки якщо сусіди цих подвоєних вершин утворюють кліку. Ці три операції, якщо не застосовувати зазначеної умови, утворюють всі дистанційно-успадковувані графи. Для утворення птолемеєвих графів недостатньо використовувати утворення висячих вершин і близнят, утворення двійнят (при дотриманні зазначених вище умов) теж іноді потрібне.
• Діаграма Гассе підмножини відношень непорожнього перетину максимальних клік утворює орієнтоване дерево.
• Опуклі підмножини вершин (підмножини, що містять усі найкоротші шляхи між двома вершинами в підмножині) утворюють опуклу геометрію. Тобто будь-яку опуклу множину можна отримати з повного набору вершин послідовним видаленням крайніх вершин, тобто тих, що не належать якомусь найкоротшому шляху між рештою вершин. У смарагді опуклу множину uxy не можна отримати таким способом, оскільки ні v, ні w не є крайніми.

Обчислювальна складність

Ґрунтуючись на описі орієнтованими деревами, птолемеєві графи можна розпізнати за лінійний час.

Література

• Hans-Jürgen Bandelt, Henry Martyn Mulder. . Distance-hereditary graphs // Journal of Combinatorial Theory. — 1986. — Т. 41, no. 2 (18 квітня). — С. 182–208. — (Series B). — DOI:10.1016/0095-8956(86)90043-2.
• Martin Farber, Robert E. Jamison. . Convexity in graphs and hypergraphs // SIAM Journal on Algebraic and Discrete Methods. — 1986. — Т. 7, no. 3 (18 квітня). — С. 433–444. — DOI:10.1137/0607049.
• Edward Howorka. . A characterization of Ptolemaic graphs // Journal of Graph Theory. — 1981. — Т. 5, no. 3 (18 квітня). — С. 323–331. — DOI:10.1002/jgt.3190050314.
• David C. Kay, Gary Chartrand. . A characterization of certain ptolemaic graphs // Canadian Journal of Mathematics. — 1965. — Т. 17 (18 квітня). — С. 342–346. — DOI:10.4153/CJM-1965-034-0.
• Terry A. McKee. . Clique graph representations of Ptolemaic graphs // Discussiones Mathematicae Graph Theory. — 2010. — Т. 30, no. 4 (18 квітня). — С. 651–661. — DOI:10.7151/dmgt.1520.
• Ryuhei Uehara, Yushi Uno. . Laminar structure of Ptolemaic graphs with applications // Discrete Applied Mathematics. — 2009. — Т. 157, no. 7 (18 квітня). — С. 1533–1543. — DOI:10.1016/j.dam.2008.09.006.