Skip to main content
Register
Springer Professional
SEARCH
Menu 1 2 3 4
Top

2021 | Book

Logic Read chapter Read first chapter

Discrete Mathematics and Graph Theory

A Concise Study Companion and Guide

Author: Prof. Dr. K. Erciyes

Publisher: Springer International Publishing

Book Series : Undergraduate Topics in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
share
SHARE
insite
SEARCH

About this book

This textbook can serve as a comprehensive manual of discrete mathematics and graph theory for non-Computer Science majors; as a reference and study aid for professionals and researchers who have not taken any discrete math course before. It can also be used as a reference book for a course on Discrete Mathematics in Computer Science or Mathematics curricula.

The study of discrete mathematics is one of the first courses on curricula in various disciplines such as Computer Science, Mathematics and Engineering education practices.

Graphs are key data structures used to represent networks, chemical structures, games etc. and are increasingly used more in various applications such as bioinformatics and the Internet. Graph theory has gone through an unprecedented growth in the last few decades both in terms of theory and implementations; hence it deserves a thorough treatment which is not adequately found in any other contemporary books on discrete mathematics, whereas about 40% of this textbook is devoted to graph theory.

The text follows an algorithmic approach for discrete mathematics and graph problems where applicable, to reinforce learning and to show how to implement the concepts in real-world applications.

Table of Contents

Frontmatter

Fundamentals of Discrete Mathematics

Frontmatter
Chapter 1. Logic
Abstract
Logic deals with laws of thought, and mathematical logic and proofs are the basic methods of reasoning mathematics. The laws of logic help us to understand the meaning of statements. Statements come in various forms, for example “7 is a prime number” is a statement which we can deduce to be true.
K. Erciyes
Chapter 2. Proofs
Abstract
A mathematical system consists of axioms, definitions, theorems and various other structures. A theorem is a proposition that can be proved to be true and an argument that establishes the truth of a statement is called a Proof.
K. Erciyes
Chapter 3. Algorithms
Abstract
Algorithms have been used for a long time, long before the invent of computers, to solve problems in a structured way. An algorithm is a finite set of instructions or logic, written in order, to accomplish a certain predefined task. There are certain requirements from any algorithm; it may or may not receive inputs but some form of output, which is the solution to the problem at hand, is expected. For example, if we want to find the sum of first n positive integers, n is the input to the algorithm, and the sum is the output.
K. Erciyes
Chapter 4. Set Theory
Abstract
Sets are fundamental structures in discrete mathematics. A set consists of elements that may or may not be related. One basic requirement when defining a set is that we should be able to decide whether a given object is an element of a set. For example, if set A consists of odd integers between 0 and 6, we can say 3 is an element and 4 is not an element of this set.
K. Erciyes
Chapter 5. Relations and Functions
Abstract
A set of objects may be related to another set of objects with some similarity. A relation associates an element of a set with an element of another set. Let the set A be consisting of names of persons as David, Jose, Kemal and the set B be the some cities as Istanbul, London and Madrid.
K. Erciyes
Chapter 6. Sequences, Induction and Recursion
Abstract
We review three related topics in this chapter: sequences, induction and recursion. A sequence is an ordered list of elements and is a function from natural number set to a set of real numbers. Summation of sequences may be defined in various ways.
K. Erciyes
Chapter 7. Introduction to Number Theory
Abstract
Number theory is the study of mostly integers and their relations. This branch of mathematics is old and was often thought to have trivial application areas.
K. Erciyes
Chapter 8. Counting and Probability
Abstract
Combinatorics  is a branch of mathematics that studies the configurations and arrangements of objects. Enumeration is one important task dealt in combinatorics to find the number of configurations of objects under consideration and counting is the basic process to perform this task. We need counting when we analyze the complexity of algorithms. We start this chapter by reviewing basic counting methods and then study the basic principles of permutations and combinations which are methods to count the number of ways that a set of objects can be organized. Probabilities of events can be computed using counting principles as we investigate in the second part of this chapter.
K. Erciyes
Chapter 9. Boolean Algebras and Combinational Circuits
Abstract
Boolean  algebra operating on the binary numbers 0 and 1 was first developed by George Boolean in 19th century [1]. A Boolean function is an expression using binary variables. We review basic Boolean algebra laws, duals of these laws, functions and a visual method called Karnaugh-maps to simplify a Boolean expression in the first part of this chapter. We then review combinational circuits in the second part and describe simple structures called logic gates to build a logic circuit to represent a Booelan function. We conclude this chapter by arithmetic circuits to add binary numbers.
K. Erciyes
Chapter 10. Introduction to the Theory of Computation
Abstract
Theory of computation deals with developing mathematical models of computation. This area of research is divided into three subareas: complexity theory, computability theory and automata theory. We mostly review basic structures of automata theory which are languages and finite state automata in this chapter. A language is defined over a set of symbols called an alphabet. A finite state machine is a mathematical tool to model a computing system. Unlike a combinational circuit, a finite state machine has a memory and its behavior and output depends on its current input and its current state. A finite state automata is a finite state machine with no outputs; instead, it has final states called accepting states. A finite state automata can be used to recognize a language conveniently. We review languages, finite state machines, finite state automata, language recognition in this chapter and conclude the first part with the Turing machine named after Alan Turing, which is a more general type of a finite state machine. We then have a short review of complexity theory with the basic complexity classes.
K. Erciyes

