Samenvatting
Samenvatting Grafen
- Vak
- Wiskunde
- Instelling
- NHL Stenden Hogeschool (NHL)
Korte maar krachtige samenvatting, compleet en zonder dubbelingen, met duidelijke voorbeelden als geheugensteun.
[Meer zien]Voorbeeld 2 van de 9 pagina's
Voorbeeld 2 van de 9 pagina's
In winkelwagengesponsord bericht van onze partner
Voorbeeld van de inhoud
1. Conventies2. Tips
3. Definities
3.1. Schema wandeling
3.2. Schema graaf
4. Eigenschappen
5. Kortste pad
6. Optimale netwerk
7. Doolhof
8. Chinese postbodeprobleem
9. Handelsreizigersprobleem
10. Ondergrens LHC
11. Maximale afwijking t.o.v. het LHC
12. Vinden van een K3,3
13. Kleurbaarheid
13.1. Kleurgetal bepalen
13.2. Landkaartkleuring
14. Compatabilieitsgraaf
1/9 © Peter Zomerdijk
, 1. Conventies
• voorbeelden zijn omkaderd
• G: graaf
• A ⇒ B : als A dan B (nodig)
• A ⇔ B : als A dan B en als B dan A (nodig ꓥ voldoende: A ⇒ B ꓥ B ⇒ A)
2. Tips
• bewijzen vaak vanuit het ongerijmde
• bij vraag naar "minstens" of "minimaal", gebruik kleurbaarheid (zie 13)
3. Definities
graaf : diagram, bestaande uit punten die al dan niet verbonden zijn met lijnen
aantal punten n : aantal punten (knopen) in een G
aantal lijnen m : aantal lijnen in een G
label : unieke identificatie, hoofdletter voor punt, kleine letter voor lijn
buren : 2 direct verbonden punten
geïsoleerd punt : punt met valentie 0
eindpunt : punt met valentie 1
valentie : aantal lijnen aan een punt = aantal buren
lus : lijn vanaf een punt naar hetzelfde punt
dubbele lijn : meerdere lijnen tussen dezelfde buren
valentierij : niet-dalende rij van valenties
valentiesom V : som van de valenties
gerichte G : lijnen zijn pijlen en geven een gedwongen richting aan
gewogen G : lijnen hebben waardes
simpele G : bevat geen lussen en geen dubbele lijnen
wandeling = weg : serie aaneengesloten lijnen
rondwandeling : wandeling met start = finish
pad = pennenstreek : wandeling met elke lijn maximaal 1 keer
samenhangende G : tussen elk paar punten bestaat een pad
component = deel G : los gedeelte binnen een niet-samenhangende G
brug : lijn die bij weglating het aantal componenten verhoogd
orde k : dezelfde valentie van elk punt
regelmatige G : simpele G van orde k
volledige G Kn : regelmatige G van n punten met een lijn tussen elk paar punten
2-delige G : punten kunnen in 2 groepen (W,Z) met elke lijn tussen 1 W en 1 Z
volledige 2-delige G Kp,q : tussen elk puntenpaar W-Z precies 1 lijn
circuit : pad met startpunt = finishpunt
n-hoek : circuit met n punten en n lijnen
complement Gc : bestaat uit alle punten en de ontbrekende lijnen t.o.v. de volledige
gelijke G : evenveel lijnen tussen overeenkomstig gelabelde punten (exact gelijk)
isomorfe G ; gelijk maar met andere of zonder labels
zelfcomplementaire G ; de originele G (5-hoek) is isomorf met het complement (5-puntige ster)
eulerpad ; pad met elke lijn precies 1 keer
semi-euler G ; samenhangende G met eulerpad
eulercircuit : circuit met elke lijn precies 1 keer
euler G : samenhangende G met eulercircuit
2/9 © Peter Zomerdijk
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper PAJZ. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €5,99. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 71498 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen