[PDF] [PDF] GRAPH THEORY WITH APPLICATIONS

View - Download [PDF] GRAPH THEORY WITH APPLICATIONS

Previous PDF

Next PDF

GRAPH THEORY

WITH APPLICATIONS

J. A. Bondy and U. S. R. Murty

Department of Combina tories and Optimization,

University of Waterloo,

Ontario,

Canada

NORfH-HOLLAND

New York • Amsterdam • Oxford

@J.A. Bondy and U.S.R. Muny 1976

First published in Great Britain 1976 by

The Macmillan Press Ltd.

First published in the U.S.A. 1976 by

Elsevier Science Publishing

Co., Inc.

52 Vanderbilt Avenue, New York, N.Y. 10017

Fifth Printing, 1982.

Sole Distributor

in the U.S.A:

Elsevier Science Publishing

Co., Inc.

Library

of Congress Cataloging in Publication Data

Bondy, John Adrian.

Graph theory with applications.

Bibliography: p.

lncludes index.

1. Graph theory.

QA166.B67 1979

ISBN 0.:444-19451-7

1. Murty, U.S.R., joint author. II. Title.

511 '.5 75-29826

AU rights reserved. No part of this publication may be reproduced or transmitted, in any form or by any means, without permission.

Printed

in the United States of America

To our parents

Preface

This book is intended as an introduction to graph theory. Our aim bas been to present what we consider to be the basic material, together with a wide variety of applications, both to other branches of mathematics and to real-world problems. Included are simple new proofs of theorems of Brooks, Chvâtal, Tutte and Vizing. The applications have been carefully selected, and are treated in some depth. We have chosen to omit ail so-called 'applications' that employ just the language of graphs and no theory. The applications appearing at the end of each chapter actually make use of theory developed earlier in the same chapter. We have also stressed the importance of efficient methods of solving problems. Several good al gorithms are included and their efficiencies are analysed. We do not, however, go into the computer iinplementation of these algorithms.

The exercises at the

end of each section are of varying difficulty. The harder ones are starred (*) and, for these, hints are provided in appendix I. ln some exercises, new . definitions · are introduced. The reader is recom mended to acquaint himself with these definitions. Other exercises, whose numbers are indicated by bold type, are used in subsequent sections; these should ail be attempted. Appendix II consists of a table in which basic properties of four graphs are listed. When new definitions are introduced,

· the reader may find it

helpful to check bis understanding by referring to this table. Appendix III includes a selection of interesting graphs with special properties. These may prove to be useful in testing new conjectures. In appendix IV, we collect together a number of unsolved problems, some known to be very difficult, and others more hopeful. Suggestions for further reading are given in appendix V.

Many people have contributed, either directly

or indirectly, to this book.

We are particularly indebted to C. Berge and D.

J. ~-Welsh for introducing

us to graph theory, to G. A. Dirac,

J. Edmonds, L. Lovâsz and W. T. Tutte,

whose works have influenced oui-treatment of the subject, to V. Chungphaisan and C. St. J. A. Nash-Williams for their careful reading of the

Preface vii

manuscript and valuable suggestions, and to the ubiquitous G. O. M. for his kindness and constant encouragement.

We also wish to thank

S. B. Maurer, P. J. O'Halloran, C. Thomassen,

B. Toft and our colleagues at the University of Waterloo for many helpful comments, and the National Research Council of Canada for its financial support. Finally, we would like to express our appreciation to Joan Selwood for her excellent typing and Diana Rajnovich for her beautiful artwork.

J. A. Bondy

U.

S. R. Murty

Contents

Pre/ace

1 GRAPHS AND SUBGRAPHS

1.1 Graphs and Simple Graphs .

1.2 Graph Isomorphism

1.3

The Incidence and Adjacency Matrices

1.4

Subgraphs

1.5 Vertex Degrees

1.6

Paths and Connection

1.7 Cycles

Applications

1.8 The Shortest Path Problem.

1.9 Sperner's Lemma.

2 TREES

2.1 Trees

2.2

Cut Edges and Bonds

2.3 Cut Vertices.

2.4

Cayley's Formula .

Applications

2.5 The Connector Problem

3 CONNECTIVITY

3 .1 Connectivity .

3.2 Blocks .

Applications

3.3 Construction of Reliable Communication Networks

4 EULER TOURS AND HAMILTON CYCLES

4.1 Euler Tours .

4.2 Hamilton Cycles .

Applications

4.3 The.Chinese Postman Problem

4.4 The Travelling Salesman Problem

vi 1 4 7 8 10 12 14 15 21
25
27
31
32
36
42
44
47
51
53
62
65

Contents

5 MATCHINGS

5 .1 Matchings

5 .2 Matchings and Coverings in Bipartite Graphs

5.3 Perfect Matchings .

Applications

5.4 The Personnel Assignment Problem ·

5.5 The Optimal Assignment Problem

. 6 EDGE COLOURINGS

6.1 Edge Chromatic Number

6.2 Vizing's Theorem .

Applications

63 The Timetabling Problem

7 INDEPENDENT SETS AND CLIQUES

7.1 Independent Sets .

7.2 Ramsey's Theorem

7 .3

Turan 's Theorem .

Applications

7.4 Schur's Theorem .

7.5 A Geometry Problem .

8 VERTEX COLOURINGS

8.1 Chroniatic Number

8.2 Brooks' Theorem .

8.3 Haj6s'

· Conjecture.

8.4 Chromatic

Polynomial~.

8.5 Girth and Chromatic Number

Applications

8.6 A Storage Problem

9 PLANAR GRAPHS

ix 70
72
76
80
86
91
93
96
. 101 103
. 109 112
113
. .117 . 122 123
125
129
131

9.1 Plane and Planar Graphs 135

9.2 Dual Graphs . 139

9.3 Euler's Formula . . 143

9.4 Bridges . . 145

9.5 Kuratowski's Theorem . . 151

9.6 The Five-Colour Theorem and the Four-Colour Conjecture 156

9.7 Nonhamiltonian Planar Graphs . 160

Applications

9 .8 A Planarity Algorithm . . 163

X

10 DIRECTED GRAPHS

10.1 Directed Graphs .

10.2

Directed Paths

10.3

Directed Cycles

Applications

10.4 A Job Sequencing Problem.

10.5 Designing an Efficient Computer Drum

10.6 Making a Road System One-Way

10.7 Ranking the Participants in a Tournament.

quotesdbs_dbs7.pdfusesText_13

[PDF] graph with 5 vertices of degrees 1

[PDF] graphème definition française

[PDF] graphic design courses in mumbai

[PDF] graphic design curriculum pdf

[PDF] graphic design for visually impaired

[PDF] graphic design manual principles and practice pdf

[PDF] graphic design notes

[PDF] graphic design pdf

[PDF] graphic design portfolio pdf 2019

[PDF] graphic design project pdf

[PDF] graphic design tutorials adobe illustrator pdf

[PDF] graphic equalizer

[PDF] graphics py

[PDF] graphics py colors

[PDF] graphing calculator indefinite integral