Ptolemaiosz gróf

A ptolemaioszi gráfelméletben a gráf olyan irányítatlan gráf , amelyben a legrövidebb úttávolságok kielégítik Ptolemaiosz ( görög csillagász és matematikus Ptolemaiosz ) egyenlőtlenségét . A Ptolemaioszi gráfok pontosan olyan gráfok, amelyek akkordális és távolság öröklöttek . Ezek a gráfok blokkgráfokat [1] tartalmaznak, és a tökéletes gráfok alosztályát képezik .

Leírás

Egy gráf akkor és csak akkor ptolemaioszi, ha teljesíti a következő egyenértékű feltételeket:

• A legrövidebb út mentén lévő távolságok kielégítik Ptolemaiosz egyenlőtlenségét – bármely négy u , v , w és x csúcsra a d ( u , v ) d ( w , x ) + d ( u , x ) d ( v , w ) ≥ d ( u , w ) d ( v , x ) [1] . Például az ábrán látható smaragd gráf (3-fan) nem ptolemaioszi, mert ebben a gráfban d ( u , w ) d ( v , x ) = 4 nagyobb, mint d ( u , v ) d ( w , x ) ) + d ( u , x ) d ( v , w ) = 3 .
• Az átfedő maximális klikkek metszéspontja az az elválasztó , amely elválasztja a két klikk közötti különbséget [2] . Nem ez a helyzet az ábrán látható smaragd gráf esetében – az uvy és wxy klikkeket nem választja el egymástól y metszéspontja , mivel a klikkeket vw él köti össze.
• Minden k csúcsú ciklusnak legalább 3( k − 3)/2 átlója van [2] .
• A gráf egyszerre akkordális (minden háromnál nagyobb ciklusnak van átlója), és távolság öröklött (bármely összekapcsolt generált részgráf távolsága megegyezik a teljes gráf távolságával) [2] . A smaragd gráf akkordális, de nem távolságöröklött – az uvwx által generált részgráfban az u és x távolság 3, ami nagyobb, mint a teljes gráf ugyanazon csúcsai közötti távolság. Mivel az akkordális és a távolság öröklött gráfok is tökéletesek , így a Ptolemaioszi gráfok is tökéletesek [3] .
• A gráf akkordális, és nem tartalmaz smaragdokat – olyan gráfokat, amelyek két, nem metsző átlónak egy ötszöghöz való hozzáadásával jönnek létre [3] .
• A grafikon távolság öröklött, és nem tartalmaz generált 4 ciklust [4] .
• Egy gráf egyetlen csúcsból építhető fel olyan műveletsorral, amelyben egy új 1-es fokú (függő) csúcsot adunk hozzá, vagy egy meglévő csúcsot duplikálunk (ikreket vagy ikreket képezve), azzal a feltétellel, hogy a duplázási művelet, a duplikált csúcs nem szomszédos a párjával (ikrekkel), csak akkor, ha ezeknek a kettős csúcsoknak a szomszédai klikket alkotnak. Ez a három művelet, ha a megadott feltétel nincs alkalmazva, az összes távolság öröklött gráfot alkot. A Ptolemaioszi gráfok kialakításához nem elegendő a függőcsúcsok és ikrek képzését használni, esetenként ikrek képzése is szükséges (a fenti feltételeknek megfelelően) [5] .
• A maximális klikkek nem üres metszéspontjából álló relációk részhalmazának Hasse-diagramja egy orientált fát alkot [6] .
• A konvex csúcsrészhalmazok (a részhalmaz két csúcsa közötti összes legrövidebb utat tartalmazó részhalmazok) konvex geometriát alkotnak . Azaz bármely konvex halmaz megkapható a csúcsok teljes halmazából a szélső csúcsok szekvenciális eltávolításával, azaz nem tartozik a fennmaradó csúcsok közötti legrövidebb úthoz [7] . A smaragdban az uxy konvex halmaz így nem érhető el, mivel sem v , sem w nem szélsőséges.

Számítási összetettség

Az irányított fák általi leírás alapján a Ptolemaioszi gráfok lineáris időben felismerhetők [6] .

Jegyzetek

1. ↑ 1 2 Kay, Chartrand, 1965 , p. 342–346.
2. ↑ 1 2 3 Howorka, 1981 , p. 323–331.
3. ↑ 1 2 Graphclass: ptolemaic , < http://www.graphclasses.org/classes/gc_95.html > . Letöltve: 2016. június 5. Archiválva : 2016. március 30. a Wayback Machine -nél . 
4. ↑ McKee, 2010 , p. 651–661.
5. ↑ Bandelt, Mulder, 1986 , p. 182–208.
6. ↑ 1 2 Uehara, Uno, 2009 , p. 1533–1543
7. ↑ Farber, Jamison, 1986 , p. 433–444.

Irodalom

• Hans-Jürgen Bandelt, Henry Martyn Mulder. Távolság-örökletes gráfok // Journal of Combinatorial Theory . - 1986. - 1. évf. 41. sz. 2. - P. 182-208. - doi : 10.1016/0095-8956(86)90043-2 .
• Martin Farber, Robert E. Jamison. Konvexitás gráfokban és hipergráfokban // SIAM Journal on Algebraic and Discrete Methods . - 1986. - 1. évf. 7, sz. 3. - P. 433-444. - doi : 10.1137/0607049 .
• Edward Howorka. Ptolemaioszi gráfok jellemzése // Journal of Graph Theory . - 1981. - 1. évf. 5, sz. 3. - P. 323-331. - doi : 10.1002/jgt.3190050314 .
• David C. Kay, Gary Chartrand.  Egyes ptolemaioszi gráfok jellemzése  // Canadian Journal of Mathematics . - 1965. - 1. évf. 17. - P. 342-346. - doi : 10.4153/CJM-1965-034-0 .
• Terry A. McKee. Ptolemaioszi gráfok klikk gráf reprezentációi // Discussions Mathematicae Graph Theory. - 2010. - 20. évf. 30, sz. 4. - P. 651-661. - doi : 10.7151/dmgt.1520 .
• Ryuhei Uehara, Yushi Uno. Ptolemaioszi gráfok lamináris szerkezete alkalmazásokkal // Discrete Applied Mathematics . - 2009. - Vol. 157. sz. 7. - P. 1533-1543. - doi : 10.1016/j.dam.2008.09.006 .