图论导引习题答案IntroductiontoGraphTheorysolutionmanual第二版

习题答案

5星 · 超过95%的资源需积分: 45 13 浏览量 2019-01-04 11:53:19 上传评论 19 收藏 3.36MB PDF 举报

资源详情

资源评论

i ii

INTRODUCTION TO GRAPH THEORY

SECOND EDITION (2001)

SOLUTION MANUAL

SUMMER 2005 VERSION



DOUGLAS B. WEST

MATHEMATICS DEPARTMENT

UNIVERSITY OF ILLINOIS

or transmitted in any form without permission.

NOTICE

This is the Summer 2005 version of the Instructor’s Solution Manual for

Introduction to Graph Theory, by Douglas B. West. A few solutions have

been added or clariﬁed since last year’s version.

Also present is a (slightly edited) annotated syllabus for the one-

semester course taught from this book at the University of Illinois.

This version of the Solution Manual contains solutions for 99.4% of

the problems in Chapters 1–7 and 93% of the problems in Chapter 8. The

author believes that only Problems 4.2.10, 7.1.36, 7.1.37, 7.2.39, 7.2.47,

and 7.3.31 in Chapters 1–7 are lacking solutions here. There problems are

too long or difﬁcult for this text or use concepts not covered in the text; they

will be deleted in the third edition.

The positions of solutions that have not yet been written into the ﬁles

are occupied by the statements of the corresponding problems. These prob-

lems retain the

(−), (!), (+), (∗) indicators. Also (•) is added to introduce

the statements of problems without other indicators. Thus every problem

whose solution is not included is marked by one of the indicators, for ease

of identiﬁcation.

The author hopes that the solutions contained herein will be useful to

instructors. The level of detail in solutions varies. Instructors should feel

free to write up solutions with more or less detail according to the needs of

the class. Please do not leave solutions posted on the web.

Due to time limitations, the solutions have not been proofread or edited

as carefully as the text, especially in Chapter 8. Please send corrections to

west@math.uiuc.edu. The author thanks Fred Galvin in particular for con-

tributing improvements or alternative solutions for many of the problems

in the earlier chapters.

This will be the last version of the Solution Manual for the second

edition of the text. The third edition will have many new problems, such

as those posted at http://www.math.uiuc.edu/ west/igt/newprob.html . The

effort to include all solutions will resume for the third edition. Possibly

other pedagogical features may also be added later.

Inquiries may be sent to west@math.uiuc.edu. Meanwhile, the author

apologizes for any inconvenience caused by the absence of some solutions.

Douglas B. West

iii Solutions Preface iv

Mathematics Department - University of Illinois

MATH 412

SYLLABUS FOR INSTRUCTORS

Text: West, Introduction to Graph Theory, second edition,

Prentice Hall, 2001.

Many students in this course see graph algorithms repeatedly in

courses in computer science. Hence this course aims primarily to improve

students’ writing of proofs in discrete mathematics while learning about

the structure of graphs. Some algorithms are presented along the way, and

many of the proofs are constructive. The aspect of algorithms emphasized

in CS courses is running time; in a mathematics course in graph theory

from this book the algorithmic focus is on proving that the algorithms work.

Math 412 is intended as a rigorous course that challenges students to

think. Homework and tests should require proofs, and most of the exercises

in the text do so. The material is interesting, accessible, and applicable;

most students who stick with the course will give it a fair amount of time

and thought.

An important aspect of the course is the clear presentation of solutions,

which involves careful writing. Many of the problems in the text have hints,

either where the problem is posed or in Appendix C (or both). Producing

a solution involves two main steps: ﬁnding a proof and properly writing

it. It is generally beneﬁcial to the learning process to provide “collabora-

tive study sessions” in which students can discuss homework problems in

small groups and an instructor or teaching assistant is available to answer

questions and provide direction. Students should then write up clear and

complete solutions on their own.

This course works best when students have had prior exposure to

writing proofs, as in a “transition” course. Some students may need fur-

