Portal:Discrete mathematics
Introduction
Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not vary smoothly in this way, but have distinct, separated values. Discrete mathematics therefore excludes topics in "continuous mathematics" such as calculus and analysis. Discrete objects can often be enumerated by integers. More formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets (sets that have the same cardinality as subsets of the natural numbers, including rational numbers but not real numbers). However, there is no exact definition of the term "discrete mathematics." Indeed, discrete mathematics is described less by what is included than by what is excluded: continuously varying quantities and related notions.
The set of objects studied in discrete mathematics can be finite or infinite. The term finite mathematics is sometimes applied to parts of the field of discrete mathematics that deals with finite sets, particularly those areas relevant to business.
Research in discrete mathematics increased in the latter half of the twentieth century partly due to the development of digital computers which operate in discrete steps and store data in discrete bits. Concepts and notations from discrete mathematics are useful in studying and describing objects and problems in branches of computer science, such as computer algorithms, programming languages, cryptography, automated theorem proving, and software development. Conversely, computer implementations are significant in applying ideas from discrete mathematics to real-world problems, such as in operations research.
Selected article
A 1-forest (a maximal pseudoforest), formed by three 1-trees |
In graph theory, a pseudoforest is an undirected graph^{[1]} in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two closed paths of consecutive edges share any vertex with each other, nor can any two such closed paths be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.
The names are justified by analogy to the more commonly studied trees and forests. (A tree is a connected graph with no cycles; a forest is a disjoint union of trees.) Gabow and Tarjan^{[2]} attribute the naming of pseudoforests to Dantzig's 1963 book on linear programming, in which pseudoforests arise in the solution of certain network flow problems.^{[3]} Pseudoforests also form graph-theoretic models of functions and occur in several algorithmic problems. Pseudoforests are sparse graphs – they have very few edges relative to their number of vertices – and their matroid structure allows several other families of sparse graphs to be decomposed as unions of forests and pseudoforests.
...Archive | Image credit: User:David Eppstein | Read more... |
WikiProjects
The Mathematics WikiProject is the center for mathematics-related editing on Wikipedia. Join the discussion on the project's talk page.
Project pages
Essays
Subprojects
Related projects
Selected images
Did you know?
- ...that there are precisely six convex regular polytopes in four dimensions? These are analogs of the five Platonic solids known to the ancient Greeks.
- ...that the Catalan numbers solve a number of problems in combinatorics such as the number of ways to completely parenthesize an algebraic expression with n+1 factors?
Categories
Topics in Discrete mathematics
Major areas | Combinatorics | Graph Theory | Game theory |
---|---|---|---|
Related portals
Algebra | Analysis |
Category theory |
Computer science |
Cryptography |
Discrete mathematics |
Logic | Mathematics |
Number theory |
Physics | Science | Set theory | Statistics |
Associated Wikimedia
- ^ The kind of undirected graph considered here is often called a multigraph or pseudograph, to distinguish it from a simple graph.
- ^ Gabow & Tarjan (1988).
- ^ Dantzig (1963).