Interactive Lessons

Netwerken: delen, routes en gewichten

Lesnotities

Definitie

Een netwerk: knooppunten en kanten

Een netwerk is een tekening van stippen en lijnen. De stippen zijn de knooppunten en een lijn tussen twee knooppunten is een kant. Zo kun je een metrokaart, vrienden, wegen of de gangen van een school tekenen. Bij Delen typ je de kanten, zoals A-B, B-C, of kies je een situatie, en de applicatie telt de knooppunten en de kanten.
Voorbeeld
Het netwerk A-B, A-C, B-C, C-D, D-E heeft 5 knooppunten (A, B, C, D en E) en 5 kanten.
ABCDE5 vertices, 5 edges
Regel

De graden tellen op tot twee keer het aantal kanten

De graad van een knooppunt is het aantal kanten dat erin uitkomt. Elke kant heeft twee uiteinden, dus hij wordt twee keer geteld als je alle graden optelt. De som van de graden is dus altijd twee keer het aantal kanten, en dus altijd even. Delen toont de graden en hun som.
Voorbeeld
De graden zijn 2, 2, 3, 2 en 1 → , en kanten. Een som van 13 kan niet, want die is oneven.
A2B2C3D2E1Degrees: 2, 2, 3, 2, 1
Definitie

Delen en kringen

Een netwerk is één deel als je langs kanten van elk knooppunt naar elk ander knooppunt kunt komen. Zo niet, dan heeft het losse delen. Een kring is een rondje dat terugkomt bij het begin zonder een knooppunt twee keer te gebruiken. Delen zegt uit hoeveel delen het netwerk bestaat en of er een kring is.
Voorbeeld
A-B, B-C, A-C, D-E en een los knooppunt F geven 3 delen: A, B, C; dan D, E; en F alleen. A, B en C vormen een kring: A − B − C − A.
ABCDEF3 separate parts
Definitie

Routes: een pad komt een knooppunt niet twee keer tegen

Een route (een pad) gaat langs kanten van het ene knooppunt naar het andere en komt geen knooppunt twee keer tegen. Om de routes van A naar F te tellen, volg je elke eerste stap vanaf A en bezoek je nooit een knooppunt twee keer. Bij Routes kies je Van en Naar, zie je hoeveel routes er zijn en loop je ze langs met Route; de lijst toont eerst de routes met de minste kanten.
Voorbeeld
In het netwerk A-B, A-C, B-C, C-D, D-E, E-F, D-F zijn er 4 routes van A naar F: 2 beginnen met A − B en 2 beginnen met A − C. De kortste is A − C − D − F met 3 kanten; de langste is A − B − C − D − E − F met 5 kanten.
ABCDEFA − C − D − F: 3 edges
Definitie

Een gewogen netwerk en het totale gewicht

In een gewogen netwerk heeft elke kant een gewicht: een afstand, een tijd of een prijs. Je typt het na een dubbele punt: A-B:4. Het totale gewicht van een route is de som van de gewichten van de kanten. Bij Gewichten staan de gewichten in kleine vakjes op de kanten.
Voorbeeld
In het metronetwerk A-B:4, B-C:3, C-D:5, B-E:6, E-F:2, D-F:4, C-E:7 heeft de route A − B − C − D − F het totaal . De route A − B − C − E − F heeft ook .
4356247ABCDEFA − B − C − D − F: 4 + 3 + 5 + 4 = 16
Regel

Het kleinste totaal, stap voor stap

Om het kleinste totaal te vinden hoef je niet elke route op te schrijven. Begin bij het eerste knooppunt met het totaal 0. Het knooppunt met het kleinste totaal dat nog niet definitief is, wordt definitief. Werk de totalen van de buren bij: een kleiner totaal vervangt een groter. Herhaal dit. Bij Gewichten laat de tabel met Beste totaal en Status (definitief of voorlopig) dit stap voor stap zien.
Voorbeeld
Vanaf A in het metronetwerk: A 0; B 4; C 7 ; E 10 (, beter dan via C); D 12 ; F 12 . Het kleinste totaal van A naar F is 12, op A − B − E − F.
4356247ABCDEFA − B − E − F: 4 + 6 + 2 = 12
Let op!

De minste kanten is niet altijd het goedkoopst

De route met de minste kanten kan een groter totaal hebben dan een langere route. Stop dus niet bij de kortste route: tel de gewichten van de routes op en vergelijk. Gewichten toont het totaal van de route met de minste kanten en zegt hoeveel meer die kost dan het kleinste totaal.
Voorbeeld
In A-B:2, B-C:2, A-C:7, C-D:1, van A naar D: A − C − D heeft 2 kanten en het totaal . A − B − C − D heeft 3 kanten en het totaal , dat is 3 minder.
2271ABCDA − B − C − D: 2 + 2 + 1 = 5
Tip

Een netwerk typen en de toetsen

Typ de kanten met komma’s ertussen, zoals A-B, B-C. Een losse letter is een knooppunt zonder kant. Gebruik de letters A tot en met H, met hoogstens 12 kanten. Een gewicht staat na een dubbele punt, zoals A-B:4, en elke kant heeft er een nodig of geen enkele. Er zijn 4 kant-en-klare situaties. Niets wat je typt wordt opgeslagen of ergens naartoe gestuurd. Elke stepper, keuze en knop werkt met het toetsenbord.
Voorbeeld
A-B:4, B-C:3, C-D mag niet, want C-D heeft geen gewicht. A-B:4, B-C:3, C-D:5 mag wel.

Oefenen

