2 svar
136 visningar
dimcic 1 – Fd. Medlem
Postad: 7 okt 2021 21:26 Redigerad: 7 okt 2021 21:31

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:
vVdv=2E
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.

farfarMats 1092
Postad: 7 okt 2021 21:39 Redigerad: 7 okt 2021 21:40

En graf är (väl?) sammanhängande omm det finns en väg mellan varje par av noder

Laguna Online 28597
Postad: 7 okt 2021 21:45

Fundera på en graf med två komponenter. Hur många kanter måste minst fattas jämfört med en komplett graf?

Svara Avbryt
Close