Siro merkintä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 6. helmikuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Graceful labeling graafiteoriassa on sellainen graafin , jossa on reunat, kärkipisteiden merkitseminen jollakin kokonaislukujen osajoukolla välillä 0 ja mukaan lukien, että eri kärjet merkitään eri numeroilla ja siten, että jos jokainen reuna on merkitty graafin nimien absoluuttisella erolla. pisteitä, jotka se yhdistää, niin kaikki tuloksena olevat erot ovat erilaisia ​​[1] . Graceful graph - kaaviota kutsutaan siroksi kaavioksi .

Termin "graceful markup" kirjoittaja on Solomon Golomb ; Alexander Rosa oli ensimmäinen , joka valitsi tämän merkintäluokan ja esitteli sen nimellä -markup vuoden 1967 kaaviomerkintöjä käsittelevässä artikkelissa .  [2] .

Yksi graafiteorian tärkeimmistä todistamattomista hypoteeseista on Graceful Tree Conjecture , joka tunnetaan myös nimellä Ringel- Kotzigin arvelu sen laatineiden Gerhard Ringelin ja Anton Kotzigin mukaan , jonka mukaan kaikki puut ovat siroja . Vuodesta 2017 lähtien olettamusta ei ole vielä todistettu, mutta muotoilun yksinkertaisuuden vuoksi se herätti laajan matematiikan ystävien huomion (jonka seurauksena ilmestyi monia vääriä todisteita), Kotzig kuvasi aikanaan jopa massayrityksiä todistaa se "taudina" [3] .   

Päätulokset

Alkuperäisessä artikkelissa Rosa osoitti, että Euler-graafi , jonka reunat ovat m ≡ 1 (mod 4) tai m ≡ 2 (mod 4), ei voi olla siro. [2] , se osoittaa myös, että sykli C n on siro silloin ja vain jos n ≡ 0 (mod 4) tai n ≡ 3 (mod 4).

Suloisia ovat kaikki polut , toukat , kaikki hummerit täydellisesti yhteensopivilla [4] , kaikki pyörät , verkot , peräsimet , hammaspyörät , kaikki suorakaiteen muotoiset hilat [5] sekä kaikki n -ulotteiset hyperkuutiot [ 6] . Kaikki yksinkertaiset graafit , joissa on 4 tai vähemmän kärkeä, ovat siroja, ainoat ei-siroiset yksinkertaiset graafit viidellä pisteellä ovat 5- sykli ( viisikulmio ), täydellinen K 5 -graafi ja perhonen [7] .

Kaikki puut, joissa on enintään 27 kärkeä, ovat kauniita; Aldred ja McKay saivat tämän tuloksen vuonna 1998 käyttämällä tietokoneohjelmaa [  5] [8] ; niiden lähestymistavan parantaminen (käyttäen eri laskentamenetelmää) mahdollisti vuonna 2010 osoittamisen, että kaikki puut 35 kärkeen asti ovat kauniita - tämä on Wenjie Fangin johtaman Graceful Tree Verification Projectin [9] tulos .

Muistiinpanot

  1. ↑ Virginia Vassilevska, "Puiden koodaus ja siro merkitseminen." SURF 2001. PostScript arkistoitu 25. syyskuuta 2006 Wayback Machinessa
  2. ↑ 1 2 Rosa, A. Graafisten teoria (Internat. Sympos., Rooma, 1966)  (määrittelemätön) . - New York: Gordon and Breach, 1967. - S. 349-355 .
  3. ↑ Huang, C.; Kotzig, A.; Rosa, A. Lisätuloksia puiden merkinnöistä  (määrittämätön)  // Utilitas Mathematica. - 1982. - T. 21 . - S. 31-48 .
  4. ↑ Morgan, David. Kaikki täydellisesti yhteensopivat hummerit ovat kauniita  //  Bulletin of the Institute of Combinatorics and its Applications. - 2008. - T. 53 . - S. 82-85 .
  5. ↑ 1 2 Gallian, Joseph A. Dynaaminen kaaviomerkintöjen tutkimus  // Electronic  Journal of Combinatorics : päiväkirja. - 1998; 18. painos vuonna 2015. - Vol. 5 . - P. Dynamic Survey 6 (sähköinen), 1. painos 43 sivua, 18. - 389 sivua .
  6. ↑ Kotzig, Anton. Täydellisten kuvaajien hajotukset isomorfisiksi kuutioiksi  (englanniksi)  // Journal of Combinatorial Theory. Sarja B  : lehti. - 1981. - Voi. 31 , ei. 3 . - s. 292-296 . - doi : 10.1016/0095-8956(81)90031-9 .
  7. ↑ Weisstein, Eric W. Graceful kaavio  Wolfram MathWorld -verkkosivustolla .
  8. ↑ Aldred, REL; McKay, Brendan D. Graceful and harmonious labellings of trees  (neopr.)  // Bulletin of the Institute of Combinatorics and its Applications. - 1998. - T. 23 . - S. 69-72 .
  9. ↑ Fang, Wenjie. A Computational Approach to the Graceful Tree Conjecture  (englanniksi)  : Journal. - 2010. - arXiv : 1003.3045 . Katso myös Graceful Tree Verification Project

Kirjallisuus