Wat is in het netwerk A-B, A-C, B-C, C-D, D-E de graad van knooppunt C? Makkelijk
ABCDEThe network of the question
Toon de oplossing
De graad is het aantal kanten dat in C uitkomt. Tel de kanten die in C eindigen: A-C, B-C en C-D.
Dat zijn er 3.
3
Tel elke kant van het knooppunt één keer. Een kant A-B telt mee voor A en voor B.
Een netwerk heeft 6 knooppunten met de graden 3, 3, 2, 2, 2 en 2. Hoeveel kanten heeft het? Makkelijk
Toon de oplossing
Tel de graden op → .
Elke kant heeft twee uiteinden en is dus twee keer geteld → kanten.
7 kanten
Antwoord niet 14: dat is de som van de graden, waarin elke kant twee keer zit.
Welke van deze is een route in het netwerk A-B, A-C, B-C, C-D, D-E: A − C − D − E, A − B − D − E of A − C − B − C? Makkelijk
Toon de oplossing
Controleer elke stap: is er een kant tussen de twee letters, en komt een letter twee keer voor?
A − B − D − E: B-D is geen kant. A − C − B − C: C komt twee keer voor. A − C − D − E: A-C, C-D en D-E zijn kanten en geen knooppunt komt twee keer voor.
A − C − D − E
Een route gebruikt alleen kanten van het netwerk en komt nooit een knooppunt twee keer tegen.
Hoeveel routes zijn er van A naar F in het netwerk A-B, A-C, B-C, C-D, D-E, E-F, D-F? Middel
ABCDEFFrom A to F
Toon de oplossing
Volg de eerste stap vanaf A. Via B: A − B − C en dan verder naar D. Via C: A − C en dan verder naar D. Bezoek nooit een knooppunt twee keer.
Vanaf D kom je direct in F (D-F) of via E (D − E − F). Via B zijn er 2 routes en via C zijn er 2 routes: A − C − D − F, A − B − C − D − F, A − C − D − E − F en A − B − C − D − E − F.
routes.
4 routes
Ordenen op de eerste stap helpt: zo vergeet je geen route en tel je er geen twee keer.
Wat is in het metronetwerk A-B:4, B-C:3, C-D:5, B-E:6, E-F:2, D-F:4, C-E:7 het totale gewicht van de route A − B − C − E − F? Middel
4356247ABCDEFThe metro: weights in minutes
Toon de oplossing
Lees het gewicht van elke kant van de route af: A-B is 4, B-C is 3, C-E is 7 en E-F is 2.
Tel ze op → .
16
Een route met een andere laatste stap kan hetzelfde totaal hebben: A − B − C − D − F is ook 16.
Wat is in hetzelfde metronetwerk het kleinste totale gewicht van een route van A naar F, en welke route is dat? Middel
4356247ABCDEFA − B − E − F: 4 + 6 + 2 = 12
Toon de oplossing
Begin bij A met 0. B krijgt 4. C krijgt . E krijgt , beter dan via C.
D krijgt . F krijgt via E; via D zou het zijn.
Het kleinste totaal is 12, op A − B − E − F → .
12, op A − B − E − F
De route met de minste kanten (3 kanten) is hier ook de goedkoopste, maar dat is toeval, geen regel.
Hoeveel meer kost in het netwerk A-B:2, B-C:2, A-C:7, C-D:1 de route met de minste kanten van A naar D dan de route met het kleinste totale gewicht? Moeilijk
2271ABCDFrom A to D
Toon de oplossing
Minste kanten: A − C − D met 2 kanten. Het totaal is .
De andere route is A − B − C − D met 3 kanten en het totaal .
Het verschil is .
3
Hier bestaan maar twee routes, dus je kunt ze direct vergelijken. Bij meer routes werk je stap voor stap vanaf A.
Een netwerk heeft 6 knooppunten en elk knooppunt heeft graad 3. Hoeveel kanten heeft het? Kan een netwerk 5 knooppunten hebben die allemaal graad 3 hebben? Moeilijk
Toon de oplossing
De graden tellen op tot . Dat is twee keer het aantal kanten, dus er zijn kanten.
Bij 5 knooppunten zou de som zijn. De som van de graden moet twee keer het aantal kanten zijn, dus even, en 15 is oneven.
9 kanten; nee, dat kan niet
Een oneven som van graden komt nooit voor: het aantal knooppunten met een oneven graad is altijd even.
Zoek in de schoolgangen A-B:20, B-C:35, A-D:30, B-D:15, D-E:25, C-E:10 het kleinste totaal van B naar E en de route met het op een na kleinste totaal. Moeilijk
203530152510ABCDEB − D − E: 15 + 25 = 40
Toon de oplossing
Schrijf de routes van B naar E op: B − D − E, B − C − E en B − A − D − E.
Hun totalen → , en .
Het kleinste totaal is 40, op B − D − E; het tweede is 45, op B − C − E
Controleer of je elke route hebt gevonden: beginnen met B-A, B-C of B-D dekt hier alles.

Interactieve applicaties bij dit onderwerp

Gratis applicaties openen met een gratis leerlingaccount. Docenten kunnen alle applicaties gebruiken in een live les.

Over het gratis account en Plus

Bent u docent?

Geef live lessen met deze applicaties aan uw hele klas. Probeer het gratis: de eerste één maand.

Gratis proberen

Past bij deze leerjaren

IB (MYP, Diploma): MYP 4, MYP 5, Diploma, jaar 1, Diploma, jaar 2

Cambridge International: AS Level, A Level

Engeland (GCSE, A Level): Year 12 (A Level), Year 13 (A Level)

Wat de applicaties bij dit onderwerp leren 1 applicatie

Netwerken: delen, routes en gewichten

  • Een netwerk invoeren en zijn knopen, takken en graden aflezen
  • Routes tussen twee knopen tellen en de kortste in aantal takken vinden
  • De route met het kleinste totale gewicht vinden