Graphs Theory and Applications E-Book

Jean-Claude Fournier

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 404

Veröffentlichungsjahr: 2013

Beschreibung

This book provides a comprehensive and pedagogical introduction to graph theory and its applications. It contains all the standard basic material and develops significant topics and applications, such as: colorings and the timetabling problem, matchings and the optimal assignment problem, and Hamiltonian cycles and the travelling salesman problem, to name but a few. Exercises at various levels are given at the end of each chapter, and a final chapter presents a few general problems with hints for solutions, thus providing the reader with the opportunity to test and refine their knowledge on the subject. An appendix outlines the basis of computational complexity theory, in particular the definition of NP-completeness, which is essential for algorithmic applications.

Leseprobe

Table of Contents

Introduction

Chapter 1. Basic Concepts

1.1 The origin of the graph concept

1.2 Definition of graphs

1.3 Subgraphs

1.4 Paths and cycles

1.5 Degrees

1.6 Connectedness

1.7 Bipartite graphs

1.8 Algorithmic aspects

1.9 Exercises

Chapter 2. Trees

2.1 Definitions and properties

2.2 Spanning trees

2.3 Application: minimum spanning tree problem

2.4 Connectivity

2.5 Exercises

Chapter 3. Colorings

3.1 Coloring problems

3.2 Edge coloring

3.3 Algorithmic aspects

3.4 The timetabling problem

3.5 Exercises

Chapter 4. Directed Graphs

4.1 Definitions and basic concepts

4.2 Acyclic digraphs

4.3 Arborescences

4.4 Exercises

Chapter 5. Search Algorithms

5.1 Depth-first search of an arborescence

5.2 Optimization of a sequence of decisions

5.3 Depth-first search of a digraph

5.4 Exercises

Chapter 6. Optimal Paths

6.1 Distances and shortest paths problems

6.2 Case of non-weighted digraphs: breadth-first search

6.3 Digraphs without circuits

6.4 Application to scheduling

6.5 Positive lengths

6.6 Other cases

6.7 Exercises

Chapter 7. Matchings

7.1 Matchings and alternating paths

7.2 Matchings in bipartite graphs

7.3 Assignment problem

7.4 Optimal assignment problem

7.5 Exercises

Chapter 8. Flows

8.1 Flows in transportation networks

8.2 The max-flow min-cut theorem

8.3 Maximum flow algorithm

8.4 Flow with stocks and demands

8.5 Revisiting theorems

8.6 Exercises

Chapter 9. Euler Tours

9.1 Euler trails and tours

9.2 Algorithms

9.3 The Chinese postman problem

9.4 Exercises

Chapter 10. Hamilton Cycles

10.1 Hamilton cycles

10.2 The traveling salesman problem

10.3 Approximation of a difficult problem

10.4 Approximation of the metric TSP

10.5 Exercises

Chapter 11. Planar Representations

11.1 Planar graphs

11.2 Other graph representations

11.3 Exercises

Chapter 12. Problems with Comments

12.1 Problem 1: A proof of k-connectivity

12.2 Problem 2: An application to compiler theory

12.3 Problem 3: Kernel of a digraph

12.4 Problem 4: Perfect matching in a regular bipartite graph

12.5 Problem 5: Birkhoff-Von Neumann’s theorem

12.6 Problem 6: Matchings and tilings

12.7 Problem 7: Strip mining

Appendix A. Expression of Algorithms

A.1 Algorithm

A.2 Explanations and commentaries

A.3 Other algorithms

A.4 Comments

Appendix B. Bases of Complexity Theory

B.1 The concept of complexity

B.2 Class P

B.3 Class NP

B.4 NP-complete problems

B.5 Classification of problems

B.6 Other approaches to difficult problems

Bibliography

Index

First published in France in 2006 by Hermes Science/Lavoisier entitled Théorie des graphes et applications, avec exercices et problèmes © LAVOISIER, 2006

First published in Great Britain and the United States in 2009 by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUKJohn Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USAwww.iste.co.ukwww.wiley.com

© ISTE Ltd, 2009

The rights of Jean-Claude Fournier to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Fournier, Jean-Claude.

[Théorie des graphes et applications, avec exercices et problèmes. English]

Graph theory and applications with exercises and problems / Jean-Claude Fournier.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-84821-070-7

1. Graph theory. 2. Graph theory--Problems, exercises, etc. I. Title.

QA166.F68513 2009 511'.5--dc22

2008043204

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN: 978-1-84821-070-7

To Hugo, Eliott, Mathieu,Elise, Aurélie, Antonin, Ethanand those to come…

Introduction

The concept of a graph is relatively recent since it only formally appeared during the 20th century. Today it has become essential in many fields, in particular in applied and fundamental computer science, in optimization, and in algorithmic complexity. The study of graphs and their applications therefore provides an opportunity to deal with very diverse questions with numerous applications. It can be used, for example, to develop task scheduling methods from optimal paths in graphs, or properties of communication networks in relation to the connectedness of graphs. Historically, graphs were considered long before the theory was developed, with famous problems such as the Königsberg bridge problem (presented in Chapter 9).

This work studies the principal aspects of graph theory with special emphasis on major applications. Its content is aimed at advanced undergraduate and students beginning post-graduate studies in mathematics and computer science. It calls for very few pre-requisites, essentially a familiarity with basic vocabulary and mathematical reasoning. In return, the study of this new subject will be a great opportunity for students to test and improve their personal logic. Graph theory is indeed a new subject, which is very different from the traditional mathematics taught, but which requires the same intellectual rigor. The great novelty of this subject may throw even the best students in mathematics, which shows how beneficial studying this subject can be!