Graph Theory

Frontmatter
Chapter 11. Introduction to Graphs
Abstract
Graphs are key data structures that find numerous applications. A graph has a number of nodes some of which are connected. This simple structure can be used to represent many real-life applications such as a road network, communication network and a biological network. In fact, any network may be modeled by a graph and the methods of graph theory can be implemented conveniently to solve various problems in these networks. We define graphs, review types, operations on graphs and graph representations in this chapter to form the basic background for further chapters in this part.
K. Erciyes
Chapter 12. Trees and Traversals
Abstract
A tree is a graph with no cycles. Applications of trees are various; organization of an establishment, a family genealogical relationships can all be represented by a tree. Trees also find a number of applications in computer science, a fundamental usage is the representation of data. We start this chapter with the terminology and properties of trees. We then look at ways of traversing trees and describe specific tree types. In the second part of the chapter, our focus is on methods of tree construction from a general graph. Two basic methods for unweighted graphs are the breadth-first-search and the depth-first-search as we review. For weighted graphs, building an MST tree has many real-life applications as we will see.
K. Erciyes
Chapter 13. Subgraphs
Abstract
In  this chapter, we will review few special subgraphs that find numerous real-life applications. We start with the clique which is a fully connected graph. Finding cliques in a graph is needed to discover closely related nodes of the graph which may be proteins, network nodes or even persons. We then look at a fundamental problem called matching in a graph which is a set of disjoint edges. Independent sets, dominating sets and vertex cover each provide a subset of vertices of a graph with a specific property. We conclude this chapter with another well-known graph problem: vertex coloring. where each vertex should be colored with a different color than its neighbors. All of these problems except matching are NP-hard problems defying solutions in polynomial time.
K. Erciyes
Chapter 14. Connectivity, Network Flows and Shortest Paths
Abstract
Connectivity is a fundamental concept in graph theory as it has both theoretical and practical implications. A graph is called connected if it is possible to reach all vertices from any vertex. Connectivity is related to network flows and matching as we will see. In practice, connectivity is important in reliable communication networks as it has to be provided in loss of edges (links) or vertices (routers) in these networks.
K. Erciyes
Chapter 15. Graph Applications
Abstract
Graphs whether undirected or directed, weighted or unweighted have numerous applications. A graph can be used to represent a network of any kind as we have seen which means any network application can make use of graph theory. We will review such graph application areas centered around networks in this chapter, starting with the analysis of large graphs. These networks are computer networks, ad hoc wireless networks, biological networks and social networks.
K. Erciyes
Backmatter
Metadata
Title
Discrete Mathematics and Graph Theory
Author
Prof. Dr. K. Erciyes
Copyright Year
2021
Electronic ISBN
978-3-030-61115-6
Print ISBN
978-3-030-61114-9
DOI
https://doi.org/10.1007/978-3-030-61115-6

Premium Partner

Neuer Inhalt
    Image Credits