ther explicit discussions of the structure of proofs. Such discussion appear

in many texts, such as

D’Angelo and West, Mathematical Thinking: Problem-Solving and Proofs;

Eisenberg, The Mathematical Method: A Transition to Advanced Mathematics;

Fletcher/Patty, Foundations of Higher Mathematics;

Galovich, Introduction to Mathematical Structures;

Galovich, Doing Mathematics: An Introduction to Proofs and Problem Solving;

Solow, How to Read and Do Proofs.

Suggested Schedule

The subject matter for the course is the ﬁrst seven chapters of the text,

skipping most optional material. Modiﬁcations to this are discussed below.

The 22 sections are allotted an average of slightly under two lectures each.

In the exercises, problems designated by (−) are easier or shorter than

most, often good for tests or for “warmup” before doing homework problems.

Problems designated by

(+) are harder than most. Those designated by (!)

are particularly instructive, entertaining, or important. Those designated

(∗) make use of optional material.

The semester at the University of Illinois has 43 ﬁfty-minute lectures.

The ﬁnal two lectures are for optional topics, usually chosen by the students

from topics in Chapter 8.

Chapter 1 Fundamental Concepts 8

Chapter 2 Trees and Distance 5.5

Chapter 3 Matchings and Factors 5.5

Chapter 4 Connectivity and Paths 6

Chapter 5 Graph Coloring 6

Chapter 6 Planar Graphs 5

Chapter 7 Edges and Cycles 5

* Total 41

Optional Material

No later material requires material marked optional. The “optional”

marking also suggests to students that the ﬁnal examination will not cover

that material.

The optional subsections on Disjoint Spanning Trees (Bridg-It) in Sec-

tion 2.1 and Stable Matchings in Section 3.2 are always quite popular with

the students. The planarity algorithm (without proof) in 6.2 is appealing

to students, as is the notion of embedding graphs on the torus through

Example 6.3.21. Our course usually includes these four items.

The discussion of

f -factors in Section 3.3 is also very instructive and

is covered when the class is proceeding on schedule. Other potential addi-

tions include the applications of Menger’s Theorem at 4.2.24 or 4.2.25.

Other items marked optional generally should not be covered in class.

Additional text items not marked optional that can be skipped when

behind schedule:

1.1: 31, 35 1.2: 16, 21–23 1.3: 24, 31–32 1.4: 1, 4, 7, 25–26

2.1: 8, 14–16 2.2: 13–19 2.3: 7–8 3.2: 4

4.1: 4–6 4.2: 20–21 5.1: 11, 22(proof) 5.3: 10–11, 16(proof)

6.1: 18–20, 28 6.3: 9–10, 13–15 7.2: 17

v Solutions Preface vi

Comments

There are several underlying themes in the course, and mentioning

these at appropriate moments helps establish continuity. These include

1) TONCAS (The Obvious Necessary Condition(s) are Also Sufﬁcient).

2) Weak duality in dual maximation and minimization problems.

3) Proof techniques such as the use of extremality, the paradigm for induc-

tive proofs of conditional statements, and the technique of transforming a

problem into a previously solved problem.

Students sometimes ﬁnd it strange that so many exercises concern

the Petersen graph. This is not so much because of the importance of the

Petersen graph itself, but rather because it is a small graph and yet has

complex enough structure to permit many interesting exercises to be asked.

Chapter 1. In recent years, most students enter the course having

been exposed to proof techniques, so reviewing these in the ﬁrst ﬁve sec-

tions has become less necessary; remarks in class can emphasis techniques

as reminders. To minimize confusion, digraphs should not be mentioned

until section 1.4; students absorb the additional model more easily after

becoming comfortable with the ﬁrst.

1.1: p3-6 contain motivational examples as an overview of the course;

this discussion should not extend past the ﬁrst day no matter where it

ends (the deﬁnitions are later repeated where needed). The material on

the Petersen graph establishes its basic properties for use in later examples

and exercises.

