Graciös uppmärkning

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 februari 2021; kontroller kräver 3 redigeringar .

Graciös märkning i grafteori är en sådan hörnmärkning av en graf med kanter med någon delmängd av heltal mellan 0 och inklusive att olika hörn är märkta med olika siffror, och så att om varje kant är märkt med den absoluta skillnaden mellan etiketterna för hörn som den förbinder, då kommer alla resulterande skillnader att vara olika [1] . En graf som tillåter graciös märkning kallas en graciös graf .

Författaren till termen "graciös uppmärkning" är Solomon Golomb ; Alexander Rosa var den första att peka ut denna klass av märkning och introducerade den under namnet -markup i en uppsats från 1967 om grafmärkning .  [2] .

En av de viktigaste obevisade hypoteserna inom grafteorin är Graceful Tree Conjecture , även känd som Ringel -Kotzig-förmodan efter Gerhard Ringel och Anton Kotzig , som formulerade den , som säger att alla träd är graciösa... Från och med 2017 är gissningen fortfarande inte bevisad, men på grund av formuleringens enkelhet väckte den stor uppmärksamhet av matematikälskare (som ett resultat av vilket många felaktiga bevis dök upp), Kotzig beskrev en gång till och med massförsök att bevisa det som en "sjukdom" [3] .   

Huvudresultat

I originalet visade Rosa att en Euler-graf med m ≡ 1 (mod 4) eller m ≡ 2 (mod 4) kanter inte kan vara graciös. [2] visar den också att cykeln Cn är graciös om och endast om n ≡ 0 (mod 4) eller n ≡ 3 (mod 4).

Graciösa är alla stigar , larver , alla hummer med perfekt matchning [4] , alla hjul , nät , roder , kugghjul , alla rektangulära gitter [5] , såväl som alla n -dimensionella hyperkuber [ 6] . Alla enkla grafer med 4 eller färre hörn är graciösa, de enda icke-graciösa enkla graferna på fem hörn är 5 -cykeln ( pentagon ), den kompletta K 5 - grafen och fjärilen [7] .

Alla träd med högst 27 hörn är graciösa; detta resultat erhölls av Aldred och McKay 1998 med hjälp av ett datorprogram [  5] [8] ; förbättringen av deras tillvägagångssätt (med en annan beräkningsmetod) gjorde det möjligt att visa 2010 att alla träd upp till 35 hörn inklusive är graciösa - detta är resultatet av Graceful Tree Verification Project som leds av Wenjie Fang [9] .

Anteckningar

  1. ^ Virginia Vassilevska, "Kodning och graciös märkning av träd." SURF 2001. PostScript Arkiverad 25 september 2006 på Wayback Machine
  2. ↑ 1 2 Rosa, A. Theory of Graphs (Internat. Sympos., Rome, 1966)  (ospecificerat) . - New York: Gordon and Breach, 1967. - S. 349-355 .
  3. ↑ Huang, C.; Kotzig, A.; Rosa, A. Ytterligare resultat om trädmärkningar  (obestämd)  // Utilitas Mathematica. - 1982. - T. 21 . - S. 31-48 .
  4. ↑ Morgan, David. Alla hummer med perfekt matchning är graciösa  //  Bulletin of Institute of Combinatorics and its Applications. - 2008. - T. 53 . - S. 82-85 .
  5. ↑ 1 2 Gallian, Joseph A. En dynamisk undersökning av grafmärkning  // Electronic  Journal of Combinatorics : journal. — 1998; 18:e upplagan 2015. - Vol. 5 . - P. Dynamic Survey 6 (elektronisk), i 1:a upplagan 43 sidor, på 18:e - 389 sidor .
  6. ↑ Kotzig, Anton. Nedbrytningar av kompletta grafer till isomorfa kuber  (engelska)  // Journal of Combinatorial Theory. Serie B  : tidskrift. - 1981. - Vol. 31 , nr. 3 . - s. 292-296 . - doi : 10.1016/0095-8956(81)90031-9 .
  7. ↑ Weisstein, Eric W. Graceful graf  på Wolfram MathWorld- webbplatsen .
  8. ↑ Aldred, REL; McKay, Brendan D. Graciösa och harmoniska märkningar av träd  (neopr.)  // Bulletin of Institute of Combinatorics and its Applications. - 1998. - T. 23 . - S. 69-72 .
  9. ↑ Fang, Wenjie. A Computational Approach to the Graceful Tree Conjecture  (engelska)  : tidskrift. - 2010. - arXiv : 1003.3045 . Se även Graceful Tree Verification Project

Litteratur