Ptolemaioksen kreivi
Ptolemaioksen graafiteoriassa graafi on suuntaamaton graafi , jossa lyhyimmät polun etäisyydet täyttävät Ptolemaioksen ( kreikkalainen tähtitieteilijä ja matemaatikko Ptolemaios ) epäyhtälön . Ptolemaioksen graafit ovat täsmälleen kaavioita, jotka ovat sekä sointu- että etäisyysperiytyviä . Nämä kaaviot sisältävät lohkokaavioita [1] ja ovat täydellisten kuvaajien alaluokka .
Kuvaus
Graafi on Ptolemaios, jos ja vain, jos se täyttää seuraavat vastaavat ehdot:
- Lyhimmän polun etäisyydet täyttävät Ptolemaioksen epäyhtälön - millä tahansa neljällä pisteellä u , v , w ja x epäyhtälö d ( u , v ) d ( w , x ) + d ( u , x ) d ( v , w ) ≥ d ( u , w ) d ( v , x ) [1] . Esimerkiksi kuvassa oleva smaragdigraafi (3-fan) ei ole Ptolemaios, koska tässä kaaviossa d ( u , w ) d ( v , x ) = 4 on suurempi kuin d ( u , v ) d ( w , x ) ) + d ( u , x ) d ( v , w ) = 3 .
- Mahdollisille päällekkäisille maksimiklikeille niiden leikkauspiste on erotin , joka erottaa kahden klikkin välisen eron [2] . Tämä ei päde kuvassa olevaan smaragdigraafiin - klikejä uvy ja wxy ei eroteta niiden leikkauspisteestä y , koska klikejä yhdistää reuna vw .
- Jokaisella syklillä , jossa on k pistettä, on vähintään 3( k − 3)/2 diagonaalia [2] .
- Graafi on sekä sointu (millä tahansa syklillä, jonka pituus on suurempi kuin kolme, on diagonaali) että etäisyyden periytyvä (millä tahansa yhdistetyllä generoidulla osagraafilla on samat etäisyydet kuin koko graafilla) [2] . Smaragdigraafi on sointu, mutta ei etäisyyden periytyvä — uvwx:n luomassa aligraafissa etäisyys u : sta x : ään on 3, mikä on suurempi kuin etäisyys samojen kärkien välillä koko graafissa. Koska sekä sointu- että etäisyysperiytyneet graafit ovat täydellisiä , ovat myös Ptolemaioksen graafit [3] .
- Kaavio on sointu eikä sisällä smaragdeja - kaavioita, jotka on muodostettu lisäämällä kaksi ei-leikkautuvaa lävistäjää viisikulmioon [3] .
- Kaavio on etäisyyden peritty, eikä se sisällä generoituja 4-jaksoja [4] .
- Graafi voidaan rakentaa yhdestä kärjestä operaatiosarjalla, jossa lisätään uusi 1-asteinen kärki (riippuva) tai olemassa oleva kärki monistetaan (muodostetaan kaksoset tai kaksoset), sillä ehdolla, että tuplausoperaatio, jossa kaksoispiste ei ole parinsa (kaksosten) vieressä vain, jos näiden kaksinkertaisten kärkien naapurit muodostavat klikkin. Jos määritettyä ehtoa ei sovelleta, nämä kolme operaatiota muodostavat kaikki etäisyyden periytyneet kuvaajat. Ptolemaioksen graafien muodostamiseen ei riitä, että käytetään riippuvien kärkien ja kaksosten muodostamista, vaan joskus tarvitaan myös kaksosten muodostamista (edellä mainituin ehdoin) [5] .
- Maksimiklikkien ei-tyhjän leikkauspisteen suhteiden osajoukon Hasse-kaavio muodostaa orientoidun puun [6] .
- Konveksit huippupisteiden osajoukot (osajoukot, jotka sisältävät kaikki lyhyimmät polut osajoukon kahden kärjen välillä) muodostavat konveksin geometrian . Toisin sanoen mikä tahansa konveksi joukko voidaan saada täydellisestä pistejoukosta poistamalla peräkkäin ääripisteet, eli ne eivät kuulu mihinkään lyhimpään polkuun jäljellä olevien kärkien välillä [7] . Smaragdissa kuperaa joukkoa uxy ei voida saada tällä tavalla, koska v ja w eivät ole äärimmäisiä.
Laskennallinen monimutkaisuus
Suunnattujen puiden kuvauksen perusteella Ptolemaioksen graafit voidaan tunnistaa lineaarisessa ajassa [6] .
Muistiinpanot
- ↑ 1 2 Kay, Chartrand, 1965 , s. 342-346.
- ↑ 1 2 3 Howorka, 1981 , s. 323-331.
- ↑ 1 2 Graphclass: ptolemaic , < http://www.graphclasses.org/classes/gc_95.html > . Haettu 5. kesäkuuta 2016. Arkistoitu 30. maaliskuuta 2016 Wayback Machinessa .
- ↑ McKee, 2010 , s. 651–661.
- ↑ Bandelt, Mulder, 1986 , s. 182-208.
- ↑ 1 2 Uehara, Uno, 2009 , s. 1533-1543
- ↑ Farber, Jamison, 1986 , s. 433–444.
Kirjallisuus