1.2: The deﬁnitions of path and cycle are intended to be intuitive; one

shouldn’t dwell on the heaviness of the notation for walks.

1.3: Although characterization of graphic sequences is a classical topic,

some reviewers have questioned its importance. Nevertheless, here is a

computation that students enjoy and can perform.

1.4: The examples are presented to motivate the model; these can be

skipped to save time. The de Bruijn graph is a classical application. It is

desirable to present it, but it takes a while to explain.

Chapter 2.

2.1: Characterization of trees is a good place to ask for input from the

class, both in listing properties and in proving equivalence.

2.2: The inductive proof for the Pr

ufer correspondence seems to be

easier for most students to grasp than the full bijective proof; it also illus-

trates the usual type of induction with trees. Most students in the class

have seen determinants, but most have considerable difﬁculty understand-

ing the proof of the Matrix Tree Theorem; given the time involved, it is best

just to state the result and give an example (the next edition will include

a purely inductive proof that uses only determinant expansion, not the

Cauchy-Binet Formula). Students ﬁnd the material on graceful labelings

enjoyable and illuminating; it doesn’t take long, but also it isn’t required.

The material on branchings should certaily be skipped in this course.

2.3: Many students have seen rooted trees in computer science and

ﬁnd ordinary trees unnatural; Kruskal’s algorithm should clarify the dis-

tinction. Many CS courses now cover the algorithms of Kruskal, Dijkstra,

and Huffman; here cover Kruskal and perhaps Dijkstra (many students

have seen the algorithm but not a proof of correctness), and skip Huffman.

Chapter 3.

3.1: Skip “Dominating Sets”, but present the rest of the section.

3.2: Students ﬁnd the Hungarian algorithm difﬁcult; explicit examples

need to be worked along with the theoretical discussion of the equality

subgraph. “Stable Matchings” is very popular with students and should be

presented unless far behind in schedule. Skip “Faster Bipartite Matching”.

3.3: Present all of the subsection on Tutte’s 1-factor Theorem. The

material on

f -factors is intellectually beautiful and leads to one proof of

the Erd

os-Gallai conditions, but it is not used again in the course and is an

“aside”. Skip everything on Edmonds’ Blossom Algorithm: matching algo-

rithms in general graphs are important algorithmically but would require

too much time in this course; this is “recommended reading”.

Chapter 4.

4.1: Students have trouble distinguishing “k-connected” from “connec-

tivity

k” and “bonds” from “edge cuts”. Bonds are dual to cycles in the

matroidal sense; there are hints of this in exercises and in Chapter 7, but

the full duality cannot be explored before Chapter 8.

4.2: Students ﬁnd this section a bit difﬁcult. The proof of 4.2.10 is

similar to that of 4.2.7, making it omittable, but the application in 4.2.14

is appealing. The details of 4.2.20-21 can be skipped or treated lightly,

since the main issue is the local version of Menger’s theorem. 4.2.24-25 are

appealing applications that can be added; 4.2.5 (CSDR) is a fundamental

result but takes a fair amount of effort.

4.3: The material on network ﬂow is quite easy but can take a long

time to present due to the overhead of deﬁning new concepts. The basic

idea of 4.3.13-15 should be presented without belaboring the details too

much. 4.3.16 is a more appealing application that perhaps makes the point

more effectively. Skip “Supplies and Demands”.

vii Solutions Preface viii

Chapter 5.

5.1: If time is short, the proof of 5.1.22 (Brooks’ Theorem) can be merely

sketched.

5.2: Be sure to cover Tur

an’s Theorem. Presentation of Dirac’s The-

orem in 5.2.20 is valuable as an application of the Fan Lemma (Menger’s

Theorem). The subsequent material has limited appeal to undergraduates.

5.3: The inclusion-exclusion formula for the chromatic polynomial is

derived here (5.3.10) without using inclusion-exclusion, making it accessi-

ble to this class without prerequisite. However, this proof is difﬁcult for

students to follow in favor of the simple inclusion-exclusion proof, which

