36 svar
150 visningar
sven999 54 – Fd. Medlem
Postad: 14 okt 2020 11:22

stjärngrafer

Skulle behöva lite hjälp med a)
Jag kom fram till att nästa (6,3 ) blir en stjärna med 2 sammanhängande komponenter, men kan man säga att den är sammanhängande om den har 2 sammanhängande komponenter? och hur får man (6,4) och (6,5)?

Smutsmunnen 1050
Postad: 14 okt 2020 12:06

En graf som har två komponenter är inte sammanhängade. En graf är sammanhängande om den har exakt en komponent.

Det bör inte vara svårare att konstruera (6,4) och (6,5) än (6,2) och (6,3). Det är väl bara att rita.

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 12:10

ok! men visst borde det stämma att 6,2 inte är sammanhängande graf, medan resten är det med en sammanhängande komponent för 6,3, 6,4, och 6,5?

Smutsmunnen 1050
Postad: 14 okt 2020 12:10

Men för övrigt tror jag inte att det stämmer att (6,3) har två komponenter, den bör ha 3. Vore bra att se vad du ritat.

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 12:15
Smutsmunnen skrev:

Men för övrigt tror jag inte att det stämmer att (6,3) har två komponenter, den bör ha 3. Vore bra att se vad du ritat.

såg att jag skrev fel menade 6,2. :)
men hur hade du löst b uppgiften?

Smutsmunnen 1050
Postad: 14 okt 2020 12:15

Nej (6,2), (6,3),(6,4) som uppgift a gäller så ska ingen vara sammanhängande.

(6,5) är däremot sammanhängande liksom (6,1) men uppgift a handlar ju inte om dem, däremot kanske du börjar se ett mönster inför b-uppgiften.

Förövrigt är problemet lite skevt formulerat. Av definitionen följer att nodmängden innehåller n+1 element, så grafen skulle innehålla n+1 noder, men av exemplet så tycks det röra sig om n noder. Vi ska nog förstå Z_n som innehållande 0 till n-1.

Smutsmunnen 1050
Postad: 14 okt 2020 12:17
sven999 skrev:
Smutsmunnen skrev:

Men för övrigt tror jag inte att det stämmer att (6,3) har två komponenter, den bör ha 3. Vore bra att se vad du ritat.

såg att jag skrev fel menade 6,2. :)
men hur hade du löst b uppgiften?

Om du löser 6a) bör du få en ganska tydlig hypotes inför 6b.

Sedan hur man bevisar den kan vi ta när du formulerat hypotesen.

Smutsmunnen 1050
Postad: 14 okt 2020 12:19

Vad är det för kurs förresten? Vilken termin matte? Första, andra? 

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 12:39

nice! ska testa lite! Det är diskret matte första terminen

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 12:44

har jag tänkt rätt här?

Smutsmunnen 1050
Postad: 14 okt 2020 13:20

Nej (6,3) har du fått fel,

I (6,3)

Det går en kant från 0 till 0+3=3 och från 3 en till 3+3=0

en kant från 1 till 1+3=4 och en från 4 till 4+3=1.

en kant från 2 till 2+3=5 och en från 5 till 5+3=2.

Grafen innehåller alltså bara 3 kanter.

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 13:40
Smutsmunnen skrev:

Nej (6,3) har du fått fel,

I (6,3)

Det går en kant från 0 till 0+3=3 och från 3 en till 3+3=0

en kant från 1 till 1+3=4 och en från 4 till 4+3=1.

en kant från 2 till 2+3=5 och en från 5 till 5+3=2.

Grafen innehåller alltså bara 3 kanter.

ok! nu fattar jag så det blir
6,2 = 2 sammanhängande komponenter
6,3 = 3 sammanhängande komponenter

6,4 = 2 ammanhängande komponenter
6,5 = 1 sammanhängande komponent

men på b, 1<m<n ger sammanhängande grafer
verkar som att n-m ger antalet sammanhängande komponenter för vissa men inte alla? hur hade du tänkt?

Smutsmunnen 1050
Postad: 14 okt 2020 13:46

Nä sambandet är inte antal komponenter = n-m.

I en viss graf (n,m) är alla komponenter lika stora?

Om alla komponenter är lika stora så har vi (antalet komponenter) * (storleken på komponenterna)=n.

Så antalet komponenter delar antalet hörn, n.

Så om du tittar på dina resultat för (6,m) kan du lista ut vilken delare det rör sig om? 

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 13:46
sven999 skrev:
Smutsmunnen skrev:

Nej (6,3) har du fått fel,

I (6,3)

Det går en kant från 0 till 0+3=3 och från 3 en till 3+3=0

en kant från 1 till 1+3=4 och en från 4 till 4+3=1.

en kant från 2 till 2+3=5 och en från 5 till 5+3=2.

