Ptolemaiovský hrabě
V Ptolemaiově teorii grafů je grafem neorientovaný graf , ve kterém nejkratší vzdálenosti cesty uspokojují Ptolemaiovu ( řecký astronom a matematik Ptolemaios ) nerovnost . Ptolemaiovské grafy jsou přesně grafy, které jsou jak chordální , tak zděděné podle vzdálenosti . Tyto grafy zahrnují blokové grafy [1] a jsou podtřídou dokonalých grafů .
Popis
Graf je ptolemaiovský právě tehdy, když splňuje následující ekvivalentní podmínky:
- Vzdálenosti podél nejkratší cesty splňují Ptolemaiovu nerovnost - pro libovolné čtyři vrcholy u , v , w a x je nerovnost d ( u , v ) d ( w , x ) + d ( u , x ) d ( v , w ) ≥ d ( u , w ) d ( v , x ) [1] . Například smaragdový graf (3-ventilátor) na obrázku není ptolemaiovský, protože v tomto grafu d ( u , w ) d ( v , x ) = 4 je větší než d ( u , v ) d ( w , x ) + d ( u , x ) d ( v , w ) = 3 .
- Pro všechny překrývající se maximální kliky je jejich průsečík separátorem , který odděluje rozdíl mezi dvěma klikami [2] . Toto není případ smaragdového grafu na obrázku - kliky uvy a wxy nejsou odděleny svým průsečíkem y , protože kliky spojuje hrana vw .
- Každý cyklus s k vrcholy má alespoň 3( k − 3)/2 úhlopříček [2] .
- Graf je jak tětivový (každý cyklus s délkou větší než tři má úhlopříčku), tak zděděný podle vzdálenosti (jakýkoli připojený vygenerovaný podgraf má stejné vzdálenosti jako celý graf) [2] . Smaragdový graf je chordální, ale není zděděný vzdáleností — v podgrafu generovaném pomocí uvwx je vzdálenost od u do x 3, což je větší než vzdálenost mezi stejnými vrcholy v úplném grafu. Protože oba akordické grafy a grafy zděděné vzdáleností jsou dokonalé , jsou dokonalé i Ptolemaiovy grafy [3] .
- Graf je tětivový a neobsahuje smaragdy - grafy vzniklé přidáním dvou neprotínajících se úhlopříček do pětiúhelníku [3] .
- Graf je zděděný podle vzdálenosti a neobsahuje vygenerované 4-cykly [4] .
- Graf lze sestavit z jednoho vrcholu posloupností operací, ve kterých je přidán nový vrchol stupně 1 (závěsný) nebo existující vrchol duplikován (vytvoření dvojčat nebo dvojčat), s podmínkou, že operace zdvojení, ve které duplicitní vrchol nesousedí s jeho dvojicí (dvojčaty), pouze pokud sousedé těchto zdvojených vrcholů tvoří kliku. Tyto tři operace, pokud není použita zadaná podmínka, tvoří všechny grafy zděděné vzdáleností. Pro tvorbu ptolemaiovských grafů nestačí použít tvorbu visutých vrcholů a dvojčat, někdy je zapotřebí i tvorba dvojčat (za výše uvedených podmínek) [5] .
- Hasseův diagram podmnožiny relací neprázdného průniku maximálních klik tvoří orientovaný strom [6] .
- Podmnožiny konvexních vrcholů (podmnožiny obsahující všechny nejkratší cesty mezi dvěma vrcholy v podmnožině) tvoří konvexní geometrii . To znamená, že libovolnou konvexní množinu lze získat z kompletní množiny vrcholů postupným odstraňováním extrémních vrcholů, to znamená, že nepatří k žádné nejkratší cestě mezi zbývajícími vrcholy [7] . Ve smaragdu nelze konvexní množinu uxy získat tímto způsobem, protože ani v ani w nejsou extrémní.
Výpočetní složitost
Na základě popisu usměrněnými stromy lze v lineárním čase rozpoznat Ptolemaiovy grafy [6] .
Poznámky
- ↑ 1 2 Kay, Chartrand, 1965 , s. 342–346.
- ↑ 1 2 3 Howorka, 1981 , str. 323–331.
- ↑ 1 2 Graphclass: ptolemaic , < http://www.graphclasses.org/classes/gc_95.html > . Získáno 5. června 2016. Archivováno 30. března 2016 na Wayback Machine .
- ↑ McKee, 2010 , str. 651–661.
- ↑ Bandelt, Mulder, 1986 , str. 182–208.
- ↑ 1 2 Uehara, Uno, 2009 , str. 1533–1543
- ↑ Farber, Jamison, 1986 , str. 433–444.
Literatura