will be optional since that formula is not prerequisite for the course. Hence

this formula should be omitted unless students know inclusion-exclusion.

Chordal graphs and perfect graphs are more important, but these can also

be treated lightly if short of time. Skip “Counting Acyclic Orientations”.

Chapter 6.

6.1: The technical deﬁnitions of objects in the plane should be treated

very lightly. It is better to be informal here, without writing out formal

deﬁnitions unless explicitly requested by students. Outerplanar graphs

are useful as a much easier class on which to solve problems (exercises!)

like those on planar graphs; 6.18-20 are fundamental observations about

outerplanar graphs, but other items are more important if time is short.

6.1.28 (polyhedra) is an appealing application but can be skipped.

6.2: The preparatory material 6.2.4-7 on Kuratowski’s Theorem can be

presented lightly, leaving the annoying details as reading; the subsequent

material on convex embedding of 3-connected graphs is much more inter-

esting. Presentation of the planarity algorithm is appealing but optional;

skip the proof that it works.

6.3: The four color problem is popular; for undergraduates, show the

ﬂaw in Kempe’s proof (p271), but don’t present the discharging rule un-

less ahead of schedule. Students ﬁnd the concept of crossing number easy

to grasp, but the results are fairly difﬁcult; try to go as far as the recur-

sive quartic lower bound for the complete graph. The edge bound and its

geometric application are impressive but take too much time for under-

graduates. The idea of embeddings on surfaces can be conveyed through

the examples in 6.3.21 on the torus. Interested students can be advised to

read the rest of this section.

Chapter 7.

7.1: The proof of Vizing’s Theorem is one of the more difﬁcult in the

course, but undergraduates can gain follow it when it is presented with

sufﬁcient colored chalk. The proof can be skipped if short of time. Skip

“Characterization of Line Graphs”, although if time and interest is plenti-

ful the necessity of Krausz’s condition can be explained.

7.2: Chv

atal’s theorem (7.2.13) is not as hard to present as it looks if

the instructor has the statement and proof clearly in mind. Nevertheless,

the proof is somewhat technical and can be skipped (the same can be said

of 7.2.17). More appealing is the Chv

atal–Erd

os Theorem (7.2.19), which

certainly should be presented. Skip “Cycles in Directed Graphs”.

7.3: The theorems of Tait and Grinberg make a nice culmination to

the required material of the course. Skip “Snarks” and “Flows and Cycle

Covers”. Nevertheless, these are lively topics that can be recommended for

advanced students.

Chapter 8. If time permits, material from the ﬁrst part of sections of

Chapter 8 can be presented to give the students a glimpse of other topics.

The best choices for conveying some understanding in a brief treatment are

Section 8.3 (Ramsey Theory or Sperner’s Lemma) and Section 8.5 (Random

Graphs). Also possible are the Gossip Problem (or other items) from Sec-

tion 8.4 and some of the optional material from earlier chapters. The ﬁrst

part of Section 8.1 (Perfect Graphs) may also be usable for this purpose if

perfect graphs have been discussed in Section 5.3. Sections 8.2 and 8.6 re-

quire more investment in preliminary material and thus are less suitable

for giving a “glimpse”.

1 Chapter 1: Fundamental Concepts Section 1.1: What Is a Graph? 2

1.FUNDAMENTAL CONCEPTS

1.1. WHAT IS A GRAPH?

1.1.1. Complete bipartite graphs and complete graphs. The complete bipar-

tite graph

m,n

is a complete graph if and only if m = n = 1 or {m, n} = {1, 0}.

1.1.2. Adjacency matrices and incidence matrices for a 3-vertex path.

0 1 1

1 0 0

0 1 0

1 0 1

0 1 0

0 0 1

1 1 0

1 1

1 0

0 1

1 1

0 1

1 0

1 1

0 1

1 1

1 0

0 1

1 1

0 1

1 0

1 1

Adjacency matrices for a path and a cycle with six vertices.







0 1 0 0 0 0

