Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

У теорії графів птолеме їв граф це неорієнтований граф у якому відстані по найкоротшому шляху задовольняють нерівності П

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

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

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

image
Птолемеїв граф
image
Граф-смарагд (або 3-віяло) не Птолемеїв
image
Блоковий граф, різновид птолемеєвих графів
image
Три операції, за допомогою яких можна побудувати будь-який дистанційно-успадковуваний граф. Для птолемеєвих графів сусіди двійнят мають утворювати кліку, щоб запобігти побудові 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 ((висяча вершина)) або дублюється наявна вершина (утворюючи близнюків або двійнят), з умовою, що операція подвоєння, в якій дублікат вершини не суміжний своїй парі (двійнята), тільки якщо сусіди цих подвоєних вершин утворюють кліку. Ці три операції, якщо не застосовувати зазначеної умови, утворюють всі дистанційно-успадковувані графи. Для утворення птолемеєвих графів недостатньо використовувати утворення висячих вершин і близнят, утворення двійнят (при дотриманні зазначених вище умов) теж іноді потрібне.
  • Діаграма Гассе підмножини відношень непорожнього перетину максимальних клік утворює [en].
  • Опуклі підмножини вершин (підмножини, що містять усі найкоротші шляхи між двома вершинами в підмножині) утворюють опуклу геометрію. Тобто будь-яку опуклу множину можна отримати з повного набору вершин послідовним видаленням крайніх вершин, тобто тих, що не належать якомусь найкоротшому шляху між рештою вершин. У смарагді опуклу множину uxy не можна отримати таким способом, оскільки ні v, ні w не є крайніми.

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

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

Примітки

  1. Kay, Chartrand, 1965, с. 342–346.
  2. Howorka, 1981, с. 323–331.
  3. Graphclass: ptolemaic, Information System on Graph Classes and their Inclusions, процитовано 5 червня 2016.
  4. McKee, 2010, с. 651–661.
  5. Bandelt, Mulder, 1986, с. 182–208.
  6. Uehara, Uno, 2009, с. 1533–1543.
  7. Farber, Jamison, 1986, с. 433–444.

Література

  • Hans-Jürgen Bandelt, Henry Martyn Mulder. . Distance-hereditary graphs // . — 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 // . — 1986. — Т. 7, no. 3 (18 липня). — С. 433–444. — DOI:10.1137/0607049.
  • Edward Howorka. . A characterization of Ptolemaic graphs // . — 1981. — Т. 5, no. 3 (18 липня). — С. 323–331. — DOI:10.1002/jgt.3190050314.
  • David C. Kay, Gary Chartrand. . A characterization of certain ptolemaic graphs // . — 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 // . — 2009. — Т. 157, no. 7 (18 липня). — С. 1533–1543. — DOI:10.1016/j.dam.2008.09.006.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

