Noen som vet hvordan man kan regne ut antall noder (vertices) når man bare kjenner til f.eks 10 kanter der 2 noder er av grad 4 og resten 3, eller G er regular (vanlig?) med 15 kanter?
Og f.eks.. motsatt, regne ut antall kanter?
Merker at tegnemetoden blir litt tungvindt i enkelte oppgaver:b
Regular graph
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
Solar Plexsus
- Over-Guru
- Innlegg: 1685
- Registrert: 03/10-2005 12:09
Legger du alle gradtallene til samtlige noder i en graf, vil summen være det dobbelte av antall kanter i grafen. Følgelig er det så en graf som består av 10 kanter og n noder der 2 er av grad 4 og resten (altså n - 2) er av grad 3, må
4*2 + 3*(n - 2) = 2*10.
Denne likningen har løsningen n = 6.
En regulær graf er en graf der alle noder har samme grad g. Så dersom en regulær graf har n noder og k kanter, må
n*g = 2k,
dvs. at n = 2k/g. Denne formelen gir f.eks. at for en graf med k=15 kanter og noder av grad 5, så er antall noder
n = 2*15/5 = 30/5 = 6.
4*2 + 3*(n - 2) = 2*10.
Denne likningen har løsningen n = 6.
En regulær graf er en graf der alle noder har samme grad g. Så dersom en regulær graf har n noder og k kanter, må
n*g = 2k,
dvs. at n = 2k/g. Denne formelen gir f.eks. at for en graf med k=15 kanter og noder av grad 5, så er antall noder
n = 2*15/5 = 30/5 = 6.