18 svar
165 visningar
Soderstrom är nöjd med hjälpen
Soderstrom 1933
Postad: 11 jan 15:43 Redigerad: 11 jan 15:44

Grafteori - Bijections and colourings

Fråga:

Consider the complete graph KnK_{n} with vertices labelled (1,...,n){(1, ..., n)}. Show that for any finite simple graph GG, there is a bijection between proper n-colourings of GG, and graph homomorphisms GKnG \to K_{n}

Sitter helt fast och skulle gärna behöva hjälp!

Soderstrom 1933
Postad: 12 jan 16:02

bump

Jvpm 75
Postad: 13 jan 11:45 Redigerad: 13 jan 11:56

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 Kn ska vara isomorfa måste de givetvis ha samma antal noder. Alltså kan inte G ha fler än n noder. Så vi har alltså Gn vilken enligt uppgiften har en "proper colouring" med n färger. Men enligt 3) är ju detta samma sak som en komplett graf. Dvs GKn är en isomorfi.

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

Laguna Online 17492
Postad: 13 jan 12:12

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

Jvpm 75
Postad: 13 jan 12:53

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.

Smutsmunnen 653
Postad: 13 jan 13:41

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.

Soderstrom 1933
Postad: 13 jan 14:46

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 75
Postad: 13 jan 14:59
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.

Smutsmunnen 653
Postad: 13 jan 14:59

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.

Laguna Online 17492
Postad: 13 jan 15:44
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.

Jvpm 75
Postad: 13 jan 16:58
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 GKn". Jag tror jag har missförstått allt. Jag tänkte att bijektionen var mellan G och Kn men så står det ju faktiskt inte.

Smutsmunnen 653
Postad: 13 jan 17:15 Redigerad: 13 jan 17:15

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

Laguna Online 17492
Postad: 13 jan 18:23

"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.

Smutsmunnen 653
Postad: 13 jan 18:44

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.

Jvpm 75
Postad: 13 jan 21:11
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 Kn komplett och därför måste man använda alla n färger.

Smutsmunnen 653
Postad: 13 jan 21:18
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 Kn 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. 

Jvpm 75
Postad: 13 jan 22:13

Aah, det börjar så smått klarna, tror jag... Så Kn ä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 Kn, 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 Kn. Blev det rätt nu?

Smutsmunnen 653
Postad: 14 jan 08:52
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 Kn. 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.

Jvpm 75
Postad: 14 jan 19:44

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

Svara Avbryt
Close