Flashcards basisbegrippen grafentheorie

Question 1

Wat is een graaf $G=(V,E)$?

Accepted Answer

Een graaf is een geordend paar $G=(V,E)$ waarbij $V$ een verzameling knopen (punten) is en $E$ een verzameling randen, waarbij elke rand twee knopen verbindt (in een ongerichte graaf is een rand een ongeordend paar $\{u,v\}$).

Question 2

Wat is het verschil tussen een wandeling, een pad en een cyclus?

Accepted Answer

Een wandeling mag knopen/randen herhalen. Een pad is een wandeling zonder herhaalde knopen. Een cyclus is een gesloten pad (start = einde) zonder herhaalde knopen behalve de eerste/laatste.

Question 3

Wat betekent het dat een graaf planair is, en wat is Eulers formule voor samenhangende planaire grafen?

Accepted Answer

Planair betekent dat hij in het vlak getekend kan worden zonder snijdende randen (behalve bij knopen). Voor een samenhangende planaire inbedding geldt: $$V-E+F=2,$$ waarbij $F$ het aantal vlakken is (inclusief het buitenvlak).

Flashcards basisbegrippen grafentheorie

Beheers Wiskunde met AI

Leerbronnen

Vertrouwd & Erkend