1 0 1 0 0 0

0 1 0 1 0 0

0 0 1 0 1 0

0 0 0 1 0 1

0 0 0 0 1 0













0 1 0 0 0 1

1 0 1 0 0 0

0 1 0 1 0 0

0 0 1 0 1 0

0 0 0 1 0 1

1 0 0 0 1 0







1.1.3. Adjacency matrix for K

m,n

m n

0 1

n 1 0

1.1.4.

∼

H if and only if G

∼

H. If f is an isomorphism from G to H ,

then

f is a vertex bijection preserving adjacency and nonadjacency, and

hence

f preserves non-adjacency and adjacency in G and is an isomor-

phism from

G to H . The same argument applies for the converse, since the

complement of

G is G.

1.1.5. If every vertex of a graph

G has degree 2, then G is a cycle—FALSE.

Such a graph can be a disconnected graph with each component a cycle. (If

inﬁnite graphs are allowed, then the graph can be an inﬁnite path.)

1.1.6. The graph below decomposes into copies of

•

1.1.7. A graph with more than six vertices of odd degree cannot be decom-

posed into three paths. Every vertex of odd degree must be the endpoint

of some path in a decomposition into paths. Three paths have only six

endpoints.

1.1.8. Decompositions of a graph. The graph below decomposes into copies

1,3

with centers at the marked vertices. It decomposes into bold and

solid copies of

as shown.

•

• •

•

• •

•

1.1.9. A graph and its complement. With vertices labeled as shown, two

vertices are adjacent in the graph on the right if and only if they are not

adjacent in the graph on the left.

•

• •

•

• •

•

b c

f g

•

• •

•

• •

•

f d

h b

1.1.10. The complement of a simple disconnected graph must be connected—

TRUE. A disconnected graph

G has vertices x, y that do not belong to a

path. Hence

x and y are adjacent in G. Furthermore, x and y have no com-

mon neighbor in

G, since that would yield a path connecting them. Hence

剩余259页未读，继续阅读

评论收藏

内容反馈

qq_35982500

2019-04-08

非常非常非常好

图论导引习题答案 Introduction to Graph Theory solution manual 第二版

评论1

最新资源

图论导引习题答案 Introduction to Graph Theory solution manual 第二版

评论1

最新资源

相关推荐

图论习题答案

introduction to graph theory

图论导引答案.pdf

华章数学译丛18 图论导引 原书第2版 中英文附答案

Introduction to Graph Theory

Introduction to Graph Theory, Robin Wilson

introduction to graph theoty（fourth edition）

图论导引[美]韦斯特

图论，第5版[免费预览]Graph Theory, 5th Edition [Free Preview]

《图论导引》(英文版)

《深入理解计算系统》 第二版的习题答案 CSAPP instructor's solution manual 2ed

计算理论导引第三版课后习题答案Introduction-to-the-Theory-of-Computation-Solutions

《组合数学引论》孙淑玲、许胤龙，版本讲义部分课后习题答案

组合数学Introductory Combinatorics-第五版部分章节课后习题答案

Introduction to Graph Theory-Dover (1994) by Richard J. Trudeau

Introduction to Graph Theory (2nd Edition) by Douglas B. West

Introduction to Graph Theory -- H3 Mathematics, K. M. Koh

组合学与图论概论An Introduction to Combinatorics and Graph Theory

图论引导 中文

图论引导中文版

Introduction_to_Graph_Theory

华章数学译丛18 图论导引 原书第2版+中英文.rar

10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20

图论（王树禾）作业答案

经典书籍：An Introduction to the Theory of Graph Spectra PDF版

Introduction to Graph Theory 2nd edition [d. b. west] PDF 书签+目录

matlab图论工具箱（Graph Theory Toolbox）

华章数学译丛18 图论导引原书第2版中英文附答案

《深入理解计算系统》第二版的习题答案 CSAPP instructor's solution manual 2ed

图论引导中文

华章数学译丛18 图论导引原书第2版+中英文.rar