U teoriyi grafiv ptoleme yiv graf ce neoriyentovanij graf u yakomu vidstani po najkorotshomu shlyahu zadovolnyayut nerivnosti Ptolemeya greckogo astronoma i matematika Ptolemeya Ptolemeyevi grafi ce tochno grafi yaki odnochasno ye i hordalnimi i distancijno uspadkovuvanimi Ci grafi vklyuchayut blokovi grafi i ye pidklasom doskonalih grafiv Ptolemeyiv graf Graf smaragd abo 3 viyalo ne Ptolemeyiv Blokovij graf riznovid ptolemeyevih grafiv Tri operaciyi za dopomogoyu yakih mozhna pobuduvati bud yakij distancijno uspadkovuvanij graf Dlya ptolemeyevih grafiv susidi dvijnyat mayut utvoryuvati kliku shob zapobigti pobudovi 4 ciklu pokazanogo tut OpisGraf ye ptolemeyevim todi i tilki todi koli vin zadovolnyaye takim ekvivalentnim umovam Vidstani po najkorotshomu shlyahu zadovolnyayut nerivnosti Ptolemeya dlya bud yakih chotiroh vershin u v w i x vikonuyetsya nerivnist d u v d w x d u x d v w d u w d v x Napriklad graf smaragd 3 viyalo na malyunku ne ye ptolemeyevim oskilki v comu grafi d u w d v x 4 bilshe nizh d u v d w x d u x d v w 3 Dlya bud yakih perekrivnih maksimalnih klik yih peretin ye separatorom yakij rozdilyaye riznicyu cih dvoh klik Dlya grafu smaragdu na malyunku ce ne tak kliki uvy i wxy ne rozdilyayutsya yih peretinom y oskilki isnuye rebro vw sho z yednuye kliki Bud yakij cikl z k vershinami maye shonajmenshe 3 k 3 2 diagonalej Graf ye i hordalnim bud yakij cikl z dovzhinoyu sho perevishuye tri maye diagonal i distancijno uspadkovuvanim bud yakij zv yaznij porodzhenij pidgraf maye ti zh vidstani sho j ves graf Graf smaragd ye hordalnim ale ne distancijno uspadkovuvanim u pidgrafi porodzhenomu uvwx vidstan vid u do x dorivnyuye 3 sho bilshe nizh vidstan mizh timi zh vershinami v povnomu grafi Oskilki yak hordalni tak i distancijno uspadkovuvani grafi ye doskonalimi takimi zh ye i ptolemeyevi grafi Graf hordalnij i ne mistit smaragdiv grafiv utvorenih dodannyam dvoh neperetinnih diagonalej u p yatikutnik Graf ye distancijno uspadkovuvanim i ne mistit porodzhenih 4 cikliv Graf mozhna pobuduvati z yedinoyi vershini poslidovnistyu operacij pri yakih dodayetsya nova vershina stepenya 1 visyacha vershina abo dublyuyetsya nayavna vershina utvoryuyuchi bliznyukiv abo dvijnyat z umovoyu sho operaciya podvoyennya v yakij dublikat vershini ne sumizhnij svoyij pari dvijnyata tilki yaksho susidi cih podvoyenih vershin utvoryuyut kliku Ci tri operaciyi yaksho ne zastosovuvati zaznachenoyi umovi utvoryuyut vsi distancijno uspadkovuvani grafi Dlya utvorennya ptolemeyevih grafiv nedostatno vikoristovuvati utvorennya visyachih vershin i bliznyat utvorennya dvijnyat pri dotrimanni zaznachenih vishe umov tezh inodi potribne Diagrama Gasse pidmnozhini vidnoshen neporozhnogo peretinu maksimalnih klik utvoryuye en Opukli pidmnozhini vershin pidmnozhini sho mistyat usi najkorotshi shlyahi mizh dvoma vershinami v pidmnozhini utvoryuyut opuklu geometriyu Tobto bud yaku opuklu mnozhinu mozhna otrimati z povnogo naboru vershin poslidovnim vidalennyam krajnih vershin tobto tih sho ne nalezhat yakomus najkorotshomu shlyahu mizh reshtoyu vershin U smaragdi opuklu mnozhinu uxy ne mozhna otrimati takim sposobom oskilki ni v ni w ne ye krajnimi Obchislyuvalna skladnistGruntuyuchis na opisi oriyentovanimi derevami ptolemeyevi grafi mozhna rozpiznati za linijnij chas PrimitkiKay Chartrand 1965 s 342 346 Howorka 1981 s 323 331 Graphclass ptolemaic Information System on Graph Classes and their Inclusions procitovano 5 chervnya 2016 McKee 2010 s 651 661 Bandelt Mulder 1986 s 182 208 Uehara Uno 2009 s 1533 1543 Farber Jamison 1986 s 433 444 LiteraturaHans Jurgen Bandelt Henry Martyn Mulder Distance hereditary graphs 1986 T 41 no 2 18 lipnya S 182 208 Series B DOI 10 1016 0095 8956 86 90043 2 Martin Farber Robert E Jamison Convexity in graphs and hypergraphs 1986 T 7 no 3 18 lipnya S 433 444 DOI 10 1137 0607049 Edward Howorka A characterization of Ptolemaic graphs 1981 T 5 no 3 18 lipnya S 323 331 DOI 10 1002 jgt 3190050314 David C Kay Gary Chartrand A characterization of certain ptolemaic graphs 1965 T 17 18 lipnya S 342 346 DOI 10 4153 CJM 1965 034 0 Terry A McKee Clique graph representations of Ptolemaic graphs Discussiones Mathematicae Graph Theory 2010 T 30 no 4 18 lipnya S 651 661 DOI 10 7151 dmgt 1520 Ryuhei Uehara Yushi Uno Laminar structure of Ptolemaic graphs with applications 2009 T 157 no 7 18 lipnya S 1533 1543 DOI 10 1016 j dam 2008 09 006

Дата публікації:
Топ