Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2017 | Book

Graphs and Their Applications Read chapter Read first chapter

Basic Graph Theory

Author: Md. Saidur Rahman

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
insite
SEARCH

About this book

This undergraduate textbook provides an introduction to graph theory, which has numerous applications in modeling problems in science and technology, and has become a vital component to computer science, computer science and engineering, and mathematics curricula of universities all over the world.

The author follows a methodical and easy to understand approach. Beginning with the historical background, motivation and applications of graph theory, the author first explains basic graph theoretic terminologies. From this firm foundation, the author goes on to present paths, cycles, connectivity, trees, matchings, coverings, planar graphs, graph coloring and digraphs as well as some special classes of graphs together with some research topics for advanced study.

Filled with exercises and illustrations, Basic Graph Theory is a valuable resource for any undergraduate student to understand and gain confidence in graph theory and its applications to scientific research, algorithms and problem solving.

Table of Contents

Frontmatter
Chapter 1. Graphs and Their Applications
Abstract
A graph consists of a set of vertices and set of edges, each joining two vertices. Usually an object can be represented by a vertex and a relationship between two objects is represented by an edge. In this chapter we go through some applications of graphs in solving real-world problems.
Md. Saidur Rahman
Chapter 2. Basic Graph Terminologies
Abstract
In this chapter, we learn some definitions of basic graph theoretic terminologies and know some preliminary results of graph theory.
Md. Saidur Rahman
Chapter 3. Paths, Cycles, and Connectivity
Abstract
In this chapter, we study some important fundamental concepts of graph theory. In Section 3.1 we start with the definitions of walks, trails, paths, and cycles. The well-known Eulerian graphs and Hamiltonian graphs are studied in Sections 3.2 and 3.3, respectively. In Section 3.4, we study the concepts of connectivity and connectivity-driven graph decompositions.
Md. Saidur Rahman
Chapter 4. Trees
Abstract
A tree is a connected graph that contains no cycle. In this chapter we know some properties of trees which are useful for solving computational problems on trees.
Md. Saidur Rahman
Chapter 5. Matching and Covering
Abstract
In this chapter we study matchings, vertex cover, independent set, dominating set and factor of a graph with their real-world applications.
Md. Saidur Rahman
Chapter 6. Planar Graphs
Abstract
A graph is planar if it can be drawn or embedded in the plane so that no two edges intersect geometrically except at a vertex to which they are both incident. In this chapter we study planar graphs.
Md. Saidur Rahman
Chapter 7. Graph Coloring
Abstract
Probably graph coloring concept naturally arose from its application in map coloring: given a map containing several countries, we wish to color the countries in the map in such a way that neighboring countries receive different colors to make the countries distinct. In this chapter we know about vertex coloring, edge coloring, chromatic number, chromatic index, chromatic polynomial, etc.
Md. Saidur Rahman
Chapter 8. Digraphs
Abstract
A graph is usually called a directed graph or a digraph if its edges have directions. The concept of directed graphs has many applications in solving real-world problems. In this chapter we study some properties of digraphs.
Md. Saidur Rahman
Chapter 9. Special Classes of Graphs
Abstract
In this chapter, we know about some special classes of graphs. Special classes of graphs play important roles in graph algorithmic studies. When we find a computationally hard problem for general graphs, we try to solve those problems for special classes of graphs.
Md. Saidur Rahman
Chapter 10. Some Research Topics
Abstract
In this chapter, we introduce some research areas where the students learning graph theory may find interest. Since graphs have applications in modeling many real-world problems, a researcher in graph theory can work on fundamental properties of graphs as well as developing graph models for practical applications and on devising efficient algorithms.
Md. Saidur Rahman
Backmatter
Metadata
Title
Basic Graph Theory
Author
Md. Saidur Rahman
Copyright Year
2017
Electronic ISBN
978-3-319-49475-3
Print ISBN
978-3-319-49474-6
DOI
https://doi.org/10.1007/978-3-319-49475-3

Premium Partner

    Image Credits