Markup grafic

Etichetarea graficelor în matematică  este alocarea de etichete, care sunt reprezentate în mod tradițional prin numere întregi , muchii , vârfuri sau muchii și vârfuri ale unui grafic [1] .

În mod formal, dat un grafic G = ( V , E ) , o etichetă de vârf este o funcție de la mulțimea de vârfuri V la mulțimea de etichete . Un grafic cu o astfel de funcție se numește un vârf etichetat graf . În mod similar, etichetarea muchiilor este o funcție de la setul de muchii E la setul de etichete. În acest caz, graficul se numește graf etichetat muchie .

În cazul în care etichetele marginilor sunt elemente ale unui set ordonat (adică numere reale ), etichetarea poate fi numită un grafic ponderat .

Cu excepția cazului în care este specificat în mod explicit, termenul etichetare grafic înseamnă de obicei etichetarea vârfurilor unde toate etichetele sunt distincte. Un astfel de grafic poate fi etichetat în mod echivalent prin numere întregi consecutive {1, …, | V |}, unde | v | este numărul de vârfuri ale graficului [1] . Pentru multe aplicații, muchiile sau vârfurile primesc etichete care au sens în zona corespunzătoare. De exemplu, muchiilor li se pot atribui ponderi care reprezintă „costul” călătoriei între două vârfuri adiacente [2] .

În definiția de mai sus, un graf este înțeles ca un graf simplu finit nedirecționat. Totuși, noțiunea de marcaj se aplică tuturor extensiilor și generalizărilor graficelor. De exemplu, în teoria automatelor și în teoria limbajelor formale sunt considerate de obicei multigrafe etichetate , adică grafice în care o pereche de vârfuri poate fi conectată prin mai multe muchii etichetate [3] .

Istorie

Majoritatea etichetărilor grafice își au originea în etichetările introduse de Alex Rosa în lucrarea sa din 1967 [4] . Rosa a identificat trei tipuri de etichetare, pe care le-a numit etichete α-, β- și ρ-labels [5] . β-markup a fost mai târziu redenumit de S. V. Golomb în grațios și acest nume a devenit popular.

Ocazii speciale

Markup grațios

Un grafic se numește grațios dacă vârfurile sale sunt etichetate cu numere de la 0 la | E |, dimensiunea graficului, iar această etichetare generează o etichetare a marginilor de la 1 la | E |. Pentru orice muchie e , eticheta muchiei e este egală cu diferența pozitivă dintre cele două vârfuri ale muchiei e . Cu alte cuvinte, dacă muchia e este incidentă la două vârfuri etichetate i și j , atunci muchia e este etichetată | i − j |. Astfel, un grafic G = ( V , E ) este grațios dacă și numai dacă există o încorporare care generează o bijecție de la E în numere întregi pozitive până la | E |.

În lucrarea sa, Rosa a demonstrat că toate ciclurile Euler de mărime comparabilă cu 1 sau 2 ( modulo 4) nu sunt grațioase. Familiile de grafice care sunt grațioase sunt în prezent sub investigație intensă. Poate cea mai mare presupunere nedovedită în etichetarea graficelor este conjectura Ringel-Kotzig, care afirmă că toți copacii sunt grațioși. Acest lucru a fost dovedit pentru toate potecile , omizile și multe alte familii infinite de copaci. Kotzig însuși a numit încercarea de a demonstra conjectura „rău” [6] .

Marcaje grațioase tivite

Etichetarea grațioasă pe margine a graficelor simple (grafice fără bucle și muchii multiple) cu p vârfuri și q muchii este etichetarea muchiilor prin diferite numere întregi din mulțimea {1, …, q }, astfel încât etichetarea vârfurilor generată de etichetarea vârfurilor ca suma muchiilor adiacente peste modulul p , care atribuie toate valorile de la 0 la p - 1 vârfurilor. Se spune că un grafic G are margini grațioase dacă permite etichetarea cu muchii grațioase.

Marcajul grațios al coastelor a fost primul care a fost introdus de S. Lo în 1985 [7] .

O condiție necesară pentru existența unei etichete grațioase de margine pentru un grafic este condiția Lo :

Markup armonios

O etichetare armonică a unui grafic G este o încorporare a mulțimii de vârfuri ale unui grafic G într- un grup de numere întregi de congruență modulo k , unde k este numărul de muchii ale graficului G , care generează o bijecție între muchiile graficului G. graficul G și numerele modulo k prin alegerea muchiei ( x , y ) sume ale etichetelor a două vârfuri x , y (mod k ). Un grafic armonic este un grafic care are o etichetare armonioasă. Ciclurile impare sunt grafice armonice, la fel ca și graficul Petersen . Există o presupunere că toți arborii sunt grafice armonice dacă un vârf este permis să fie reutilizat [8] . Cartea cu șapte pagini K 1,7 × K 2 oferă un exemplu de grafic nearmonic [9] .

Colorarea graficelor

Colorarea graficelor este o subclasă de marcare a graficelor. Colorarea vârfurilor atribuie etichete diferite vârfurilor adiacente, colorarea marginilor atribuie etichete diferite muchiilor adiacente.

Markup norocos

O etichetare norocoasă a lui G este alocarea de numere întregi pozitive la vârfurile lui G în așa fel încât dacă S ( v ) este suma etichetelor vârfurilor învecinate ale lui v , atunci S este colorarea vârfurilor lui G . Numărul norocos al unui grafic G este cel mai mic k pe care graficul G are o etichetare norocoasă cu numere întregi {1, …, k } [10] .

Note

  1. ↑ 1 2 Weisstein, Eric W. Grafic etichetat  (engleză) pe site-ul web Wolfram MathWorld .
  2. ↑ Calderbank, 1995 , p. 53.
  3. ↑ Evoluții în teoria limbajului, 2005 .
  4. ↑ Gallian, 1998 .
  5. ↑ Rosa .
  6. ↑ Vietri, 2008 , p. 31–46.
  7. ↑ Lo, 1985 , p. 231–241.
  8. ↑ Guy, 2004 , p. 190–191.
  9. ↑ Gallian, 1998 , p. Sondaj dinamic 6.
  10. ↑ Czerwiński, Grytczuk, Ẓelazny, 2009 , p. 1078–1081.

Literatură