Earl tähti

Tähtigraafi on yhdistetty graafi , jonka kaikki reunat ovat peräisin samasta kärjestä. Tähti, jolla on kärki, on yleensä merkitty , jota kutsutaan tähden järjestykseksi.

Muut määritelmät

Graafista-tähteä, jossa on kolme kylkiluuta, kutsutaan tassuksi tai kynsiksi [2] ( eng.  claw ).

Tähtigraafilla S k on kärkien armo, kun k on parillinen, ja ei, jos k on pariton.

Tähtigraafia voidaan kuvata myös yhdistettynä graafina , jossa korkeintaan yhden kärjen aste on suurempi kuin yksi.

Suhde muun tyyppisiin kaavioihin

Kynsikuvaajat ovat tärkeitä määriteltäessä kynsittömät graafit, graafit, joissa ei ole alagraafia, jotka ovat kynsiä [3] [4] .

Tähtikaavio on erityinen puu . Kuten mikä tahansa puu , tähtikaavio voidaan koodata käyttämällä Prüfer - sekvenssiä ; tähtigraafin K 1, k Prufer-sekvenssi koostuu k − 1 kopiosta keskuspisteestä [5] .  

Muut käyttötarkoitukset

Kynsigraafin kärkien välisten etäisyyksien joukko on esimerkki metriavaruudesta , jota ei voida isometrisesti upottaa minkään ulottuvuuden euklidiseen avaruuteen [6] .

Tähtikaavion muotoon rakennetun Zvezdan tietokoneverkon topologialla on tärkeä rooli hajautetussa tietojenkäsittelyssä .

Muistiinpanot

  1. ↑ VSUESin julkiset koulutusmateriaalit . Haettu 3. lokakuuta 2016. Arkistoitu alkuperäisestä 5. lokakuuta 2016.
  2. ↑ V.A. Evstigneev, V.N. Kasjanov. Tietojenkäsittelytieteen graafien sanakirja. - Novosibirsk. — (Ohjelmien suunnittelu ja optimointi). - ISBN 978-591124-036-3 .
  3. ↑ Faudree, Ralph ; Flandrin, Evelyne & Ryjáček, Zdeněk (1997), Claw-free graphs - A survey , Discrete Mathematics , osa 164 (1–3): 87–147 , DOI 10.1016/S0012-365X(96)00045-3  .
  4. ↑ Chudnovsky, Maria & Seymour, Paul (2005), The structure of claw-free graphs , Surveys in Combinatorics 2005 , voi. 327, Lontoo Math. soc. Lecture Note Ser., Cambridge: Cambridge Univ. Paina, s. 153–171 , < http://www.columbia.edu/~mc2775/claws_survey.pdf > Arkistoitu 23. lokakuuta 2012 Wayback Machinessa . 
  5. ↑ Gottlieb, J.; Julstrom, B.A.; Rothlauf, F. & Raidl, GR (2001), Prüfer-luvut: Huono esitys virittävistä puista evolutionaariseen hakuun , Proc. Genetic and Evolutionary Computation Conference , Morgan Kaufmann, s. 343–350 , < http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf > . Haettu 4. tammikuuta 2013. Arkistoitu 26. syyskuuta 2006 Wayback Machinessa .  
  6. ↑ Linial, Nathan (2002), äärelliset metriset avaruudet – kombinatoriikka, geometria ja algoritmit, Proc. International Congress of Mathematicians, Beijing , voi. 3, s. 573–586