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.
I think it's much easier to study that graph theory on paper.
Seller
Follow
Quico42
Reviews received
Content preview
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
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 Quico42. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.92. You're not tied to anything after your purchase.
