Grafmærkning - Graph labeling

I den matematiske disciplin grafteori er en grafmærkning tildeling af etiketter, traditionelt repræsenteret med heltal , til kanter og/eller hjørner af en graf .

Formelt givet en graf er en toppunktmærkning en funktion af et sæt etiketter; en graf med en sådan funktion defineret kaldes en toppunktsmærket graf . På samme måde er en kantmærkning en funktion af et sæt etiketter. I dette tilfælde kaldes grafen for en kantmærket graf . ${\ displaystyle G = (V, E)}$${\ displaystyle V}$${\ displaystyle E}$

Når kantetiketterne er medlemmer af et ordnet sæt (f.eks. De reelle tal ), kan det kaldes en vægtet graf .

Når det bruges uden kvalifikation, refererer udtrykket mærket graf generelt til en toppunktsmærket graf med alle etiketter adskilte. En sådan graf kan tilsvarende mærkes med de på hinanden følgende heltal , hvor er antallet af hjørner i grafen. For mange applikationer får kanterne eller hjørnerne etiketter, der er meningsfulde i det tilhørende domæne. For eksempel kan kanterne tildeles vægte, der repræsenterer "omkostningerne" ved at krydse mellem de hændende hjørner. ${\ displaystyle \ {1, ..., | V | \}}$${\ displaystyle | V |}$

I ovenstående definition forstås en graf som en begrænset, uorienteret, simpel graf. Imidlertid kan begrebet mærkning anvendes på alle udvidelser og generaliseringer af grafer. For eksempel er det inden for automatteori og formel sprogteori praktisk at overveje mærkede multigrafer , dvs. et par hjørner kan være forbundet med flere mærkede kanter.

Historie

De fleste grafmærkninger sporer deres oprindelse til etiketter, der blev præsenteret af Alexander Rosa i sit papir fra 1967. Rosa identificeret tre typer af mærkninger, som han kaldte α , β - og p -labellings. β -mærkning blev senere omdøbt til "yndefuld" af Solomon Golomb , og navnet har siden været populært.

Særlige tilfælde

Yndefuld mærkning

En yndefuld mærkning; toppunktetiketter er i sort og kantetiketter i rødt

En graf er kendt som yndefuld, når dens hjørner er mærket fra 0 til | E |, størrelsen på grafen, og denne mærkning inducerer en kantmærkning fra 1 til | E |. For enhver kant e er mærket e den positive forskel mellem de to hjørner, der hændes med e . Med andre ord, hvis e forekommer med hjørner mærket i og j , vil e blive mærket | i - j |. Således er en graf G = ( V , E ) yndefuld, hvis og kun hvis der findes en injektion, der inducerer en bijektion fra E til de positive heltal op til | E |.

I sit originale papir beviste Rosa, at alle Eulerian -grafer med størrelse svarende til 1 eller 2 ( mod 4) ikke er yndefulde. Hvorvidt visse graferfamilier er yndefulde eller ej, er et område inden for grafteori under omfattende undersøgelse. Den største ubeviste formodning i grafmærkning er formodentlig Ringel -Kotzig formodning, der antager, at alle træer er yndefulde. Dette er blevet bevist for alle stier , larver og mange andre uendelige familier af træer. Anton Kotzig har selv kaldt bestræbelsen på at bevise formodningen for en "sygdom".

Kant-yndefuld mærkning

En kant-yndefuld mærkning på en simpel graf uden sløjfer eller flere kanter på p- hjørner og q- kanter er en mærkning af kanterne med adskilte heltal i {1,…, q }, således at mærkningen på hjørnerne fremkaldes ved at mærke et toppunkt med summen af ​​de indfaldende kanter taget modulo p tildeler alle værdier fra 0 til p - 1 til hjørnerne. En graf G siges at være "kant-yndefuld", hvis den indrømmer en kant-yndefuld mærkning.

Kant-yndefuld mærkning blev først introduceret af Sheng-Ping Lo i 1985.

En nødvendig betingelse for at en graf er kant-yndefuld er "Lo's tilstand":

$${\ displaystyle q (q+1) = {\ frac {p (p-1)} {2}} \ mod s.}$$

Harmonisk mærkning

En "harmonisk mærkning" på en graf G er en indsprøjtning fra hjørnerne af G til gruppen af heltal modulo k , hvor k er antallet af kanter på G , der inducerer en bijektion mellem kanterne på G og tallene modulo k ved idet kantetiketten for en kant ( x , y ) er summen af ​​etiketterne på de to hjørner x , y (mod k ). En "harmonisk graf" er en, der har en harmonisk mærkning. Ulige cyklusser er harmoniske, ligesom Petersen -grafer . Det formodes, at træer alle er harmoniske, hvis en toppunktetiket må genbruges. Den syv-siders boggraf K _1,7 × K ₂ giver et eksempel på en graf, der ikke er harmonisk.

Graffarvning

En graffarvning er en underklasse af grafmærker. Hvirvelfarvninger tildeler forskellige etiketter til tilstødende hjørner, mens kantfarvninger tildeler forskellige etiketter til tilstødende kanter.

Heldig mærkning

En heldig mærkning af en graf G er en opgave af positive hele tal til knudepunkter af G således at hvis S ( v ) betegner summen af etiketterne på naboerne til v , derpå S er et toppunkt farvning af G . "Lykketal" for G er det mindste k, således at G har en heldig mærkning med heltalene . ${\ displaystyle \ {1, \ ldots, k \}}$

Referencer