Portal:Discrete mathematics

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Introduction

Graphs like this are among the objects studied by discrete mathematics, for their interesting mathematical properties, their usefulness as models of real-world problems, and their importance in developing computer algorithms.

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

Pseudoforest.svg
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.

WikiProjects

Project pages

Essays

Subprojects

Related projects

Selected images

Did you know?

DYK question mark

Categories

Topics in Discrete mathematics

Related portals

Associated Wikimedia

The following Wikimedia Foundation sister projects provide more on this subject:

Wikibooks
Books

Commons
Media

Wikinews 
News

Wikiquote 
Quotations

Wikisource 
Texts

Wikiversity
Learning resources

Wiktionary 
Definitions

Wikidata 
Database

Purge server cache
  1. ^ The kind of undirected graph considered here is often called a multigraph or pseudograph, to distinguish it from a simple graph.
  2. ^ Gabow & Tarjan (1988).
  3. ^ Dantzig (1963).
Retrieved from "https://en.wikipedia.org/w/index.php?title=Portal:Discrete_mathematics&oldid=854566957"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Portal:Discrete_mathematics
This page is based on the copyrighted Wikipedia article "Portal:Discrete mathematics"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA