Introduction to graph theory / Vitaly I. Voloshin.

Format:

Book

Author/Creator:

Voloshin, Vitaly I. (Vitaly Ivanovich), 1954-

Language:

English

Subjects (All):

Graph theory.

Physical Description:

1 online resource (160 p.)

Edition:

1st ed.

Place of Publication:

New York : Nova Science Publishers, c2009.

Language Note:

English

Summary:

Graph Theory is an important area of contemporary mathematics with many applications in computer science, genetics, chemistry, engineering, industry, business and in social sciences. It is a young science invented and developing for solving challenging problems of 'computerised' society for which traditional areas of mathematics such as algebra or calculus are powerless. This book is for math and computer science majors, for students and representatives of many other disciplines (like bioinformatics, for example) taking the courses in graph theory, discrete mathematics, data structures, algorithms.It is also for anyone who wants to understand the basics of graph theory, or just is curious. No previous knowledge in graph theory or any other significant mathematics is required. The very basic facts from set theory, proof techniques and algorithms are sufficient to understand it; but even those are explained in the text. The book discusses the key concepts of graph theory with emphasis on trees, bipartite graphs, cycles, chordal graphs, planar graphs and graph colouring.The reader is conducted from the simplest examples, definitions and concepts, step by step, towards an understanding of a few most fundamental facts in the field.

Contents:

Intro

INTRODUCTION TO GRAPH THEORY

Contents

Preface

Chapter 1Basic Definitions and Concepts

1.1. Fundamentals

1.2. Graph Modeling Applications

1.3. Graph Representations

1.4. Generalizations

1.5. Basic Graph Classes

1.6. Basic Graph Operations

1.7. Basic Subgraphs

1.8. Separation and Connectivity

Chapter 2Trees and Bipartite Graphs

2.1. Trees and Cyclomatic Number

2.2. Trees and Distance

2.3. Minimum Spanning Tree

2.4. Bipartite Graphs

Chapter 3Chordal Graphs

3.1. Preliminary

3.2. Separators and Simplicial Vertices

3.3. Degrees

3.4. Distances in Chordal Graphs

3.5. Quasi-triangulated Graphs

Chapter 4Planar Graphs

4.1. Plane and Planar Graphs

4.2. Euler's Formula

4.3. K5 and K3,3 Are not Planar Graphs

4.4. Kuratowski's Theorem and Planarity Testing

4.5. Plane Triangulations and Dual Graphs

Chapter 5Graph Coloring

5.1. Preliminary

5.2. Definitions and Examples

5.3. Structure of Colorings

5.4. Chromatic Polynomial

5.5. Coloring Chordal Graphs

5.6. Coloring Planar Graphs

5.7. Perfect Graphs

5.8. Edge Coloring and Vizing's Theorem

5.9. Upper Chromatic Index

Chapter 6Graph Traversals and Flows

6.1. Eulerian Graphs

6.2. Hamiltonian Graphs

6.3. Network Flows

Chapter 7Appendix

7.1. What Is Mathematical Induction

7.2. Graph Theory Algorithms and Their Complexity

7.3. Answers and Hints to Selected Exercises

7.4. Glossary of Additional Concepts

References

Index.

Notes:

Description based upon print version of record.

Includes bibliographical references (p. [139]) and index.

Description based on print version record.

ISBN:

1-61470-113-X

OCLC:

756501382