2
svar
159
visningar
Grafer, Diskret matematik
Fråga:
Visa att en enkel ögelfri graf med 11 hörn och mer än 45 bågar är sammanhängande.
Känns som en enkel fråga att lösa, men är lite vilse.
Tänkte mig först att jag kanske behöver räkna ut gradtalet enligt denna formeln:
Där gradtalet är 2 45 (antalet bågar) = 90
Och sedan därifrån kanske räkna ut antalet kanter, eller enligt någon definition avgöra om en graf är sammanhängande med infon vi nu fått ut.
Uppskattar all hjälp.
En graf är (väl?) sammanhängande omm det finns en väg mellan varje par av noder
Fundera på en graf med två komponenter. Hur många kanter måste minst fattas jämfört med en komplett graf?