Resume
Samenvatting Grafentheorie (OAWI-H1GRAAF-12)
- Cours
- Établissement
Samenvatting voor grafentheorie (behaald cijfer: 8,1)
[Montrer plus]
Vendeur
S'abonner
joshtukker
Avis reçus
Aperçu du contenu
1755945 Josh TukkerGrafentheorie
Hoofdstuk 1 – Inleiding en basisbegrippen
1.2 Basisbegrippen
• 𝑛 is het aantal punten, 𝑚 is het aantal lijnen.
• Een graaf is een diagram die bestaat uit punten die wel of niet verbonden worden door één of
meer lijnen.
§ Is de lijn voorzien van een richting? Dit is een gerichte graaf.
§ Is de lijn voorzien van een gewicht? Dit is een gewogen graaf.
• Twee verbonden punten zijn buren, twee verbonden lijnen heten buurlijnen.
§ Er is sprake van meervoudige lijnen als tussen twee punten meer dan één lijn loopt.
§ Een lus is een lijn van een punt naar zichzelf.
§ Een graaf zonder meervoudige lijnen en lussen is een enkelvoudige graaf.
§ Als van graaf 𝐺 enkele lijnen en/of punten worden weggelaten, dan ontstaat de deelgraaf
van 𝐺.
• De valentie van een punt geeft aan hoeveel lijnen er aan een punt vastzitten, waarbij een lus voor
twee telt.
§ Bij enkelvoudige grafen wordt ook het begrip lijnvalentie gebruikt. Dit geeft het aantal andere
lijnen aan die vastzitten aan die lijn.
§ Een geïsoleerd punt is een punt met valentie 0.
§ De valentie-rij is de niet-dalende rij van valenties van de punten van de graaf.
§ Een graaf 𝐺 is regelmatig van de orde 𝒌 als ieder punt van 𝐺 valentie 𝑘 heeft.
• Handenschud-lemma:
§ In elke graaf is de valentiesom gelijk aan 2𝑚.
• Een ongelabelde graaf is een graaf waarbij de punten geen naam hebben.
§ Als er voor de tekening van twee ongelabelde grafen een naamgeving te verzinnen is zo dat ze
dezelfde (gelabelde) graaf voorstellen, dan zijn beide ongelabelde grafen isomorf.
- Twee ongelabelde grafen 𝐺 en 𝐻 zijn isomorf als het mogelijk is de punten van 𝐺 en 𝐻 zo te
labelen dat gelijk gelabelde punten van 𝐺 en 𝐻 gelijke buren hebben.
• Een pad in een graaf is een rij opeenvolgende verschillende lijnen.
§ Een pad wordt genoteerd als een rij opeenvolgende lijnen.
§ Paden worden aangegeven met Griekse letters (α, β, γ, etc.).
§ Het eerste punt heet het beginpunt en het laatste punt heet het eindpunt.
- Als het beginpunt en eindpunt van een pad α samenvallen, heet het pad α een circuit.
o Een circuit van drie lijnen noem je een driehoek, een circuit van vier lijnen noem je een
vierhoek, etc.
• Een graaf heet een samenhangende graaf als er tussen elk tweetal verschillende punten van de
graaf een pad bestaat.
§ Een niet-samenhangende graaf bestaat uit een aantal componenten, die ieder afzonderlijk wel
samenhangend zijn, maar onderling niet verbonden zijn.
1.3 Verbindingsmatrices
• Een graaf kan numeriek worden weergegeven door middel van een verbindingsmatrix.
§ In een verbindingsmatrix geeft het getal 1 aan dat punten buren zijn.
§ Het aantal tweestap-, driestap-, vierstap-, etc-routes zijn te berekenen met behulp van de
matrixvermenigvuldiging.
1/9
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur joshtukker. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €4,99. Vous n'êtes lié à rien après votre achat.
Peut-on faire confiance à Stuvia ?
4.6 étoiles sur Google & Trustpilot (+1000 avis)
65040 résumés ont été vendus ces 30 derniers jours
Fondée en 2010, la référence pour acheter des résumés depuis déjà 15 ans
Récemment vu par vous
Examen ·
NMLS Test Outline Questions with correct Answers
Pack ·
PORTAGE LEARNING BIOD 152 A&P 2 EXAMS
Examen ·
PPCT|| 95 Questions|| Correct Answers|| Verified
Examen ·
FISDAP Operations EMT Exam With Verified Answers
Examen ·
EENT APEA EXAM QUESTIONS WITH COMPLETE SOLUTIONS
Examen ·
MN Dental Jurisprudence Exam 2024 Graded A+
Examen ·
NUR 326 Exam 1 Questions With Complete Solutions
Resume ·
Samenvatting - Kinesiologie van pols en hand
