Ptolemæiske Greve
I Ptolemæisk grafteori er en graf en urettet graf , hvor de korteste vejafstande opfylder Ptolemæus's ( græske astronom og matematiker Ptolemæus ) ulighed . Ptolemæiske grafer er netop grafer, der er både akkordale og afstandsnedarvede . Disse grafer inkluderer blokgrafer [1] og er en underklasse af perfekte grafer .
Beskrivelse
En graf er ptolemæisk, hvis og kun hvis den opfylder følgende ækvivalente betingelser:
- Afstande langs den korteste vej opfylder Ptolemæus' ulighed - for alle fire hjørner u , v , w og x uligheden d ( u , v ) d ( w , x ) + d ( u , x ) d ( v , w ) ≥ d ( u , w ) d ( v , x ) [1] . For eksempel er smaragdgrafen (3-fan) i figuren ikke ptolemæisk, fordi i denne graf er d ( u , w ) d ( v , x ) = 4 større end d ( u , v ) d ( w , x ) + d ( u , x ) d ( v , w ) = 3 .
- For alle overlappende maksimumkliker er deres skæringspunkt den adskillelsestegn , der adskiller forskellen mellem de to kliker [2] . Dette er ikke tilfældet for smaragdgrafen i illustrationen - klikerne uvy og wxy er ikke adskilt af deres skæringspunkt y , da der er en kant vw , der forbinder klikerne.
- Enhver cyklus med k hjørner har mindst 3( k − 3)/2 diagonaler [2] .
- Grafen er både akkordal (enhver cyklus med en længde større end tre har en diagonal) og afstandsnedarvet (enhver forbundet genereret subgraf har samme afstande som hele grafen) [2] . Smaragdgrafen er kordal , men ikke afstandsnedarvet - i subgrafen genereret af uvwx er afstanden fra u til x 3, hvilket er større end afstanden mellem de samme hjørner i hele grafen. Da både akkord- og afstandsnedarvede grafer er perfekte , er ptolemæiske grafer også [3] .
- Grafen er kordal og indeholder ikke smaragder - grafer dannet ved at tilføje to ikke-skærende diagonaler til en femkant [3] .
- Grafen er afstandsnedarvet og indeholder ikke genererede 4-cyklusser [4] .
- En graf kan bygges ud fra et enkelt toppunkt ved en sekvens af operationer, hvor et nyt toppunkt af grad 1 (hængende) tilføjes eller et eksisterende toppunkt duplikeres (danner tvillinger eller tvillinger), med den betingelse at fordoblingsoperationen, hvor det duplikerede toppunkt støder ikke op til sit par (tvillinger), kun hvis naboerne til disse fordoblede hjørner danner en klike. Disse tre operationer, hvis den angivne betingelse ikke anvendes, danner alle afstandsarvede grafer. Til dannelsen af ptolemæiske grafer er det ikke nok at bruge dannelsen af hængende hjørner og tvillinger, dannelsen af tvillinger (underlagt ovenstående betingelser) er også nogle gange påkrævet [5] .
- Hasse-diagrammet af en delmængde af relationer af ikke-tom skæringspunkt mellem maksimale kliker danner et orienteret træ [6] .
- Konvekse toppunkt-delmængder (delmængder, der indeholder alle korteste veje mellem to hjørner i undermængden) danner en konveks geometri . Det vil sige, at ethvert konveks sæt kan opnås fra et komplet sæt toppunkter ved sekventielt at fjerne de ekstreme toppunkter, det vil sige, at de ikke hører til nogen korteste vej mellem de resterende toppunkter [7] . I smaragd kan den konvekse mængde uxy ikke opnås på denne måde, da hverken v eller w er ekstreme.
Beregningsmæssig kompleksitet
Baseret på beskrivelsen af rettede træer kan ptolemæiske grafer genkendes i lineær tid [6] .
Noter
- ↑ 1 2 Kay, Chartrand, 1965 , s. 342-346.
- ↑ 1 2 3 Howorka, 1981 , s. 323-331.
- ↑ 1 2 Grafklasse: ptolemæisk , < http://www.graphclasses.org/classes/gc_95.html > . Hentet 5. juni 2016. Arkiveret 30. marts 2016 på Wayback Machine .
- ↑ 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.
Litteratur