Grafteori - Bijections and colourings (Matematik/Universitet)

bump

Jag är kanske helt ute och cyklar på nån Eulerstig men jag spånar i varje fall så här, kanske det kan vara till någon hjälp:

Är osäker på om homomorfi är samma sak som isomorfi men en bijektion mellan två grafer är i varje fall isomorf om egenskaperna hos de två graferna bevaras under bijektionen.

När man ska visa något brukar det vara bra att först skriva ner några definitioner:

1) Graffärgning: Noder som är grannar ges olika färger.

2) Kromatiska talet: det minsta heltal $k$ så att grafen $G$ har en graffärgning med $k$ färger ( ${}_{χ}G$ ).

3) Komplett graf: det kromatiska talet är samma som antalet noder i grafen dvs ${}_{χ}G = |V|$ .

4) Simpel graf: Vet ej, men antar att den inte per definition behöver uppfylla kravet som en komplett graf har.

När de i frågan skriver "proper n-colourings of $G$ " så tolkar jag det som att de menar att man använder det minsta möjliga antal färger för att utföra graffärgningen och att detta resulterar i användandet av $n$ färger. Enligt 1) ovan betyder det i så fall att $G$ har minst $n$ noder.

För att de två graferna $G$ och $K_{n}$ ska vara isomorfa måste de givetvis ha samma antal noder. Alltså kan inte $G$ ha fler än $n$ noder. Så vi har alltså $G_{n}$ vilken enligt uppgiften har en "proper colouring" med $n$ färger. Men enligt 3) är ju detta samma sak som en komplett graf. Dvs $G \to K_{n}$ är en isomorfi.

Vet dock inte om detta håller i rätten i form av en tentasal...

En isomorfi är en 1-1-avbildning. En homomorfi kan avbilda flera element på samma element.

Ok, då får vi stryka sista delen av min argumentation. $G$ kan ha fler än $n$ noder eftersom vi inte kräver isomorfi utan endast homomorfi. Om jag förstått det rätt.

Det här är en trivial uppgift så det känns som att det är något i begreppen du inte förstår.

Först och främst: givet två grafer G och H med hörnmängder V och W så är en homomorfism en funktion från V till W sådan att grannar i V avbildas på grannar i W.

Observera att om H är en komplett graf så är alla noder i W grannar med alla noder i W utom sig själv. Det innebär att om H är en komplett graf så är en funktion från G till H en homomorfism om och endast om den inte avbildar grannar i V på samma element i W.

Antag nu att f är en funktion V till W där W är en komplett graf med n hörn som i problemet. Pre-imagen av f är då en partition av V, som för alla funktioner, i mängder V_1, V_2,...,V_n, där alla hörn i V_i alltså avbildas på hörn i K_n. Och f är en homomorfism om och endast om inget V_i innehåller två grannar. Så V_1, V_2,...,V_n motsvarar precis en färgläggning, nämligen måla V_i med färg i.

Asså uppgiften är inte det svåraste men begreppen och beskrivningen i uppgift texten förvirrade mig så jäkla mycket. Men nu är det tydligare tack vare förklaringarna.

Tack så mycket:))

Jvpm skrev:
Ok, då får vi stryka sista delen av min argumentation. $G$ kan ha fler än $n$ noder eftersom vi inte kräver isomorfi utan endast homomorfi. Om jag förstått det rätt.

Jag ändrar mig här: En homoformi kallas isomorf om det råder en bijektion, precis som Laguna skriver. Uppgiften förutsätter en bijektion. Alltså en isomorfism.

Det var inte meningen att få någon att känna sig dum när jag skrev att det är en trivial uppgift, poängen är precis att det är en uppgift som i princip går ut på att förstå begreppen.

Jvpm skrev:
Jvpm skrev:
Ok, då får vi stryka sista delen av min argumentation. $G$ kan ha fler än $n$ noder eftersom vi inte kräver isomorfi utan endast homomorfi. Om jag förstått det rätt.

Jag ändrar mig här: En homoformi kallas isomorf om det råder en bijektion, precis som Laguna skriver. Uppgiften förutsätter en bijektion. Alltså en isomorfism.

Nej, G kan ju ha fler än n noder.

Laguna skrev:
Jvpm skrev:
Jvpm skrev:
Ok, då får vi stryka sista delen av min argumentation. $G$ kan ha fler än $n$ noder eftersom vi inte kräver isomorfi utan endast homomorfi. Om jag förstått det rätt.

Jag ändrar mig här: En homoformi kallas isomorf om det råder en bijektion, precis som Laguna skriver. Uppgiften förutsätter en bijektion. Alltså en isomorfism.

