K-strom

V teorii grafů je k - strom typem neorientovaného grafu . Graf je k-strom, pokud ho lze získat následujícím způsobem: začneme od úplného grafu s ( k  + 1) vrcholy, pak přidáme vrcholy tak, že pro vrchol v přidané v má přesně k sousedů v graf v době přidání a tito sousedé tvoří kliku .

Charakterizace

K - stromy jsou přesně grafy dané šířky stromu , maximální v tom smyslu, že nelze přidat hrany bez zvětšení jejich šířky. Jsou to také přesně srdcové grafy, jejichž všechny maximální kliky mají stejnou velikost k  + 1 a které mají všechny minimální oddělovače kliky také stejnou velikost k .

Přidružené třídy grafů

1-stromy jsou nezakořeněné stromy . 2-stromy jsou maximální sériově paralelní grafy a také maximální vnější rovinné grafy . Rovinné 3-stromy jsou také známé jako apollonské sítě . Grafy, které mají šířku stromu maximálně k, jsou přesně podgrafy k - stromů, a proto se jim říká částečné k-stromy  (in) .

Grafy tvořené hranami a vrcholy skládaných polytopů dimenze k (které jsou polytopy vytvořené počínaje simplexem, pak opakovaným vkládáním simplexů na plochy polytopu) jsou k- stromy, když k  ≥ 3 Tento proces vkládání napodobuje konstrukci k - stromů přidáním vrcholů do kliky. K -tree je graf skládaný mnohostěnu tehdy a jen tehdy, pokud nejsou tři kliky o k  + 1), které mají vrcholy k vrcholy společné.

Poznámky a odkazy

  1. (in) HP Patil , „  On the structure of k -trees  “ , Journal of Combinatorics, Information and System Sciences , sv.  11, n kost  2-4,1986, str.  57–64 ( Math Reviews  966069 ).
  2. (en) Jaroslav Nesetril a Patrice Ossona de Mendez , „Strukturální vlastnosti řídkých grafů“ v dílech Martina Grötschela a Gyula OH Katona (redaktoři), Budování mostů: mezi matematikou a informatikou , Springer-Verlag, al.  "Bolyai společnost Matematická studie" ( n o  19), 2008( ISBN  978-3-540-85218-6 , číst online ) , s.  390.
  3. (in) Frank Hwang Dana Richards a Pawel Winter , „Polynomially Solvent Cases“ , The Steiner Tree Problem , sv.  53, Elsevier, kol.  "Annals of Discrete Mathematics (North-Holland Mathematics Studies)",1992( ISBN  978-0-444-89098-6 ) , str.  177.
  4. (in) Olivier Bodini, Alexis Darrasse a Michele Soria, „  Vzdálenosti v náhodných apollonských síťových strukturách  “ , 20. výroční mezinárodní konference o formálních výkonových řadách a algebraické kombinatorice (FPSAC2008) , Vina del Mar, Chile,červen 2008, str.  307-318 ( HAL  hal-00345749 , číst online , konzultováno 25. října 2020 ).
  5. (in) Etan Koch a Micha A. Perles , "Krycí účinnost stromy a k- -trees" , ve sborníku z konference sedmého Kombinatorický Southeastern, teorie grafů a výpočetní techniky (Louisiana State Univ., Baton Rouge, La., 1976 ) , Utilitas Math., Winnipeg, Man., Coll.  "  Congressus Numerantium  " ( n o  XVII)1976( Math Reviews  0457265 ) , str.  391–420. Congressus Numerantium, č. XVII.
  6. (in) Alexander Below , Jesús A. De Loera a Jürgen Richter-Gebert , „  Složitost hledání malých triangulací konvexních 3-polytopů  “ , Journal of Algorithms , sv.  50, n O  2 2004, str.  134–167 ( DOI  10.1016 / S0196-6774 (03) 00092-0 ).
  7. (De) Peter Kleinschmidt, „  Eine graphentheoretische Kennzeichnung der Stapelpolytope  “ , Archiv der Mathematik , sv.  27, n o  1, 1976, str.  663–667 ( DOI  10.1007 / BF01224736 ).

Další bibliografie