Summary
Samenvatting Grafen
- Course
- Institution
Korte maar krachtige samenvatting, compleet en zonder dubbelingen, met duidelijke voorbeelden als geheugensteun.
[Show more]
Seller
Follow
PAJZ
Reviews received
Content preview
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller PAJZ. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $6.46. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
67096 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now