Kaavion merkintä

Graafinen merkintä matematiikassa on otsikoiden  osoittamista, jotka perinteisesti esitetään graafin kokonaisluvuilla , reunoilla , pisteillä tai reunoilla ja pisteillä [1] .

Muodollisesti, kun graafi G = ( V , E ) , huippupistenimike on funktio kärkijoukosta V otsikkojoukkoon . Graafia, jossa on tällainen funktio, kutsutaan vertex-merkittyksi graafiksi . Samoin reunojen merkitseminen on funktio reunajoukosta E etikettijoukkoon. Tässä tapauksessa graafia kutsutaan reunamerkittyksi graafiksi .

Siinä tapauksessa, että reunatunnisteet ovat järjestetyn joukon elementtejä (eli reaalilukuja ), nimiöintiä voidaan kutsua painotetuksi graafiksi .

Ellei nimenomaisesti mainita, termi graafimerkintä tarkoittaa yleensä kärkimerkintää, jossa kaikki etiketit ovat erillisiä. Tällainen graafi voidaan vastaavasti merkitä peräkkäisillä kokonaisluvuilla {1, …, | V |}, missä | v | on graafin kärkien lukumäärä [1] . Monissa sovelluksissa reunoille tai pisteille annetaan tarroja, jotka ovat järkeviä vastaavalla alueella. Esimerkiksi reunoille voidaan antaa painotuksia , jotka edustavat kahden vierekkäisen kärjen välisen matkan "kustannuksia" [2] .

Yllä olevassa määritelmässä graafi ymmärretään äärellisenä suuntaamattomana yksinkertaisena graafina. Merkinnän käsite koskee kuitenkin kaikkia graafien laajennuksia ja yleistyksiä. Esimerkiksi automaattien teoriassa ja muodollisten kielten teoriassa katsotaan yleensä nimitetyt multigrafit , eli graafit, joissa pistepari voidaan yhdistää useilla leimatuilla reunoilla [3] .

Historia

Useimmat graafiset merkinnät ovat peräisin merkinnöistä, jotka Alex Rosa esitteli vuoden 1967 artikkelissaan [4] . Rosa tunnisti kolme merkintätyyppiä, joita hän kutsui α-, β- ja ρ-leimoiksi [5] . S. V. Golomb nimesi myöhemmin β- merkin uudelleen gracefuliksi ja tästä nimestä tuli suosittu.

Erikoistilaisuudet

Graceful markup

Graafia kutsutaan siroksi, jos sen kärjet on merkitty numeroilla 0 - | E |, kuvaajan koko, ja tämä merkintä luo reunamerkinnän välillä 1 - | E |. Minkä tahansa reunan e kohdalla reunan e leima on yhtä suuri kuin reunan e kahden kärjen välinen positiivinen ero . Toisin sanoen, jos reuna e osuu kahteen kärkeen , jotka on merkitty i ja j , niin reuna e on merkitty | i − j |. Siten graafi G = ( V , E ) on siro silloin ja vain jos on upotus, joka luo bijektion E :stä positiivisiksi kokonaisluvuiksi | E |.

Rosa osoitti työssään, että kaikki Eulerin syklit , joiden koko on verrattavissa 1:een tai 2:een ( modulo 4), eivät ole kauniita. Mitkä kaavioperheet ovat kauniita, on parhaillaan tiiviin tutkinnan alla. Kenties suurin todistamaton olettamus graafien merkinnöissä on Ringel-Kotzigin arvelu, jonka mukaan kaikki puut ovat siroja. Tämä on todistettu kaikille poluille , toukille ja monille muille äärettömille puuperheille. Kotzig itse kutsui yritystä todistaa olettamus "pahaksi" [6] .

Reunustetut sirot merkinnät

Yksinkertaisten graafien (kuvaajat ilman silmukoita ja useita reunoja) p - kärkisten ja q -reunojen särmäys on reunojen merkitseminen eri kokonaisluvuilla joukosta {1, …, q } siten, että kärkimerkinnän luoma kärkimerkintä on vierekkäisten reunojen summa moduulin p yli , joka antaa pisteisiin kaikki arvot 0 - p - 1 . Graafin G sanotaan olevan reunoista siro , jos se sallii reunojen siron merkitsemisen.

Graceful rib-merkintä oli ensimmäinen, jonka S. Lo otti käyttöön vuonna 1985 [7] .

Välttämätön ehto graafin reunan sulavan merkinnän olemassaololle on Lo-ehto :

Harmoninen merkintä

Graafin G harmoninen merkintä on graafin G kärkijoukon upottaminen kokonaislukujen ryhmään , joiden kongruenssimodulo k , missä k on graafin G reunojen lukumäärä , joka muodostaa bijektion graafin reunojen välille. graafi G ja luvut modulo k valitsemalla kahden kärjen x , y (mod k ) otsikoiden reuna ( x , y ) summat . Harmoninen graafi on kaavio, jolla on harmoninen merkintä. Parittomat jaksot ovat harmonisia kuvaajia, kuten Petersenin graafi . Oletuksena on, että kaikki puut ovat harmonisia graafisia, jos yhtä kärkeä voidaan käyttää uudelleen [8] . Seitsemänsivuinen kirja K 1,7 × K 2 antaa esimerkin epäharmonisesta graafista [9] .

Kaavion väritys

Kaavioiden väritys on graafin merkintöjen alaluokka. Vertex-värjäys määrittää eri tarrat vierekkäisiin kärkipisteisiin, reunaväritys määrittää eri etiketit vierekkäisiin reunoihin.

Lucky markup

G :n onnekas merkintä on positiivisten kokonaislukujen osoittaminen G : n kärkeille siten, että jos S ( v ) on v :n naapuripisteiden nimien summa , niin S on G :n kärkien väritys . Graafin G onnenluku on pienin k , joka graafilla G on onnennimitys kokonaisluvuilla {1, …, k } [10] .

Muistiinpanot

  1. ↑ 1 2 Weisstein, Eric W. Leimattu graafi  (englanniksi) Wolfram MathWorld -verkkosivustolla .
  2. ↑ Calderbank, 1995 , s. 53.
  3. ↑ Kieliteorian kehitys, 2005 .
  4. ↑ Gallian, 1998 .
  5. ↑ Rosa .
  6. ↑ Vietri, 2008 , s. 31–46.
  7. ↑ Lo, 1985 , s. 231-241.
  8. ↑ Guy, 2004 , s. 190-191.
  9. ↑ Gallian, 1998 , s. Dynaaminen kysely 6.
  10. ↑ Czerwiński, Grytczuk, Ẓelazny, 2009 , s. 1078–1081.

Kirjallisuus