This book, conceived as a textbook, is the result of long experience teaching bachelor and masters level students (notably as part of the French master in applied information technology: “MIAGE”). It also contains many exercises and problems classified in five levels of increasing difficulty:

1. Certain points and quite easy proofs are left to the reader’s initiative. They are indicated in the margin by a †.

2. Among the exercises given at the end of each chapter, some are marked with a +, indicating a useful complement to the chapter, which may also be used elsewhere in the text.

3. The exercises which are not marked are of normal difficulty. They are standard exercises, among which you will find the most classic in the field.

4. The exercises marked with a * are more difficult. They go into a subject in more depth than the chapter does.

5. A last level with a few problems is given at the end, with commentaries and sometimes hints for their resolution (Chapter 12).

Here is some information on how this book is organized. Except for the two chapters on definitions and basic concepts, which are Chapter 1 for undirected graphs and Chapter 4 for directed graphs, each chapter presents a specific subject with a major application, and is therefore relatively independent from the other chapters. It is therefore possible to make choices when organizing a course. Statements are presented according to their role and their importance in the theory, using the classic terminology: theorems, propositions, corollaries and lemmas. This terminology can be defined as follows: a theorem is an important result which is significant for the theory, a proposition is less prominent, a corollary is a result which can be deduced directly from a major result, a lemma is a result with a certain technical nature, which usually is used to prove another result. The end of the proof of a statement is marked by the symbol .

Graphs, as already mentioned, are used a lot in applications. Many problems are thereby solved in a constructive manner, which leads to writing algorithms, which may then be written in an appropriate programming language. Some of these algorithms are not simple, so it is important to express them in the best structured way possible, which will make the process of writing them in a program easier. In this work we wanted not to neglect, and even to make explicit, this algorithmic aspect, and that is why we cover in detail in Appendix A the method used to express algorithms. Similarly, in Appendix B, we give the bases of what it has become essential to know today for any scientific development, that is the theory of algorithmic complexity. It is impossible to discuss an algorithm without discussing its complexity! However, this assumes at least a good knowledge of the basic classes of the theory of complexity, which are therefore presented in Appendix B. Experience shows that it is still difficult to count on what should normally have been learned elsewhere.

There is today an important body of literature on graphs and their applications. We give only some bibliographic references here, and the reader will find more complete bibliographies within the works cited in the references. Some are relatively old references but they are works that are still interesting today and which have fed our own thoughts in their time and to which we are indebted. We want to recommend in particular Berge [2], a work which, with some others by the same author, is still today a principal reference in graph theory. Some more specific references are also given in the course of the text.

We wish to thank Nicolas Thiant for his very useful contribution to the ultimate verification of the French manuscript. Thanks also to Anne Picard-Pieter and Amit Pieter for undertaking the difficult and delicate task of translating the original French version. In addition, we thank Rebecca Edge for meticulously performing the final proofreading. Finally, we are very grateful to Guillaume and Julie Fournier who have so kindly contributed to finalizing the French and English manuscripts.

Jean-Claude Fournier

Chapter 1

Basic Concepts

After an introduction to the origin of graph conceptualization, this first chapter presents the definitions and basic properties of graph theory. This will be continued a bit later (Chapter 4) with directed graphs. Since graphs are used in many areas, in particular in computer science, the definitions and sometimes the terminology may vary in the literature. In a sense, graphs are victims of their own success! The definitions and terminology chosen here are what seem the most appropriate and the most in line with theory tradition (specifically references [1] and [2]). However, the reader is warned that he may find some differences. We have to know this even if it has no real practical consequences because the concepts remain, of course, the same.

1.1 The origin of the graph concept

Dots and lines linking some dots on a plane: such is the “naïve” view of a “graph”. This is already enough to imagine almost everything that this concept can represent in various areas. One example that first comes to mind is a communication network: dots representing the centers or nodes of the network, lines representing the links. Many questions can be asked with this network “model”, for example: does this network make it possible for all centers to communicate with one another? In other words, is it possible to reach any given center from another one, directly or going through intermediate centers? Again, given two centers, find the paths linking them, and in particular the “shortest path”, that is, the one with the lowest number of intermediary links. This last question may be widened when a numerical value is associated with the link showing a distance between points, or a time, a cost, etc. The length of a path will then consist of the sum of the values of the lines composing it. The shortest path will then be the shortest length path among those linking the two dots being considered. This gives an image of what is called a “weighted graph”.

This first example of modeling a communication network with a graph is an application that is particularly obvious. There are other problems which can be modeled with a graph but in a less obvious way. For example, let us consider this rather amusing little problem: a ferryman has to take a wolf, a goat and a cabbage across a river. He can only take one of them across at a time and cannot leave the wolf and the goat alone on one bank of the river (for obvious reasons), nor the goat and the cabbage. How can he proceed to take all of them across? Is there more than one way to solve the problem? Is there one way which is faster than the others? Since there are only a few possibilities, it is quite easy to answer these questions, but it might be interesting to think about similar but more serious problems and try to apply a general and systematic research method. This will be based on modeling the problem with a graph, which is not really difficult but requires a little more imagination than with the communication network (this model is proposed as an exercise at the end of this chapter).