Introduction to Graph Theory, Richard J. Trudeau.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：6.18M 资料格式：pdf 举报版权申诉

ce543116-0987-40ed-98bb-e97d037d6a50.pdf-第1页.png

第1页 / 共242页

ce543116-0987-40ed-98bb-e97d037d6a50.pdf-第2页.png

第2页 / 共242页

ce543116-0987-40ed-98bb-e97d037d6a50.pdf-第3页.png

第3页 / 共242页

ce543116-0987-40ed-98bb-e97d037d6a50.pdf-第4页.png

第4页 / 共242页

ce543116-0987-40ed-98bb-e97d037d6a50.pdf-第5页.png

第5页 / 共242页

ce543116-0987-40ed-98bb-e97d037d6a50.pdf-第6页.png

第6页 / 共242页

ce543116-0987-40ed-98bb-e97d037d6a50.pdf-第7页.png

第7页 / 共242页

ce543116-0987-40ed-98bb-e97d037d6a50.pdf-第8页.png

第8页 / 共242页

Half Title

Title Page

Dedication

Contents

Preface

1. Pure Mathematics

Introduction

Euclidean Geometry as Pure Mathematics

Games

Why Study Pure Mathematics?

What’s Coming

Suggested Reading

2. Graphs

Introduction

Sets

Paradox

Graphs

Graph Diagrams

Cautions

Common Graphs

Discovery

Complements and Subgraphs

Isomorphism

Recognizing Isomorphic Graphs

Semantics

The Number of Graphs Having a Given v

Exercises

Suggested Reading

3. Planar Graphs

Introduction

UG, K5, and the Jordan Curve Theorem

Are There More Nonplanar Graphs?

Expansions

Kuratowski’s Theorem

Determining Whether a Graph is Planar or Nonplanar

Exercises

Suggested Reading

4. Euler’s Formula

Introduction

Mathematical Induction

Proof of Euler’s Formula

Some Consequences of Euler’s Formula

Algebraic Topology

Exercises

Suggested Reading

5. Platonic Graphs

Introduction

Proof of the Theorem

History

Exercises

Suggested Reading

6. Coloring

Chromatic Number

Coloring Planar Graphs

Proof of the Five Color Theorem

Coloring Maps

Exercises

Suggested Reading

7. The Genus of a Graph

Introduction

The Genus of a Graph

Euler’s Second Formula

Some Consequences

Estimating the Genus of a Connected Graph

g-Platonic Graphs

The Heawood Coloring Theorem

Exercises

Suggested Reading

8. Euler Walks and Hamilton Walks

Introduction

Euler Walks

Hamilton Walks

Multigraphs

The Königsberg Bridge Problem

Exercises

Suggested Reading

Afterword

Solutions to Selected Exercises

Index

Special symbols

INTRODUCTION TO GRAPH THEORY

INTRODUCTION TO GRAPH THEORY Richard J. Trudeau DOVER PUBLICATIONS, INC. New York

Copyright © 1993 by Richard J. Trudeau. Copyright © 1976 by the Kent State University Press. All rights reserved. Copyright Bibliographical Note This Dover edition, first published in 1993, is a slightly corrected, enlarged republication of the work first published by The Kent State University Press, Kent, Ohio, 1976. For this edition the author has added a new section, “Solutions to Selected Exercises,” and corrected a few typographical and graphical errors. Library of Congress Cataloging-in-Publication Data Trudeau, Richard J. Introduction to graph theory / Richard J. Trudeau. p. cm. Rev. ed. of: Dots and lines, 1976. Includes bibliographical references and index. ISBN-13: 978-0-486-67870-2 ISBN-10: 0-486-67870-9 1. Graph theory. I. Trudeau, Richard J. Dots and lines. II. Title. QA166.T74 1993 511'.5—dc20 93-32996 CIP Manufactured in the United States by Courier Corporation 67870908 www.doverpublications.com

To Dick Barbieri and Chet Raymo

TABLE OF CONTENTS Preface 1. PURE MATHEMATICS Introduction . . . Euclidean Geometry as Pure Mathematics . . . Games . . . Why Study Pure Mathematics? . . . What’s Coming . . . Suggested Reading 2. GRAPHS Introduction . . . Sets . . . Paradox . . . Graphs . . . Graph Diagrams . . . Cautions . . . Common Graphs . . . Discovery . . . Complements and Subgraphs . . . Isomorphism . . . Recognizing Isomorphic Graphs . . . Semantics . . . The Number of Graphs Having a Given v . . . Exercises . . . Suggested Reading 3. PLANAR GRAPHS Introduction . . . UG, K5, and the Jordan Curve Theorem . . . Are There More Nonplanar Graphs? . . . Expansions . . . Kuratowski’s Theorem . . . Determining Whether a Graph is Planar or Nonplanar . . . Exercises . . . Suggested Reading 4. EULER’S FORMULA Introduction . . . Mathematical Induction . . . Proof of Euler’s Formula . . . Some Consequences of Euler’s Formula . . . Algebraic Topology . . . Exercises . . . Suggested Reading 5. PLATONIC GRAPHS Introduction . . . Proof of the Theorem . . . History . . . Exercises . . . Suggested Reading 6. COLORING Chromatic Number . . . Coloring Planar Graphs . . . Proof of the Five Color Theorem . . . Coloring Maps . . . Exercises . . . Suggested Reading 7. THE GENUS OF A GRAPH

Introduction . . . The Genus of a Graph . . . Euler’s Second Formula . . . Some Consequences . . . Estimating the Genus of a Connected Graph . . . g- Platonic Graphs . . . The Heawood Coloring Theorem . . . Exercises . . . Suggested Reading 8. EULER WALKS AND HAMILTON WALKS Introduction . . . Euler Walks . . . Hamilton Walks . . . Multigraphs . . . The Königsberg Bridge Problem . . . Exercises . . . Suggested Reading Afterword Solutions to Selected Exercises Index Special symbols

PREFACE This book is about pure mathematics in general, and the theory of graphs in particular. (“Graphs” are networks of dots and lines;* they have nothing to do with “graphs of equations.”) I have interwoven the two topics, the idea being that the graph theory will illustrate what I have to say about the nature and spirit of pure mathematics, and at the same time the running commentary about pure mathematics will clarify what we do in graph theory. I have three types of reader in mind. First, and closest to my heart, the mathematically traumatized. If you are such a person, if you had or are having a rough time with mathematics in school, if you feel mathematically stupid but wish you didn’t, if you feel there must be something to mathematics if only you knew what it was, then there’s a good chance you’ll find this book helpful. It presents mathematics under a different aspect. For one thing, it deals with pure mathematics, whereas school mathematics (geometry excepted) is mostly applied mathematics. For another, it is a more qualitative than quantitative study, so there are few calculations. Second, the mathematical hobbyist. I think graph theory makes for marvelous recreational mathematics; it is intuitively accessible and rich in unsolved problems. Third, the serious student of mathematics. Graph theory is the oldest and most geometric branch of topology, making it a natural supplement to either a geometry or topology course. And due to its wide applicability, it is currently quite fashionable. The book uses some algebra. If you’ve had a year or so of high school algebra that should be enough. Remembering specifics is not so important as having a general familiarity with equations and inequalities. Also, the discussion in Chapter 1 presupposes some experience with plane geometry. Again no specific knowledge is required, just a feeling for how the game is played.

分享到：

赞收藏

资料库

Introduction to Graph Theory, Richard J. Trudeau.pdf

相关推荐

课程资源

热门标签

最新资料