Ptolemaiovský graf - Ptolemaic graph

Ptolemaiovský graf
The drahokamový graf nebo 3-fan není Ptolemaic.
A blokový graf, speciální případ ptolemaiovského grafu
Tři operace, pomocí kterých lze sestrojit libovolný graf dědičnosti vzdálenosti. U grafů Ptolemaic jsou sousedé falešných dvojčat omezeni na vytvoření kliky, což brání konstrukci zde zobrazeného 4-cyklu.

v teorie grafů, a Ptolemaiovský graf je neorientovaný graf jehož nejkratší cesta vzdálenosti poslouchat Ptolemaiova nerovnost, který byl zase pojmenován po řecký astronom a matematik Ptolemaios. Ptolemaiovské grafy jsou přesně grafy, které jsou oba akordický a na dálku dědičné; patří mezi ně blokové grafy[1] a jsou podtřídou perfektní grafy.

Charakterizace

Graf je Ptolemaiovský právě tehdy, pokud splňuje některou z následujících ekvivalentních podmínek:

  • The nejkratší cesta vzdálenosti poslouchat Ptolemaiova nerovnost: pro každé čtyři vrcholy u, proti, w, a Xnerovnost d(u,proti)d(w,X) + d(u,X)d(proti,w) ≥ d(u,w)d(proti,X) drží.[1] Například drahokamový graf (3-fan) na obrázku není Ptolemaic, protože v tomto grafu d(u,w)d(proti,X) = 4, větší než d(u,proti)d(w,X) + d(u,X)d(proti,w) = 3.
  • Za každé dvě překrývání maximální kliky, průnik dvou klik je a oddělovač který rozděluje rozdíly mezi dvěma klikami.[2] Na ilustraci drahokamového grafu to není pravda: kliky uvy a wxy nejsou odděleny průsečíkem, y, protože je tu hrana vw který spojuje kliky, ale vyhýbá se křižovatce.
  • Každý k-vrchol cyklus má alespoň 3(k − 3)/2 úhlopříčky.[2]
  • Graf je obojí akordický (každý cyklus o délce větší než tři má úhlopříčku) a na dálku dědičné (každý připojen indukovaný podgraf má stejné vzdálenosti jako celý graf).[2] Zobrazený drahokam je akordický, ale nikoli dědičně vzdálený: v podgrafu vyvolaném uvwx, vzdálenost od u na X je 3, větší než vzdálenost mezi stejnými vrcholy v celém grafu. Protože jak chordální, tak vzdálenostně dědičné grafy jsou perfektní grafy, stejně tak Ptolemaiovské grafy.[3]
  • Graf je akordový a neobsahuje indukovaný drahokam, graf vytvořený přidáním dvou nepřekračujících úhlopříček do pětiúhelníku.[3]
  • Graf je dědičně odstupňovaný a neobsahuje znak indukovaný 4-cyklus.[4]
  • Graf lze zkonstruovat z jednoho vrcholu sekvencí operací, které přidávají nový vrchol stupně (přívěsek) nebo duplikují (zdvojnásobují) existující vrchol, s výjimkou operace dvojčete, ve které nový duplicitní vrchol není sousedící s jeho dvojčaty (falešná dvojčata) lze použít pouze tehdy, když sousedé dvojčat vytvoří kliku. Tyto tři operace bez výjimky tvoří veškerý dědičný graf vzdálenosti. K vytvoření všech ptolemaiovských grafů nestačí použít závěsné vrcholy a skutečná dvojčata; někdy je také vyžadován výjimečný případ falešných dvojčat.[5]
  • The Hasseův diagram vztahu podmnožiny na neprázdných křižovatkách maximálních klik tvoří an orientovaný strom.[6]
  • Konvexní podmnožiny vrcholů (podmnožiny, které obsahují každou nejkratší cestu mezi dvěma vrcholy v podmnožině) tvoří konvexní geometrie. To znamená, že každou konvexní množinu lze dosáhnout z celé sady vrcholů opakovaným odstraněním extrémního vrcholu, který nepatří k žádné nejkratší cestě mezi zbývajícími vrcholy.[7] V klenotu je konvexní sada uxy nelze takto dosáhnout, protože ani jeden proti ani w je extrémní.

Výpočetní složitost

Na základě charakterizace orientovanými stromy lze v Ptolemaiovských grafech rozpoznat lineární čas.[6]

Výčet

The generující funkce pro Ptolemaiovské grafy lze popsat symbolicky, což umožňuje rychlý výpočet čísel těchto grafů. Na základě této metody je počet Ptolemaiových grafů s n označené vrcholy, pro Bylo zjištěno, že je[8]

1, 1, 4, 35, 481, 9042, 216077, 6271057, 214248958, 8424002973, 374708368981, 18604033129948, 1019915376831963, ... (sekvence A287886 v OEIS )

Reference

  1. ^ A b Kay, David C .; Chartrand, Gary (1965), „Charakterizace určitých ptolemaiových grafů“, Kanadský žurnál matematiky, 17: 342–346, doi:10.4153 / CJM-1965-034-0, hdl:10338.dmlcz / 126208, PAN  0175113.
  2. ^ A b C Howorka, Edward (1981), „Charakterizace Ptolemaiovských grafů“, Journal of Graph Theory, 5 (3): 323–331, doi:10,1002 / jgt.3190050314, PAN  0625074.
  3. ^ A b "Graphclass: ptolemaic", Informační systém o třídách grafů a jejich začlenění, vyvoláno 2016-06-05.
  4. ^ McKee, Terry A. (2010), „Clique graph representations of Ptolemaic graphs“, Diskuse Mathematicae Graph Theory, 30 (4): 651–661, doi:10,7151 / dmgt.1520, PAN  2761626.
  5. ^ Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), „Dědičné grafy vzdálenosti“, Journal of Combinatorial Theory, Řada B, 41 (2): 182–208, doi:10.1016/0095-8956(86)90043-2, PAN  0859310.
  6. ^ A b Uehara, Ryuhei; Uno, Yushi (2009), „Laminární struktura Ptolemaiovských grafů s aplikacemi“, Diskrétní aplikovaná matematika, 157 (7): 1533–1543, doi:10.1016 / j.dam.2008.09.006, PAN  2510233.
  7. ^ Farber, Martin; Jamison, Robert E. (1986), „Konvexita v grafech a hypergrafech“, SIAM Journal o algebraických a diskrétních metodách, 7 (3): 433–444, doi:10.1137/0607049, hdl:10338.dmlcz / 127659, PAN  0844046.
  8. ^ Bahrani, Maryam; Lumbroso, Jérémie (2018), "Výčty, zakázané charakterizace podgrafu a split-decomposition", Electronic Journal of Combinatorics, 25 (4)