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:
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?
Det måste saknas något i uppgiften.
Vad står det ordagrant?
Det står exakt så ordagrant:
Doesnt make sense då.
Jag kan utan vidare rita grafer som uppfyller kriterierna i uppgiften med såväl 11, 12 som 13 kanter.
Hur får du till det till 11, 12 och 13?
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?
Ja precis, men jag vet inte riktigt hur.
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?
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?
Ja och vad kan vi säga om summan?
Summan måste vara jämn eftersom vi har 2*|E| på andra sidan av summa tecknet?
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?
Vad skulle hända med gradtal 4?
Hmm ja det får jag inte till riktigt.
Vad är det du inte får till? Hänger inte med på frågan
Jag tänker 3*2 + 4*5 eller? Så att första fallet blir 26/2= 13?
Ja alla hörn som inte har grad 3 måste ju ha 4.
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?
Tror det står fel
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?
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.
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?
Svaret på frågan som ställs är "11, 12 eller 13".
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?
