Antalet delgrafer för en komplett graf
Finns det ett specifikt sätt som man ska utgå ifrån för att hitta alla möjliga delmängder för en komplett graf?
Så leder frågan iaf:
Bestäm antalet delgrafer till den kompletta grafen med hörnmängden
{1, 2, 3, 4}.
Observera att om en kant {i, j} tillhör delgrafen, så måste detsamma
gälla för hörnen i och j. Notera också att exempelvis en graf vars enda
kant är {1, 2} och en graf vars enda kant är {1, 3}, är olika grafer, även
om de innehåller samma hörn.
Om man börjar med att fråga: kan du beskriva alla delgrafer till en komplett graf med fyra hörn?
Hur många hörn kan en delgraf som mest ha? Som minst?
4 som högst och 2 som minst..? stämmer det?
4 som högst stämmer såklart men varför 2 som minst?
Tänkte på att det inte går att bilda en graf med 1 nod(hörn) därför blir det minst 2 för att kunna bilda en delgraf till den ursprungliga grafen med 4 noder (hörn)
En graf behöver inte ha några kanter så det går bra med en graf med 1 nod.
I vissa sammanhang tillåter man även en graf med 0 hörn, noll-grafen, men den kan vi strunta i och konstatera att en delgraf har från 1 till 4 hörn.
Finns det några andra restriktioner? Eller är vilken graf som helst med 1 till 4 hörn en delgraf till den kompletta grafen med 4 hörn?
Att man inte ska tillägga några extra kanter som inte finns med i den ursprungliga grafen, om det va det du försökte komma till?
Men finns det verkligen kanter som man skulle kunna lägga till den ursprungliga grafen?
Det vi har är ju den kompletta grafen, ska inte den innehålla alla kanter?
Ja men det har du rätt i, blev bara lite förvirrad. Men jag har iaf nu ritat upp den kompletta grafen så jag kan tydligt se den framför mig
Ah men vad bra.
Så slutsatsen bör vara att det inte finns några andra restriktioner.
Så länge hörnmängden är en icke-tom delmängd till {1,2,3,4} så är grafen en delgraf till den kompletta grafen på {1,2,3,4}.
Nu får vi fyra fall:
Delgrafen har ett hörn: hur många olika grafer går det att bilda på ett hörn, säg på mängden {1}?
Delgrafen har två hörn: hur många olika grafer går det att bilda på två hörn, säg på mängden {1,2}?
Och samma fråga för 3 och 4.
Ta de frågorna först även om det tillkommer ytterligare en komplikation, nämligen på hur många sätt vi kan välja en hörnmängd av en viss storlek.
Yes nu hänger jag med!
Men jag har lite svårt med detta.. visst bör man använda sig av n över 4 metoden? alltså om man ska först räkna på antal mängder med 1 hörn så tar man 1 över 4 då vi har 4 hörn o välja på. Sen gör jag samma med dina andra frågeställningar. Sen summerar jag ihop resultatet
Är det så jag ska göra?
Ja det ger ju antal sätt att väla hörnmängden.
Men sen om hörnmängden är {1,2} finns ju också två olika möjligheter.
Nämligen en graf som består av två isolerade hörn och en graf som består av två hörn med en kant mellan sig.
Så den första frågan är: givet en hörnmängd med k element, hur många olika grafer finns på den hörnmängden?
Förlåt jag hänger inte med nu, denna moment är inte min starka sida. Kan du förklara lite mer hur jag ska tänka och gå tillväga? det uppskattas så mycket!
Behöver fortfarande hjälp, om någon är villig att hjälpa :)
