🕸️

Discrete Mathematics: Graphs & Structures

60 cards · 🇺🇸 English

Graphs, paths, trees and the discrete structures behind computer science.

logicdiscrete-mathgraphs

Study all 60 cards for free

Flashcards, quizzes, pixel-art games and a daily review that remembers for you.

Study this deck free

Try the first 10 cards

1 / 10
Question

Discrete mathematics

Knew itLearning

Tap the card for the answer · swipe right if you knew it, left if not

Already have an account? Sign in

Cards

  1. 1Discrete mathematics
    The study of mathematical structures that are fundamentally discrete (countable, separated values) rather than continuous, including integers, graphs, and logical statements.
  2. 2How does discrete mathematics differ from continuous mathematics?
    Discrete mathematics deals with countable, separated objects (integers, graphs); continuous mathematics deals with smooth, connected phenomena (real numbers, calculus, geometry).
  3. 3Why is discrete mathematics important for computer science?
    Computers operate in discrete steps and store discrete bits. Discrete math provides foundations for algorithms, data structures, databases, cryptography, and computational theory.
  4. 4Graph in discrete mathematics
    A structure consisting of vertices (nodes) connected by edges (links). Used to model relationships, networks, and connections.
  5. 5a directed vs undirected graph
    Undirected: edges have no direction (symmetric relationship). Directed (digraph): edges have direction indicated by arrows (asymmetric relationship).
  6. 6Path in a graph
    A sequence of vertices where each adjacent pair is connected by an edge. A simple path visits each vertex at most once.
  7. 7Cycle in a graph
    A path that starts and ends at the same vertex. A simple cycle has no repeated vertices except the first/last.
  8. 8Connected graph
    A graph where there exists a path between every pair of vertices. No isolated components.
  9. 9Tree in graph theory
    A connected, acyclic (no cycles) undirected graph. A tree with n vertices has exactly n-1 edges.
  10. 10Spanning tree
    A subgraph that includes all vertices of the original graph and is a tree (connected, acyclic). Used in network design.
  11. 11State the Four Color Theorem.
    Any map can be colored using at most four colors so that no adjacent regions share the same color. Proved in 1976 by Appel and Haken using computers.
  12. 12Graph coloring
    Assigning colors to vertices such that no two adjacent vertices share the same color. The chromatic number is the minimum colors needed.
  13. 13Complete graph Kₙ
    A graph where every pair of distinct vertices is connected by an edge. Kₙ has n vertices and n(n-1)/2 edges.
  14. 14Bipartite graph
    A graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to the other. No edges within a set.
  15. 15Euler's formula for planar graphs
    V - E + F = 2, where V = vertices, E = edges, F = faces (regions). Applies to connected planar graphs.
  16. 16Eulerian path
    A path that visits every edge exactly once. Exists if a graph has exactly 0 or 2 vertices of odd degree.
  17. 17Hamiltonian path
    A path that visits every vertex exactly once. Finding one is NP-complete (computationally hard).
  18. 18Combinatorics
    The study of counting, arranging, and combining discrete objects. Includes permutations, combinations, and enumeration techniques.
  19. 19Permutation
    An ordered arrangement of objects. The number of permutations of n objects is n! = n × (n-1) × ... × 2 × 1.
  20. 20Combination
    A selection of objects where order doesn't matter. The number of ways to choose k objects from n is C(n,k) = n!/(k!(n-k)!).
  21. 21Binomial coefficient C(n,k)
    The number of ways to choose k items from n items without regard to order. Also written as (n choose k) or ₙCₖ.
  22. 22State the Pigeonhole Principle.
    If n items are placed into m containers with n > m, then at least one container must contain more than one item.
  23. 23Inclusion-Exclusion Principle
    For counting elements in unions of sets: |A∪B| = |A| + |B| - |A∩B|. Generalizes to more sets by alternating addition and subtraction.
  24. 24Generating function
    A formal power series used to encode sequences of numbers (like combinatorial counts). Coefficient of xⁿ gives the nth term.
  25. 25Pascal's triangle
    A triangular array where each number is the sum of the two above it. Row n contains binomial coefficients C(n,k) for k=0 to n.
  26. 26Recurrence relation
    An equation that defines a sequence recursively in terms of previous terms. Example: Fibonacci Fₙ = Fₙ₋₁ + Fₙ₋₂.
  27. 27Fibonacci sequence
    F₀=0, F₁=1, Fₙ = Fₙ₋₁ + Fₙ₋₂. Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Appears throughout nature and mathematics.
  28. 28Mathematical logic
    The study of formal systems of reasoning, including propositional logic, predicate logic, and rules of inference.
  29. 29Proposition
    A declarative statement that is either true or false (but not both). Example: '5 is prime' (true), '2+2=5' (false).
  30. 30Basic logical connectives
    AND (∧), OR (∨), NOT (¬), IMPLIES (→), IF AND ONLY IF (↔). Used to build compound propositions from simple ones.

And 30 more cards. Study the whole deck free

Articles about this deck

More Mathematics decks

See all
Study all 60 cards free