У теорії графів птолеме́їв граф — це неорієнтований граф, у якому відстані по найкоротшому шляху задовольняють нерівності Птолемея (грецького астронома і математика Птолемея). Птолемеєві графи — це точно графи, які одночасно є і хордальними, і дистанційно-успадковуваними. Ці графи включають блокові графи і є підкласом досконалих графів.
Опис Граф є птолемеєвим тоді і тільки тоді, коли він задовольняє таким еквівалентним умовам:
Відстані по найкоротшому шляху задовольняють нерівності Птолемея — для будь-яких чотирьох вершин , , і виконується нерівність . Наприклад, граф-смарагд (3-віяло) на малюнку не є птолемеєвим, оскільки в цьому графі більше, ніж Для будь-яких перекривних максимальних клік їх перетин є сепаратором, який розділяє різницю цих двох клік. Для графу-смарагду на малюнку це не так: кліки і не розділяються їх перетином оскільки існує ребро що з'єднує кліки. Будь-який цикл з вершинами має щонайменше діагоналей. Граф є і хордальним (будь-який цикл з довжиною, що перевищує три, має діагональ), і дистанційно-успадковуваним (будь-який зв'язний породжений підграф має ті ж відстані, що й весь граф). Граф-смарагд є хордальним, але не дистанційно-успадковуваним: у підграфі, породженому відстань від до дорівнює 3, що більше, ніж відстань між тими ж вершинами в повному графі. Оскільки як хордальні, так і дистанційно-успадковувані графи є досконалими, такими ж є і птолемеєві графи. Граф хордальний і не містить смарагдів — графів, утворених доданням двох неперетинних діагоналей у п'ятикутник.. Граф є дистанційно-успадковуваним і не містить породжених 4-циклів. Граф можна побудувати з єдиної вершини послідовністю операцій, при яких додається нова вершина степеня 1 (висяча вершина) або дублюється наявна вершина (утворюючи близнюків або двійнят), з умовою, що операція подвоєння, в якій дублікат вершини не суміжний своїй парі (двійнята), тільки якщо сусіди цих подвоєних вершин утворюють кліку. Ці три операції, якщо не застосовувати зазначеної умови, утворюють всі дистанційно-успадковувані графи. Для утворення птолемеєвих графів недостатньо використовувати утворення висячих вершин і близнят, утворення двійнят (при дотриманні зазначених вище умов) теж іноді потрібне. Діаграма Гассе підмножини відношень непорожнього перетину максимальних клік утворює . Опуклі підмножини вершин (підмножини, що містять усі найкоротші шляхи між двома вершинами в підмножині) утворюють опуклу геометрію. Тобто будь-яку опуклу множину можна отримати з повного набору вершин послідовним видаленням крайніх вершин, тобто тих, що не належать якомусь найкоротшому шляху між рештою вершин. У смарагді опуклу множину не можна отримати таким способом, оскільки ні , ні не є крайніми.
Обчислювальна складність Ґрунтуючись на описі орієнтованими деревами, птолемеєві графи можна розпізнати за лінійний час.
Примітки
Література