23 svar
330 visningar
Nilo 96 – Fd. Medlem
Postad: 8 okt 2021 17:57

Hur beräknar man antalet kanter?

Hej! 

Jag sitter fast med denna uppgift:

En graf har 7 hörn. Graden hos varje hörn i grafen är 3 eller 4. Hur många kanter innehåller grafen om man vet att båda gradtalen finns representerade? 

Jag försökte få fram kanterna genom: 

vVdeg(v) = 2E

Jag tänkte att 7 * 3 = 21/2 = 10,5 kanter och 7 * 4 = 28/2 = 14. Jag tänkte att man kanske skulle addera de, men det blev väldigt fel med vad som stod i facit. I facit står det 11 kanter, men jag förstår absolut inte hur de får fram det. 

Skulle någon kunna hjälpa mig? 

Smutsmunnen 1048
Postad: 8 okt 2021 19:17

Det måste saknas något i uppgiften.

Vad står det ordagrant?

Nilo 96 – Fd. Medlem
Postad: 8 okt 2021 19:34

Det står exakt så ordagrant: 

Smutsmunnen 1048
Postad: 8 okt 2021 19:57

Doesnt make sense då.

Jag kan utan vidare rita grafer som uppfyller kriterierna i uppgiften med såväl 11, 12 som 13 kanter.

Nilo 96 – Fd. Medlem
Postad: 8 okt 2021 19:59

Hur får du till det till 11, 12 och 13?

Smutsmunnen 1048
Postad: 8 okt 2021 20:00

Jag får det inte till det, jag ritar dem.

I vilket fall är det uppenbart att 11,12,13 är de enda möjligheterna eller hur?

Nilo 96 – Fd. Medlem
Postad: 8 okt 2021 20:01

Ja precis, men jag vet inte riktigt hur.

Smutsmunnen 1048
Postad: 8 okt 2021 20:02

Vilka gradtal kan en nod ha?

Vad blir summan av graderna som mest och som minst?

Hur förhåller sig summan av graderna till antalet kanter?

Nilo 96 – Fd. Medlem
Postad: 8 okt 2021 20:08

Om inte jag är helt ute och cyklar: 

1. Gradtalen borde väl vara 3 respektive 4. 

2. Summan bör väl vara 2 x antal kanter (som inte är givet) 

3. Har man summan av graderna till alla noder så ska man kunna räkna fram antalet kanter?

Smutsmunnen 1048
Postad: 8 okt 2021 21:22

Ja och vad kan vi säga om summan?

Nilo 96 – Fd. Medlem
Postad: 8 okt 2021 21:32

Summan måste vara jämn eftersom vi har 2*|E| på andra sidan av summa tecknet?

Nilo 96 – Fd. Medlem
Postad: 8 okt 2021 21:35 Redigerad: 8 okt 2021 21:36

Jag läste på lite om "handshaking" lemma och där står det: 

"antalet noder av udda grad är jämnt"

Innebär det att antalet om vi har gradtalet 3 så finns det ett jämnt antal av de? Alltså 2, 4, 6 och inte mer eftersom vi har 7 noder?

Men jag undrar vad som händer med gradtal 4 isåfall? 

Micimacko 4088
Postad: 8 okt 2021 22:27

Vad skulle hända med gradtal 4?

Nilo 96 – Fd. Medlem
Postad: 8 okt 2021 22:31

Hmm ja det får jag inte till riktigt.

Micimacko 4088
Postad: 8 okt 2021 22:41

Vad är det du inte får till? Hänger inte med på frågan

Nilo 96 – Fd. Medlem
Postad: 8 okt 2021 22:47

Jag tänker 3*2 + 4*5 eller? Så att första fallet blir 26/2= 13?

Micimacko 4088
Postad: 8 okt 2021 22:59 Redigerad: 8 okt 2021 22:59

Ja alla hörn som inte har grad 3 måste ju ha 4.

Nilo 96 – Fd. Medlem
Postad: 8 okt 2021 23:00

Okej nu fick jag till 13, 12 och 11. Men hur kommer det sig att endast 11 står i min facit bok? Ska man välja mellan de på något sätt?

Micimacko 4088
Postad: 8 okt 2021 23:02

Tror det står fel

Nilo 96 – Fd. Medlem
Postad: 8 okt 2021 23:23

Eller hur? För det blir ju olika fall beroende på det jämna antalet av gradtal 3? Så då blir det för 2 => 13, 

4 => 12 och 6 => 11? 

Laguna 30218
Postad: 9 okt 2021 10:01

Som Smutsmunnen sa, det går att rita grafer som uppfyller kraven och som har antingen 11, 12 eller 13 kanter.

Jag gjorde en med 11 kanter, och sedan behöver man bara hitta två noder som har grad 3 och inte är förbundna, och förbinda dem så får man 12 kanter. Det kan man göra en gång till.

Nilo 96 – Fd. Medlem
Postad: 9 okt 2021 10:12

Skulle du säga att alla svar stämmer eller att 11 som svar är rätt? I sådana fall, varför just 11?

Laguna 30218
Postad: 9 okt 2021 10:23

Svaret på frågan som ställs är "11, 12 eller 13".

Nilo 96 – Fd. Medlem
Postad: 9 okt 2021 10:36

Okej, tack! 
Jag fick en funderare. Låt säga att gradtalen skulle vara positiva, t ex 4 och 6 och att grafen har ett jämnt antal noder t ex 8.
Ska man isåfall tänka annorlunda? 

Jag tänker på ”handshaking” lemma? Om det finns ett omvänd sats när det är jämna noder och gradtal?

Svara
Close