Contele Ptolemeic
În teoria grafurilor ptolemeice , un graf este un graf nedirecționat în care cele mai scurte distanțe ale drumului satisfac inegalitatea lui Ptolemeu ( astronomul și matematicianul grec Ptolemeu ) . Graficele ptolemeice sunt tocmai grafice care sunt atât cordale , cât și moștenite la distanță . Aceste grafice includ grafice bloc [1] și sunt o subclasă de grafice perfecte .
Descriere
Un grafic este ptolemeic dacă și numai dacă îndeplinește următoarele condiții echivalente:
- Distanțele pe calea cea mai scurtă satisfac inegalitatea lui Ptolemeu - pentru oricare patru vârfuri u , v , w și x inegalitatea d ( u , v ) d ( w , x ) + d ( u , x ) d ( v , w ) ≥ d ( u , w ) d ( v , x ) [1] . De exemplu, graficul de smarald (3-fan) din figură nu este ptolemaic, deoarece în acest grafic d ( u , w ) d ( v , x ) = 4 este mai mare decât d ( u , v ) d ( w , x ) ) + d ( u , x ) d ( v , w ) = 3 .
- Pentru orice clicuri maxime suprapuse , intersecția lor este separatorul care separă diferența dintre cele două clicuri [2] . Acesta nu este cazul graficului de smarald din ilustrație - clicurile uvy și wxy nu sunt separate prin intersecția lor y , deoarece există o margine vw care conectează clicurile.
- Orice ciclu cu k vârfuri are cel puțin 3( k − 3)/2 diagonale [2] .
- Graficul este atât cordal (orice ciclu cu lungime mai mare de trei are o diagonală) cât și distanță moștenit (orice subgraf generat conectat are aceleași distanțe ca întregul grafic) [2] . Graficul de smarald este cordal, dar nu moștenit de distanță — în subgraful generat de uvwx , distanța de la u la x este 3, care este mai mare decât distanța dintre aceleași vârfuri din graficul complet. Deoarece atât graficele cordale cât și cele moștenite de distanță sunt perfecte , la fel sunt și graficele ptolemeice [3] .
- Graficul este cordal și nu conține smaralde - grafice formate prin adăugarea a două diagonale care nu se intersectează la un pentagon [3] .
- Graficul este moștenit pe distanță și nu conține 4-cicluri generate [4] .
- Un grafic poate fi construit dintr-un singur vârf printr-o succesiune de operații în care se adaugă un nou vârf de gradul 1 (atârnat) sau se dublează un vârf existent (formând gemeni sau gemeni), cu condiția ca operația de dublare, în care vârful duplicat nu este adiacent perechii sale (gemeni), doar dacă vecinii acestor vârfuri dublate formează o clică. Aceste trei operații, dacă condiția specificată nu este aplicată, formează toate graficele moștenite de distanță. Pentru formarea graficelor ptolemeice nu este suficient să folosiți formarea de vârfuri și gemeni suspendați, uneori este necesară și formarea de gemeni (sub rezerva condițiilor de mai sus) [5] .
- Diagrama Hasse a unei submulțimi de relații de intersecție nevide a clicurilor maxime formează un arbore orientat [6] .
- Subseturile de vârfuri convexe (subseturile care conțin toate căile cele mai scurte între două vârfuri din submulțime) formează o geometrie convexă . Adică, orice mulțime convexă poate fi obținută dintr-un set complet de vârfuri prin eliminarea secvențială a vârfurilor extreme, adică neaparținând vreunei căi mai scurte între vârfurile rămase [7] . În smarald , mulțimea convexă uxy nu poate fi obținută în acest fel, deoarece nici v și nici w nu sunt extreme.
Complexitate computațională
Pe baza descrierii prin arbori direcționați, graficele ptolemeice pot fi recunoscute în timp liniar [6] .
Note
- ↑ 1 2 Kay, Chartrand, 1965 , p. 342–346.
- ↑ 1 2 3 Howorka, 1981 , p. 323–331.
- ↑ 1 2 Graphclass: ptolemaic , < http://www.graphclasses.org/classes/gc_95.html > . Consultat la 5 iunie 2016. Arhivat la 30 martie 2016 la Wayback Machine .
- ↑ McKee, 2010 , p. 651–661.
- ↑ Bandelt, Mulder, 1986 , p. 182–208.
- ↑ 1 2 Uehara, Uno, 2009 , p. 1533–1543
- ↑ Farber, Jamison, 1986 , p. 433–444.
Literatură