Diskret matematik

minsta antalet färger en graf kan ha utan att ha någon edge till en annan vertecis med samma färg Chromatic number

En graf där inga edge behöver korsa varandra i en 2D bild Planar graph

noder Vertices

Båge, vägen mellan noderna Edges

Ytor Faces, region

för planargraphs antalen ytor r är lika med e-v+2

alla vägarna(edges) en gång oberoend av antalet nodes. Sluten Euler circuit

alla noder(vertices) en gång oberoend av att korsa edges. Sluten Hamilton cycle

{n \choose k} OR C(n, k) n!/(k!(n-k)!)

olika vridning av samma graph Isomorphic

Naturliga tal N

Heltal Z

Rationela tal Q

Reela tal R

Komplexa tal OR Imaginära tal C

A={a}; B={b}; D={c}; Om A & B & C tillsammans delar mängden k, hur räknas k ut? A+B+C-A∩B-B∩C-C∩A+A∪B∪C

sätt att färga grafen G med x färger då x ∈𝐍 P[G](x)

P[triangel](x) = x(x-1)(x-2)

P[kvadrat](x)= x(x-1)(x-1)+x(x-1)(x-2)^2

Bipartite graph sign K[n, m]

Path graph sign P[n]

Cycle graph sign C[n]

Complete graph sign K[n]

Wheel graph sign W[n]

Hypercube graph sign Q[n]

Odd graph sign O[n]

Tree edges v-1

Tree Chromatic number 2, if v > 1

Ser ut som ett träd med en utgångsprick verices som delar upp sig i en eller flera nya verices Rooted tree

I rooted tree de yttersta noderna (verices) Leaf

grafen G[n] invers same vertices, opposite edges

Hypercube graph Q[n] vetices 2^n

Hypercube graph Q[n] edges 2^(n-1)*n

Hypercube graph Q[n] Chromatic number 2

Euler circuit regel deg(v)=even

Haminton cycle regel deg(e)=even

Complete graph K[n] edges v(v-1)/2

Planar graph edges ≤3v-6

Planar graph faces ≤2v-4

Wheel graph W[n] edges 2(v-1)

Wheel graph cromatic number 3 if odd, 4 if even

complete bipartite graph OR biclique K[m, n] edges m*n

Bipartite graph cromatic number 2

Path graph P[n] edges v-1

Path graph P[n] cromatic number 2

C(n, k) n!/(k!(n-k)!)

P(n, k) n!/(n-k)!

Click

Type

Listen

Games

Drucken