FVI - Def.

Een taal L ⊆ Σ* is een reguliere taal

Ze kan opgebouwd worden vanuit ∅, {λ} en {σ} door een eindig aantal keer de bewerkingen concatenatie, unie en Kleene-sluiting te gebruiken

Een string x wordt aanvaard door een eindige automaat A

δ*(q0, x) ∈ F

Een toestand qi behoort tot δ*(q0, σ1σ2…σn) in een niet-deterministische eindige automaat

Er bestaat een pad in de automaat van q0 naar qi waarvan de pijlen opeenvolgend de labels σ1, σ2…σn hebben (inclusief λ-pijlen)

Een functie f is Turing-berekenbaar

Er bestaat een Turingmachine M zodanig dat f = fM

Een functie is effectief berekenbaar (These van Church)

De functie is Turing-berekenbaar

Een taal L is NP-compleet

L ∈ NP en voor elke andere taal L′ ∈ NP geldt dat L′ ∝ L

G(V, E, ϕ) is een enkelvoudige graaf

(1) Voor elke boog e in E geldt ϕ(e)=(v,w) impliceert v ≠ w, en (2) voor elke e1, e2 in E geldt e1 ≠ e2 impliceert ϕ(e1) ≠ ϕ(e2)

Twee bogen in een graaf zijn parallel

Ze verbinden dezelfde knopen met elkaar

Een graaf is samenhangend

Er bestaat een pad tussen elk paar knopen van de graaf

Een graaf G heeft een Euleriaanse kring

De graaf is samenhangend en elke knoop heeft een even graad

Een graaf G heeft een Euleriaans pad

De graaf is samenhangend en hoogstens 2 knopen hebben een oneven graad

Een graaf G′(V′, E′) is een deelgraaf van een graaf G(V, E)

V′ ⊆ V en E′ ⊆ E

G′(V′, E′) is de deelgraaf van G geïnduceerd door V′

E′ = {(v, w) ∈ E | v, w ∈ V′}

Een graaf G(V, E) is een component van een graaf G′(V′, E′)

G ⊆ G′, G is niet leeg, G is samenhangend en er bestaat geen samenhangende graaf G′′ waarvoor G ⊂ G′′ ⊆ G′

Element (B^k)ij van booleaanse buurmatrix B is 1

Er bestaat een pad van lengte k van knoop vi naar vj

Element Sij van de sommatrix S is 1 (met S als de som van B^k voor k=1 tot l)

Er bestaat een pad van lengte l of korter tussen knoop vi en vj

Twee enkelvoudige grafen G(V, E) en G′(V′, E′) zijn isomorf

Er bestaat een bijectie h van V naar V′ zodanig dat {h(x) | x ∈ V} = V′ en {(h(x), h(y)) | (x, y) ∈ E} = E′

Twee enkelvoudige grafen zijn isomorf (obv buurmatrix)

Er bestaat een ordening van de knopen zodat hun buurmatrix gelijk is

Twee grafen G en G′ zijn isomorf (obv incidentiematrix)

Er bestaat een ordening van de knopen en bogen waarvoor de incidentiematrices van G en G′ gelijk zijn

Een enkelvoudige graaf G(V, E) is tweeledig

V kan opgedeeld worden in twee niet-lege deelverzamelingen V1 en V2, zodat er enkel bogen bestaan tussen V1 en V2 (en nooit binnen V1 of V2)

Een graaf G is een subdivisie van een graaf G′

G′ kan uit G bekomen worden door nul, één of meer rijreducties (het verwijderen van een knoop van graad 2)

Twee grafen G en G′ zijn homeomorf

Er bestaat een subdivisie van G die isomorf is met een subdivisie van G′

Graaf G is vlak (gegeven dat G homeomorf is met G′)

Graaf G′ is vlak

Een graaf is vlak (Stelling van Kuratowski)

De graaf bevat geen deelgraaf die een subdivisie is van K5 of K3,3

T(VT, ET) is een opspannende boom voor G(V, E)

T is een boom, VT = V en ET ⊆ E

Een graaf heeft een opspannende boom

De graaf is samenhangend

De capaciteit van snede (P, P) is gelijk aan de stroming F(a,z)

Voor alle i ∈ P, j ∈ P is F(i, j) = Ci,j en voor alle i ∈ P, j ∈ P is F(i, j) = 0

Een knoop v ∈ V komt overeen met w ∈ W in een matching

De gehele stroming F(v, w) = 1 in het overeenkomstige matching netwerk

Een gerichte, tweeledige graaf G(V∪W, E) heeft een volledige matching (Trouwstelling van Hall)

Voor elke deelverzameling S ⊆ V geldt |S| ≤ |R(S)|

Een relatie R op een verzameling S is een partiële orderelatie

R is reflexief, antisymmetrisch en transitief

Element a is een supremum van X (a = sup(X))

a is een bovengrens voor X en voor elke bovengrens a′ van X geldt dat a ≤ a′

Element b is een infimum van X (b = inf(X))

b is een ondergrens voor X en voor elke ondergrens b′ van X geldt dat b ≥ b′

Een verzameling X in een complete tralie is gericht

Elke eindige deelverzameling van X heeft een bovengrens in X