Samenvatting
Samenvatting Grafen
- Vak
- Instelling
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 winkelwagen
In winkelwagen
Verkoper
Volgen
PAJZ
Ontvangen beoordelingen
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
Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:
Bewezen kwaliteit door reviews
Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!
In een paar klikken geregeld
Geen gedoe — betaal gewoon eenmalig met iDeal, creditcard of je Stuvia-tegoed en je bent klaar. Geen abonnement nodig.
Direct to-the-point
Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!
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 $7.02. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 72437 samenvattingen verkocht
Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen
Laatst bekeken door jou
Case uitwerking ·
Casus 3
Voordeelbundel ·
Biostatistiek
Voordeelbundel ·
Totale samenvatting inleiding verzekeringen
Voordeelbundel ·
Plan van aanpak scriptie - aangiftebereidheid bij lichtere vormen van criminaliteit verhogen
College aantekeningen ·
Apuntes
Voordeelbundel ·
Volledige samenvatting UK en US E2CG
Voordeelbundel ·
Zwangsvollstreckungsrecht und Zivilrechtspaket
Voordeelbundel ·
DATA SCIENCE METHODS FOR MADS BUNDLE