Grafen innehåller alltså bara 3 kanter.

ok! nu fattar jag så det blir
6,2 = 2 sammanhängande komponenter
6,3 = 3 sammanhängande komponenter

6,4 = 2 ammanhängande komponenter
6,5 = 1 sammanhängande komponent

men på b, 1<m<n ger sammanhängande grafer
verkar som att n-m ger antalet sammanhängande komponenter för vissa men inte alla? hur hade du tänkt?

eller är b att dem blir sammanhängande när m<=3?

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 13:54

nja, vet inte riktigt storleken, men menar du t.ex:
6,2 har 2 komponenter, storleken på hörnen är (6+9), då får vi 2*(6+9)?

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 14:09

och på fråga a så blir det väll ingen sammanhängande graf eftersom alla har fler än 1 komponenter?

Smutsmunnen 1050
Postad: 14 okt 2020 14:09

Nej (6,2) har 2 komponenter, båda innehåller 3 hörn.  Så 2*3=6

På samma sätt har (6,3) 3 komponenter, alla tre innehåller 2 hörn. Så 3*2=6.

Så antal komponenter är en delare till antal hörn (=n).

Till exempel om vi tittar på (7,m) utan att rita upp den. Om vi antar att alla komponenter är lika stora, så vet vi att antalet komponenter delar 7, så vi vet att det blir 1 komponent eller 7 komponenter.

Återstår då bara fråga: hur avgöra från m vilken delare till 7? 

Smutsmunnen 1050
Postad: 14 okt 2020 14:13
sven999 skrev:

och på fråga a så blir det väll ingen sammanhängande graf eftersom alla har fler än 1 komponenter?

Det stämmer.

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 14:15
Smutsmunnen skrev:

Nej (6,2) har 2 komponenter, båda innehåller 3 hörn.  Så 2*3=6

På samma sätt har (6,3) 3 komponenter, alla tre innehåller 2 hörn. Så 3*2=6.

Så antal komponenter är en delare till antal hörn (=n).

Till exempel om vi tittar på (7,m) utan att rita upp den. Om vi antar att alla komponenter är lika stora, så vet vi att antalet komponenter delar 7, så vi vet att det blir 1 komponent eller 7 komponenter.

Återstår då bara fråga: hur avgöra från m vilken delare till 7? 

är det beroende på storleken på m? annars vet jag inte riktigt 

Smutsmunnen 1050
Postad: 14 okt 2020 14:18

Det är klart att det beror av m.

Om du tittar på dina resultat

(6,2)-> 2 komponenter

(6,3)-> 3 komponenter

(6,4)-> 2 komponenter

(6,5)-> 1 komponent.

Finns det någon känd delarfunktion som ni pratat om på kursen? Som kanske skulle kunna beskriva antalet komponenter?

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 14:24
Smutsmunnen skrev:

Det är klart att det beror av m.

Om du tittar på dina resultat

(6,2)-> 2 komponenter

(6,3)-> 3 komponenter

(6,4)-> 2 komponenter

(6,5)-> 1 komponent.

Finns det någon känd delarfunktion som ni pratat om på kursen? Som kanske skulle kunna beskriva antalet komponenter?

Inte vad jag kommer på, på rak arm

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 14:26
sven999 skrev:
Smutsmunnen skrev:

Det är klart att det beror av m.

Om du tittar på dina resultat

(6,2)-> 2 komponenter

(6,3)-> 3 komponenter

(6,4)-> 2 komponenter

(6,5)-> 1 komponent.

Finns det någon känd delarfunktion som ni pratat om på kursen? Som kanske skulle kunna beskriva antalet komponenter?

Inte vad jag kommer på, på rak arm

vill ju säga n/m men det verkar inte funka?

Smutsmunnen 1050
Postad: 14 okt 2020 14:28

Det är största gemensamma delaren SGD(n,m).

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 14:30

aha!!!! coolt :D 

Smutsmunnen 1050
Postad: 14 okt 2020 14:31

Så nu har du en hypotes för b)-uppgiften.

Bara bevisa den.

Smutsmunnen 1050
Postad: 14 okt 2020 14:42

Hint för bevis:

Antag att du börjar i nod nummer r. Därifrån går du till r+m, därifrån till r+2m, därifrån till r+3m osv. Hur lång tid innan du kommer tillbaka dit du började? Antal steg är storleken på varje komponent. När du vet storleken på varje komponent är det lätt att beräkna antal komponenter.

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 15:27

Nice! jag löste den :) 
Hur hade du löst denna?

tänker jag rätt om A har 2 och C har 4 sätt

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 15:32
sven999 skrev:

Nice! jag löste den :) 
Hur hade du löst denna?

tänker jag rätt om A har 2 och C har 4 sätt

b och c borde ha 5, och e 4 st?

Smutsmunnen 1050
Postad: 14 okt 2020 15:55

På b) exempelvis har du helt fel. På c) med. På e) är det inte heller 4.

Försök att tänka utifrån definitionen av automorfism.

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 16:11
Smutsmunnen skrev:

På b) exempelvis har du helt fel. På c) med. På e) är det inte heller 4.

Försök att tänka utifrån definitionen av automorfism.

Har du något tips på hur man ska tänka?

Smutsmunnen 1050
Postad: 14 okt 2020 18:08
sven999 skrev:
Smutsmunnen skrev:

På b) exempelvis har du helt fel. På c) med. På e) är det inte heller 4.

Försök att tänka utifrån definitionen av automorfism.

Har du något tips på hur man ska tänka?

Börja med b. Den är på sitt sätt lättast. Men den går inte att lösa genom att titta på grafen, man är tvungen att tänka på vad en isomorfi är.

Sedan måste man ha lite olika tricks för olika grafer. Finns ingen enkel, genrell metod för att räkna automorfier.

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 18:24

ok, skulle du kunna ge ett exeempel så jag vet hur jag ska tänka på resten?

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 18:37
Smutsmunnen skrev:
sven999 skrev:
Smutsmunnen skrev:

På b) exempelvis har du helt fel. På c) med. På e) är det inte heller 4.

Försök att tänka utifrån definitionen av automorfism.

Har du något tips på hur man ska tänka?

Börja med b. Den är på sitt sätt lättast. Men den går inte att lösa genom att titta på grafen, man är tvungen att tänka på vad en isomorfi är.

Sedan måste man ha lite olika tricks för olika grafer. Finns ingen enkel, genrell metod för att räkna automorfier.

är det 10 på d, 20 på b?

Smutsmunnen 1050
Postad: 14 okt 2020 18:38
sven999 skrev:
Smutsmunnen skrev:
sven999 skrev:
Smutsmunnen skrev:

På b) exempelvis har du helt fel. På c) med. På e) är det inte heller 4.

Försök att tänka utifrån definitionen av automorfism.

Har du något tips på hur man ska tänka?

Börja med b. Den är på sitt sätt lättast. Men den går inte att lösa genom att titta på grafen, man är tvungen att tänka på vad en isomorfi är.

Sedan måste man ha lite olika tricks för olika grafer. Finns ingen enkel, genrell metod för att räkna automorfier.

är det 10 på d, 20 på b?

10 på d stämmer, 20 på b nej.

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 18:44
Smutsmunnen skrev:
sven999 skrev:
Smutsmunnen skrev:
sven999 skrev:
Smutsmunnen skrev:

På b) exempelvis har du helt fel. På c) med. På e) är det inte heller 4.

Försök att tänka utifrån definitionen av automorfism.

Har du något tips på hur man ska tänka?

Börja med b. Den är på sitt sätt lättast. Men den går inte att lösa genom att titta på grafen, man är tvungen att tänka på vad en isomorfi är.

Sedan måste man ha lite olika tricks för olika grafer. Finns ingen enkel, genrell metod för att räkna automorfier.

är det 10 på d, 20 på b?

10 på d stämmer, 20 på b nej.

okej! har du något tips på hur jag ska tänka på b c, e?

sven999 54 – Fd. Medlem
Postad: 14 okt 2020 18:48
Smutsmunnen skrev:
sven999 skrev:
Smutsmunnen skrev:
sven999 skrev:
Smutsmunnen skrev:

På b) exempelvis har du helt fel. På c) med. På e) är det inte heller 4.

Försök att tänka utifrån definitionen av automorfism.

Har du något tips på hur man ska tänka?

Börja med b. Den är på sitt sätt lättast. Men den går inte att lösa genom att titta på grafen, man är tvungen att tänka på vad en isomorfi är.

Sedan måste man ha lite olika tricks för olika grafer. Finns ingen enkel, genrell metod för att räkna automorfier.

är det 10 på d, 20 på b?

10 på d stämmer, 20 på b nej.

borde inte b vara 5!   ?

Smutsmunnen 1050
Postad: 15 okt 2020 10:06
sven999 skrev:
Smutsmunnen skrev:
sven999 skrev:
Smutsmunnen skrev:
sven999 skrev:
Smutsmunnen skrev:

På b) exempelvis har du helt fel. På c) med. På e) är det inte heller 4.

Försök att tänka utifrån definitionen av automorfism.

Har du något tips på hur man ska tänka?

Börja med b. Den är på sitt sätt lättast. Men den går inte att lösa genom att titta på grafen, man är tvungen att tänka på vad en isomorfi är.

Sedan måste man ha lite olika tricks för olika grafer. Finns ingen enkel, genrell metod för att räkna automorfier.

är det 10 på d, 20 på b?

10 på d stämmer, 20 på b nej.

borde inte b vara 5!   ?

Ja!

Svara
Close