Diskret matematik

Alla Inga Spara

• 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)!

Alla Inga Spara