Resume
Samenvatting Grafentheorie
- Cours
- Établissement
Een samenvatting van het vak Grafentheorie (volledige reader samengevat).
[Montrer plus]
Vendeur
S'abonner
cdenhollander
Avis reçus
Aperçu du contenu
GRAFENTHEORIE SAMENVATTINGHOOFDSTUK 1: BASIS
Een graaf is een wiskundige structuur die bestaat uit punten (vertices) en lijnen (edges).
Definitie
Een graaf G bestaat uit een eindige verzameling V, waarvan de elementen punten heten, en een
verzameling E, bestaande uit ongeordende paren van verschillende punten, welke lijnen genoemd
worden.
Een lijn heeft een begin-
en eindpunt, maar het
G wordt vaak aangeduid als (V, E)
kan ook andersom.
en soms als V(G) en E(G).
Volgens de definitie zijn er nu wat situaties te bedenken die hier net wel, of net niet, aan voldoen.
We bakenen de definitie dus af.
• Een verbinding van een punt met zichzelf?
Nee, want de verzameling E bestaat uit paren verschillende punten. Dit komt echter in de
opgaven af en toe wel voor.
• Twee verschillende verbindingen tussen twee punten?
Nee, want we hebben het over een verzameling paren en dus komt
één paar niet twee keer voor.
• Punten zonder verbindingen met anderen?
Ja, dat wordt niet uitgesloten. Dit noemen we dan een geïsoleerd punt.
Notaties
Punten hebben vaak een naam of een label, zoals 1, 2, 3 of a, b, c. Lijnen worden zo mogelijk
aangegeven door de labels van beide uiteinden achter elkaar te schrijven, zoals ab, 1a of 13, maar ba,
a1 of 31 zijn dan dezelfde lijnen.
Isomorfe grafen
Twee grafen G en H zijn isomorf als er een bijectie is tussen V(G) en V(H) en tussen E(G) en E(H). Dit
wil dus zeggen dat er bij één punt uit de ene graaf precies één punt uit de tweede graaf hoort en
omgekeerd. Zo hoort bij iedere lijn uit de eerste graaf ook precies één lijn uit de tweede graaf en
omgekeerd.
,• Deelgraaf: een deel van de punten en lijnen weggelaten.
• Opspannende deelgraaf: alleen een deel van de lijnen weggelaten.
• Geïndiceerde deelgraaf: elke lijn in de graaf die punten uit de deelgraaf verbindt, zit ook in de
deelgraaf. Dus als je een punt weglaat, laat je automatisch de lijn weg die eraan vastzit.
• Punten u en v die met elkaar verbonden zijn noemen we
buren.
• Punten u en v die met elkaar verbonden zijn heten de
uiteinden van de lijn uv.
• Twee lijnen met een gemeenschappelijk uiteinde heten
aangrenzend.
• Punt u en lijn uv heten incident met elkaar.
• De graad d(v) van een punt v van graaf G is het aantal lijnen van G dat incident is met v. De graad
van v zegt dus eigenlijk hoeveel verschillende lijnen er samenkomen in v.
• Een punt met graad 0 heet een geïsoleerd punt.
• Een punt met graad 1 heet een eindpunt.
Gradentheorie
De som van de graden van de punten van een graaf is altijd even.
Bewijs:
Elke lijn is incident met twee punten en telt dus bij twee punten mee in de graad. Dus ook geldt dat
het aantal punten van een oneven graad in een graaf even is.
Soorten grafen
Reguliere graaf
• Alle punten hebben dezelfde graad.
• k-regulier wil zeggen dat alle punten k als graad hebben.
• Volledige graaf: alle mogelijke lijnen tussen ieder tweetal punten komen voor.
Notatie: 𝐾𝑛
, Paden
• Notatie: 𝑃𝑛 .
• n geeft het aantal punten aan.
• 𝑃1 gebruiken we niet.
Cykels
• Notatie 𝐶𝑛 .
• n geeft het aantal punten aan.
• 𝐶1 en 𝐶2 bestaan we niet.
Wielen
• Notatie 𝑊𝑛.
• n geeft het aantal punten aan.
• Dit is pas zinvol vanaf n = 4.
Bipartiete graaf (tweedelingsgraaf)
• Punten vallen uiteen in twee verzamelingen
𝑉1 en 𝑉2 .
• Iedere lijn verbindt een punt uit 𝑉1 met een
punt uit 𝑉2 .
Volledige tweedelingsgraaf
• Ieder punt van 𝑉1 is verbonden met ieder punt van 𝑉2 .
• Als #𝑉1 = 𝑛 en #𝑉2 = 𝑚 dan is 𝐾𝑛,𝑚 de volledige
tweedelingsgraaf.
Bomen
• Een boom is een graaf zonder cykels.
• De eigenschappen van bomen volgt later.
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 cdenhollander. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €2,99. Vous n'êtes lié à rien après votre achat.
Peut-on faire confiance à Stuvia ?
4.6 étoiles sur Google & Trustpilot (+1000 avis)
78075 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à 14 ans