Yndefuld markering

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 6. februar 2021; checks kræver 3 redigeringer .

Yndefuld mærkning i grafteori er en sådan toppunktsmærkning af en graf med kanter med en delmængde af heltal mellem 0 og inklusive, at forskellige hjørner er mærket med forskellige tal, og sådan at hvis hver kant er mærket med den absolutte forskel mellem etiketterne i hjørner, som den forbinder, så vil alle de resulterende forskelle være forskellige [1] . En graf, der tillader yndefuld mærkning, kaldes en yndefuld graf .

Forfatteren til udtrykket "graceful markup" er Solomon Golomb ; Alexander Rosa var den første til at udpege denne klasse af mærkning og introducerede den under navnet -markup i et papir fra 1967 om grafmærkning .  [2] .

En af de vigtigste ubeviste hypoteser i grafteorien er Graceful Tree Conjecture , også kendt som Ringel- Kotzig-formodningen efter Gerhard Ringel og Anton Kotzig , som formulerede den , som siger , at alle træer er yndefulde ... Fra 2017 er formodningen stadig ikke bevist, men på grund af formuleringens enkelhed tiltrak den bred opmærksomhed blandt matematikelskere (som et resultat af, at der dukkede mange forkerte beviser op), Kotzig beskrev på et tidspunkt endda masseforsøg på at bevise det som en "sygdom" [3] .   

Hovedresultater

I det originale papir beviste Rosa, at en Euler-graf med m ≡ 1 (mod 4) eller m ≡ 2 (mod 4) kanter ikke kan være yndefuld. [2] viser den også, at cyklussen C n er yndefuld, hvis og kun hvis n ≡ 0 (mod 4) eller n ≡ 3 (mod 4).

Yndefulde er alle stier , larver , alle hummere med perfekt match [4] , alle hjul , net , ror , tandhjul , alle rektangulære gitter [5] såvel som alle n -dimensionelle hyperkuber [ 6] . Alle simple grafer med 4 eller færre hjørner er yndefulde, de eneste ikke-yndefulde simple grafer på fem spidser er 5 -cyklussen ( femkant ), den komplette K 5 graf og sommerfuglen [7] .

Alle træer med ikke mere end 27 hjørner er yndefulde; dette resultat blev opnået af Aldred og McKay i 1998 ved hjælp af et computerprogram [  5] [8] ; forbedringen af ​​deres tilgang (ved at bruge en anden beregningsmetode) gjorde det muligt i 2010 at vise, at alle træer op til 35 hjørner inklusive er yndefulde - dette er resultatet af Graceful Tree Verification Project ledet af Wenjie Fang [9] .

Noter

  1. ↑ Virginia Vassilevska, "Kodning og yndefuld mærkning af træer." SURF 2001. PostScript Arkiveret 25. september 2006 på Wayback Machine
  2. ↑ 1 2 Rosa, A. Theory of Graphs (Internat. Sympos., Rom, 1966)  (uspecificeret) . - New York: Gordon and Breach, 1967. - S. 349-355 .
  3. ↑ Huang, C.; Kotzig, A.; Rosa, A. Yderligere resultater om  træmærkninger (ubestemt)  // Utilitas Mathematica. - 1982. - T. 21 . - S. 31-48 .
  4. ↑ Morgan, David. Alle hummere med perfekt matchning er yndefulde  //  Bulletin of the Institute of Combinatorics and its Applications. - 2008. - T. 53 . - S. 82-85 .
  5. ↑ 1 2 Gallian, Joseph A. En dynamisk undersøgelse af grafmærkning  // Electronic  Journal of Combinatorics : journal. — 1998; 18. udgave i 2015. - Bd. 5 . - P. Dynamic Survey 6 (elektronisk), i 1. udgave 43 sider, på 18. - 389 sider .
  6. ↑ Kotzig, Anton. Dekomponering af komplette grafer til isomorfe terninger  (engelsk)  // Journal of Combinatorial Theory. Serie B  : tidsskrift. - 1981. - Bd. 31 , nr. 3 . - S. 292-296 . - doi : 10.1016/0095-8956(81)90031-9 .
  7. ↑ Weisstein, Eric W. Yndefuld graf  på Wolfram MathWorld- webstedet .
  8. ↑ Aldred, REL; McKay, Brendan D. Yndefulde og harmoniske mærkninger af træer  (neopr.)  // Bulletin fra Institute of Combinatorics and its Applications. - 1998. - T. 23 . - S. 69-72 .
  9. ↑ Fang, Wenjie. A Computational Approach to the Graceful Tree Conjecture  (engelsk)  : tidsskrift. - 2010. - arXiv : 1003.3045 . Se også Graceful Tree Verification Project

Litteratur