Grafmärkning - Graph labeling

I den matematiska disciplinen grafteori är en grafmärkning tilldelning av etiketter, traditionellt representerade av heltal , till kanter och/eller hörn av en graf .

Formellt, med en graf , är en hörnmärkning en funktion av till en uppsättning etiketter; en graf med en sådan funktion definierad kallas en hörnmärkt graf . På samma sätt är en kantmärkning en funktion av en uppsättning etiketter. I detta fall kallas grafen för en kantmärkt graf . ${\ displaystyle G = (V, E)}$${\ displaystyle V}$${\ displaystyle E}$

När kantetiketterna är medlemmar i en ordnad uppsättning (t.ex. de verkliga siffrorna ) kan det kallas en vägd graf .

När det används utan kvalifikation hänvisar termen märkt diagram i allmänhet till en toppunktmärkt graf med alla etiketter distinkta. En sådan graf kan likvärdigt märkas med de på varandra följande heltalen , där är antalet hörn i grafen. För många applikationer ges kanterna eller hörnen etiketter som är meningsfulla i den associerade domänen. Exempelvis kan kanterna tilldelas vikter som representerar "kostnaden" för att korsa mellan de infallande hörnen. ${\ displaystyle \ {1, ..., | V | \}}$${\ displaystyle | V |}$

I ovanstående definition förstås en graf som en begränsad, oriktad enkel graf. Begreppet märkning kan dock tillämpas på alla tillägg och generaliseringar av grafer. Till exempel, i automatteori och formell språkteori är det bekvämt att överväga märkta multigrafer , dvs ett par hörn kan anslutas med flera märkta kanter.

Historia

De flesta grafmärken spårar sitt ursprung till märkningar som presenterades av Alexander Rosa i hans 1967 -papper. Rosa identifierat tre typer av labellings, som han kallade α , β - och p -labellings. β -märkningar döptes senare till "graciösa" av Solomon Golomb , och namnet har varit populärt sedan dess.

Speciella fall

Graciös märkning

En graciös märkning; hörnetiketter är i svart och kantetiketter i rött

Ett diagram är känt som graciöst när dess hörn är märkta från 0 till | E |, grafens storlek och denna märkning inducerar en kantmärkning från 1 till | E |. För vilken kant e som helst är etiketten e den positiva skillnaden mellan de två hörnen som inträffar med e . Med andra ord, om e är infallande med hörn märkta i och j , kommer e att märkas | i - j |. Således är en graf G = ( V , E ) graciös om och bara om det finns en injektion som inducerar en bijektion från E till de positiva heltalen upp till | E |.

I sitt originalpapper bevisade Rosa att alla Eulerian -grafer med storlek motsvarande 1 eller 2 ( mod 4) inte är graciösa. Huruvida vissa familjer av grafer är graciösa eller inte är ett område inom grafteori som omfattas av omfattande studier. Förmodligen är den största obevisade gissningen inom grafmärkning ringel -Kotzig -gissningen, som antar att alla träd är graciösa. Detta har bevisats för alla stigar , larver och många andra oändliga trädfamiljer. Anton Kotzig själv har kallat ansträngningen att bevisa gissningen en "sjukdom".

Kantgraciös märkning

En kant-graciös märkning på en enkel graf utan slingor eller flera kanter på p- hörn och q- kanter är en märkning av kanterna med olika heltal i {1,…, q } så att märkningen på hörnen induceras genom att markera en toppunkt med summan av de infallande kanterna tagna modulo p tilldelar alla värden från 0 till p - 1 till hörnen. En graf G sägs vara "kant-graciös" om den medger en kant-graciös märkning.

Kantgraciösa märkningar introducerades först av Sheng-Ping Lo 1985.

En nödvändig förutsättning för att en graf ska vara kant-graciös är "Lo's skick":

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

Harmonisk märkning

En "harmonisk märkning" på en graf G är en injektion från G -hörnen till gruppen heltal modulo k , där k är antalet kanter på G , som inducerar en bijektion mellan kanterna på G och talen modulo k med ta kantetiketten för en kant ( x , y ) för att vara summan av etiketterna för de två hörnen x , y (mod k ). En "harmonisk graf" är en som har en harmonisk märkning. Udda cykler är harmoniska, liksom Petersen -grafer . Det gissas att träd är alla harmoniska om en hörnetikett får återanvändas. Den sjusidiga bokdiagrammet K _1,7 × K ₂ ger ett exempel på en graf som inte är harmonisk.

Graffärgning

En graffärgning är en underklass med grafmärkning. Vertex -färgningar tilldelar angränsande hörn olika etiketter, medan kantfärgningar tilldelar olika etiketter till angränsande kanter.

Lycklig märkning

En tur märkning av en graf G är en tilldelning av positiva heltal till hörnen i G sådan att om S ( v ) betecknar summan av etiketterna på grannarna av v , då S är en vertex färgning av G . "Lyckantal" för G är det minsta k så att G har en lycklig märkning med heltal . ${\ displaystyle \ {1, \ ldots, k \}}$

Referenser