100% tevredenheidsgarantie Direct beschikbaar na je betaling Lees online óf als PDF Geen vaste maandelijkse kosten
logo-home
Eerder door jou gezocht
Eerder door jou gezocht
logo
Samenvatting Grafentheorie €5,49
In winkelwagen
Snel navigeren naar
Voorbeeld
  2.  
  3. Haagse Hogeschool (HHS)
  4.  
  5. Grafentheorie

Samenvatting

Samenvatting Grafentheorie

2 beoordelingen
 13 keer verkocht

In dit document worden de basisonderwerpen in de grafentheorie behandeld. Definities worden uitgelegd met af en toe wat voorbeelden. Algoritmen, heuristieken en stellingen zijn met plaatjes helder weergegeven.

Voorbeeld 2 van de 12  pagina's

Document informatie

  • 2 oktober 2018
  • 12
  • 2017/2018
  • Samenvatting

Onderwerpen

  • grafentheorie samenvatting
  • hbo grafentheorie naslagwerk

Geschreven voor

Alle documenten voor dit vak (2)

2  beoordelingen

review-writer-avatar

Door: karinheijmen • 3 jaar geleden

review-writer-avatar

Door: jyvre • 4 jaar geleden

Ik vind dat het veel gemakkelijker is om die grafentheorie op papier te bestuderen.

Verkoper

avatar-seller
Quico42

Ontvangen beoordelingen

Voorbeeld van de inhoud

A. Inleiding (p1-p7)
compatibel veroorzaken geen conflcten met elkaar (ln dlt geval verkeersstromen).
compatiblllteltsgraa Graaf waarln punten met lljnen zljn veribonden aan andere punten dle
f compatibel zljn (elkaar nlet conflcteren).




deelgraaf Onderdeel van een graaf.
volledlge graaf Deelgraven dle zo zljn opgeibouwd waariblj elk tweetal punten veribonden
ls. Hlervoor zljn mlnlmaal 3 punten nodlg.




In de compatiblllteltgraaf ls het ‘drlehoekjef ABC een volledlge deelgraaf.
Ze ibestaat ult louter wederzljds compatibele stromen want A, B en C
kunnen alle tegelljkertjd stromen!
Bepaal de  Teken de compatiblllteltgraaf.
compatibllltelt en  Bepaal voor élk punt de grootste volledlge deelgraaf en streep
cyclustjd m.ib.v. een duibibele door.
compatiblllteltgraaf.  Selecteer een aantal van deze deelgrafen zó dat elk punt van de
compatiblllteltgraaf ln deze selecte van deelgrafen voorkomt.
 Deel de cyclustjd door het aantal volledlge deelgrafen ult de
selecte ken aan ledere perlode zonn volledlge deelgraaf toe.
gerichte graaf = Graaf dle wordt toegepast iblj projecten met dlverse taken (actvltelten).
projectgraaf De projectgraaf houdt rekenlng met:
 Van startpunt naar elndpunt vla pljlen.
 Volgorde (vla pljlen) en duur van de taken.
 Taken dle onafankelljk van elkaar plaatsvlnden (vanult het
startpunt met lljnen).




Maxlmale ultloop proces V iblj volledlge ibezetng =6 3 2 - 4 - 3 = 4 uur
competitiegraaf Graaf dle wordt toegepast om de voedselketen weer te geven. Een
compettegraaf ibestaat ult losse delen (componenten).

Ecologlsche Soorten ult één component van de compettegraaf reageren op dezelfde
ibetekenls van een manler op omgevlngsfactoren zoals temperatuur, vochtgheld en hoogte.
component ln de
compettegraaf



1

, B. Basisbegrippen (p9-p19)
graaf Dlagram, ibestaande ult punten dle al dan nlet veribonden zljn door een lljn.
Tussen een tweetal punten mogen meerdere lljnen lopen (meervoudlge
lljnen) en het ls ook toegestaan dat een lljn loopt van een punt naar zlchzelf
(lus). Opm: een graaf ls géén plategrond op schaal.
slmpele graaf Graaf zonder lussen en meervoudlge lljnen.
gewogen graaf Graaf met lljnen dle zljn voorzlen van een getal (gewlcht).
label (punt = n) Naam van een punt, aangeduld met een hoofdleter.
n = aantal punten een graaf.
label (lijn = m) Naam van een lljn, aangeduld met een klelne leter.
m = aantal lljnen van een graaf.
buren 2 punten dle door een lljn zljn veribonden.
valentie Het aantal lljnen dat aan dat punt vast zlt (een lus telt voor 2).
valentierij De nlet-dalende (stjgende) rlj van alle valentes van een graaf.
geïsoleerd punt Een punt dat nlet veribonden ls met een ander punt.
eindpunt Een punt dat met één lljn ls veribonden met een ander punt.
regelmatig van Een graaf G heet regelmatgg vangdegordegk als leder punt van G valente k
de orde heef.




Regelmatge graaf van de orde 3 (aantal lljnen 12, valentesom 24).
valentesom ls 2m

m = aantal lljnen




P heef valente 5. Q heef valente 3. R ls een geïssoleerd punt en S een
elndpunt. De valentesom ls 1 2 3 3 5= 14. De graaf heef 7 lljnen.
lsomorf structureel gelljk
gelljke grafen Twee gelaibelde grafen noemen we gelljk als er tussen overeenkomstg
gelaibelde punten evenveel lljnen lopen (zle graaf X en Y hleronder).
Als je de laibels van Y julst herplaatst, dan wordt graaf Y gelljk aan X.
isomorfe grafen Twee grafen, gelaibelde of ongelaibelde, noemen we lsomorf als het
mogelljk ls de punten van ibelde grafen te (her-)laibelen zo dat gelljke grafen
ontstaan




Als je ln graaf Z de julste laibels plaatst, dan ls deze gelljk aan graaf X en Y.
wandellng Een rlj opeenvolgende lljnen (ln een graaf). Een punt en lljn mogen ln een
wandellng meerdere keren voorkomen.
pad Een rlj opeenvolgende, verschillende lljnen (ln een graaf). Een punt mag ln


2

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

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

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

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 Quico42. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €5,49. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 66184 samenvattingen verkocht

Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen

Begin nu gratis
€5,49  13x  verkocht
  • (2)
In winkelwagen
Toegevoegd