Zusammenfassung
Samenvatting Grafen
- Kurs
- Hochschule
Korte maar krachtige samenvatting, compleet en zonder dubbelingen, met duidelijke voorbeelden als geheugensteun.
[ Mehr anzeigen ]vorschau 2 aus 9 Seiten
Vorschau 2 aus 9 Seiten
In den Einkaufswagen
In den Einkaufswagen
Verkäufer
Folgen
PAJZ
Deine Reviews
Inhaltsvorschau
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
Alle Vorteile der Zusammenfassungen von Stuvia auf einen Blick:
Garantiert gute Qualität durch Reviews
Stuvia Verkäufer haben mehr als 700.000 Zusammenfassungen beurteilt. Deshalb weißt du dass du das beste Dokument kaufst.
Schnell und einfach kaufen
Man bezahlt schnell und einfach mit iDeal, Kreditkarte oder Stuvia-Kredit für die Zusammenfassungen. Man braucht keine Mitgliedschaft.
Konzentration auf den Kern der Sache
Deine Mitstudenten schreiben die Zusammenfassungen. Deshalb enthalten die Zusammenfassungen immer aktuelle, zuverlässige und up-to-date Informationen. Damit kommst du schnell zum Kern der Sache.
Häufig gestellte Fragen
Was bekomme ich, wenn ich dieses Dokument kaufe?
Du erhältst eine PDF-Datei, die sofort nach dem Kauf verfügbar ist. Das gekaufte Dokument ist jederzeit, überall und unbegrenzt über dein Profil zugänglich.
Zufriedenheitsgarantie: Wie funktioniert das?
Unsere Zufriedenheitsgarantie sorgt dafür, dass du immer eine Lernunterlage findest, die zu dir passt. Du füllst ein Formular aus und unser Kundendienstteam kümmert sich um den Rest.
Wem kaufe ich diese Zusammenfassung ab?
Stuvia ist ein Marktplatz, du kaufst dieses Dokument also nicht von uns, sondern vom Verkäufer PAJZ. Stuvia erleichtert die Zahlung an den Verkäufer.
Werde ich an ein Abonnement gebunden sein?
Nein, du kaufst diese Zusammenfassung nur für $6.82. Du bist nach deinem Kauf an nichts gebunden.
Kann man Stuvia trauen?
4.6 Sterne auf Google & Trustpilot (+1000 reviews)
45.681 Zusammenfassungen wurden in den letzten 30 Tagen verkauft
Gegründet 2010, seit 15 Jahren die erste Adresse für Zusammenfassungen
Kürzlich von dir angesehen
