Flashcards om grunderna i grafteori

Question 1

Vad är en graf $G=(V,E)$?

Accepted Answer

En graf är ett ordnat par $G=(V,E)$ där $V$ är en mängd hörn (noder) och $E$ är en mängd kanter, där varje kant förbinder två hörn (i en oriktad graf är en kant ett oordnat par $\{u,v\}$).

Question 2

Vad är skillnaden mellan en vandring, en väg och en cykel?

Accepted Answer

En vandring kan upprepa hörn/kanter. En väg är en vandring utan upprepade hörn. En cykel är en sluten väg (start = slut) utan upprepade hörn förutom det första/sista.

Question 3

Vad innebär det att en graf är plan, och vad är Eulers formel för sammanhängande plana grafer?

Accepted Answer

Plan betyder att den kan ritas i planet utan att kanter korsar varandra (förutom vid hörn). För en sammanhängande plan inbäddning gäller $$V-E+F=2,$$ där $F$ är antalet ytor (inklusive den yttre ytan).

Flashcards om grunderna i grafteori

Bemästra Matematik med AI

Inlärningsresurser

Betrodd & Erkänd