Nej, G kan ju ha fler än n noder.

Hmm, det är något jag inte förstår här. Smutsmunnen skrev också att "Pre-imagen av f är då en partition av V". Så det du säger och det Smutsmunnen säger går hand i hand.

Uppgiften efterfrågar en bijektion mellan "proper n-colouring of $G$ ", vad som nu menas med det, och "graph homomorphisms $G \to K_{n}$ ". Jag tror jag har missförstått allt. Jag tänkte att bijektionen var mellan $G$ och $K_{n}$ men så står det ju faktiskt inte.

Ja Jvpm, bijektionen är mellan å ena sidan mängden av färgläggningar å andra sidan homomorfierna.

"Proper" betyder tydligen att två grannoder inte har samma färg, och tydligen är det det man menar även om man inte säger "proper". Däremot behöver det inte vara så att det krävs n färger. Det kan vara så att man inte ens behöver använda n färger, men jag är osäker på det.

Använd definitionen i din lärobok.

Man behöver absolut inte använda alla n färger för att det ska vara en n-coloring och omvänt behöver inte en homomorfism vara surjektiv.

Smutsmunnen skrev:
Man behöver absolut inte använda alla n färger för att det ska vara en n-coloring och omvänt behöver inte en homomorfism vara surjektiv.

Att en homomorfi inte behöver vara surjektiv har jag läst mig till på Wikipedia, men kan du utveckla vad du menar med att man inte behöver använda alla n-färgerna för att det ska vara en n-coloring? Att man inte behöver använda alla n färger för en graffärgning (vertex coloring) förstår jag. Det kan ju finnas olika färgningar där en av dem är den med minst antal färger. Är det det du menar?

För i det här fallet är ju $K_{n}$ komplett och därför måste man använda alla n färger.

Jvpm skrev:
Smutsmunnen skrev:
Man behöver absolut inte använda alla n färger för att det ska vara en n-coloring och omvänt behöver inte en homomorfism vara surjektiv.

Att en homomorfi inte behöver vara surjektiv har jag läst mig till på Wikipedia, men kan du utveckla vad du menar med att man inte behöver använda alla n-färgerna för att det ska vara en n-coloring? Att man inte behöver använda alla n färger för en graffärgning (vertex coloring) förstår jag. Det kan ju finnas olika färgningar där en av dem är den med minst antal färger. Är det det du menar?

För i det här fallet är ju $K_{n}$ komplett och därför måste man använda alla n färger.

Fast det är inte K_n man färglägger:

a bijection between proper n-colourings of G, and graph homomorphisms G→Kn.

Aah, det börjar så smått klarna, tror jag... Så $K_{n}$ är komplett (dvs alla noder är grannar med alla andra vilket är ekvivalent med att om den skulle graffärgas så skulle det ske med $n$ färger). Vidare har vi en homomorfi mellan $G$ och $K_{n}$ , dvs strukturen av grannar bevaras mellan de två graferna. Därmed kan vi sluta oss till att vi har en bijektion mellan en graffärgning av $G$ med $n$ färger och homomorfin med $K_{n}$ . Blev det rätt nu?

Jvpm skrev:
Därmed kan vi sluta oss till att vi har en bijektion mellan en graffärgning av $G$ med $n$ färger och homomorfin med $K_{n}$ . Blev det rätt nu?

Nä vi har en bijektion mellan mängden av graffärgningar av G med n färger och mängden av homomorfier mellan G och K_n.

Det är kanske bäst att ge lite exempel. Jag tar triviala exempel.

Först låt G vara grafen som består av en enda nod.

G kan då färgläggas på n sätt med n färger. Alltså vi väljer en av de n färgerna för den enda noden.

Å andra sidan: låt v vara den enda noden i G och låt 1,2,3...,n vara noderna i K_n. Då finns det precis n homomorfier mellan G och K_n, nämligen varje funktion f(v)= i för i=1,2,3,...,n.

Så det finns lika många många färgläggningar som homomorfier.

Andra exemplet: G=K_(n+1).

Då är det omöjligt att färglägga G med n färger, det vill säga det finns 0 färgläggningar.

Å andra sidan finns heller inga homomorfier från K_(n+1) till K_(n), minst två av hörnen i K_(n+1) måste avbildas på samma hörn i K_n och då avbildas två grannar på icke-grannar.

Ok, då förstår jag äntligen. Stort tack för ditt tålamod Smutsmunnen! (Och den pedagogiska förklaringen såklart!)