图论GraphTheoryTeroHarju_图论面和边的英文资源-CSDN文库

5星 · 超过95%的资源需积分: 11 91 浏览量 2014-06-02 17:25:18 上传评论 1 收藏 689KB PDF 举报

资源推荐

资源详情

资源评论

Lecture Notes on

GRAPH THEORY

Tero Harju

Department of Mathematics

University of Turku

FIN-20014 Turku, Finland

e-mail: harju@utu.ﬁ

2007

Contents

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.1 Graphs and their plane ﬁgures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Paths and cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Connectivity of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.1 Bipartite graphs and trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3 Tours and Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.1 Eulerian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.2 Hamiltonian graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.3 Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4 Colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.1 Edge colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.2 Ramsey Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.3 Vertex colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5 Graphs on Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.1 Planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.2 Colouring planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.3 Genus of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

6 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.1 Digraphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.2 Network Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

1

Introduction

Graph theory can be said to have its beginning in

1736 when EULER considered the (general case of

the) Königsberg bridge problem: Is there a walk-

ing route that crosses each of the seven bridges

of Königsberg exactly once? (Solutio Problema-

tis ad geometriam situs pertinentis, Commentarii

Academiae Scientiarum Imperialis Petropolitanae 8

(1736), pp. 128-140.)

It took 200 years before the ﬁrst book on graph theory was written. This was done by

KÖNIG in 1936. (“Theorie der endlichen und unendlichen Graphen”, Teubner, Leipzig, 1936.

Translation in English, 1990.) Since then graph theory has developed into an extensive and

popular branch of mathematics, which has been applied to many problems in mathematics,

computer science, and other scientiﬁc and not-so-scientiﬁc areas. For the history of early

graph theory, see

N.L. BIGGS, R.J. LLOYD AND R.J. WILSON, “Graph Theory 1736 – 1936”, Clarendon

Press, 1986.

There seem to be no standard notations or even deﬁnitions for graph theoretical objects.

This is natural, because the names one uses for these objects reﬂect the applications. So,

for instance, if we consider a communications network (say, for email) as a graph, then the

computers, which take part in this network, are called nodes rather than vertices or points.

On the other hand, other names are used for molecular structures in chemistry, ﬂow charts in

programming, human relations in social sciences, and so on.

These lectures study ﬁnite graphs and majority of the topics is included in

J.A. BONDY AND U.S.R. MURTY, “Graph Theory with Applications”, Macmillan, 1978.

R. DIESTEL, “Graph Theory”, Springer-Verlag, 1997.

F. HARARY, “Graph Theory”, Addison-Wesley, 1969.

D.B. WEST, “Introduction to Graph Theory”, Prentice Hall, 1996.

R.J. WILSON, “Introduction to Graph Theory”, Longman, (3rd ed.) 1985.

In these lectures we study combinatorial aspects of graphs. For more algebraic topics and

methods, see

N. BIGGS, “Algebraic Graph Theory”, Cambridge University Press, (2nd ed.) 1993.

and for computational aspects, see

S. EVEN, “Graph Algorithms”, Computer Science Press, 1979.

3

In these lecture notes we mention several open problems that have gained respect among

the researchers. Indeed, graph theory has the advantage that it contains easily formulated open

problems that can be stated early in the theory. Finding a solution to any one of these problems

is on another layer of difﬁculty.

Sections with a star (∗) in their heading are optional.

Notations and notions

• For a ﬁnite set X, |X| denotes its size (cardinality, the number of its elements).

• Let

[1, n] = {1, 2, . . . , n},

and in general,

[i, n] = {i, i + 1, . . . , n}

for integers i ≤ n.

• For a real number x, the ﬂoor and the ceiling of x are the integers

⌊x⌋ = max{k ∈ Z | k ≤ x} and ⌈x⌉ = min{k ∈ Z | x ≤ k}.

• A family {X

1

, X

2

, . . . , X

k

} of subsets X

i

⊆ X of a set X is a partition of X, if

X =

[

i∈[1,k]

X

i

and X

i

∩X

j

= ∅ for all different i and j .

• For two sets X and Y ,

X × Y = {(x, y) | x ∈ X, y ∈ Y }

is their Cartesian product.

• For two sets X and Y ,

X△Y = (X \Y ) ∪ (Y \ X)

is their symmetric difference. Here X \ Y = {x | x ∈ X, x /∈ Y }.

• Two numbers n, k ∈ N (often n = |X| and k = |Y | for sets X and Y ) have the same

parity, if both are even, or both are odd, that is, if n ≡ k (mod 2). Otherwise, they have

opposite parity.

Graph theory has abundant examples of NP-complete problems. Intuitively, a problem is

in P

1

if there is an efﬁcient (practical) algorithm to ﬁnd a solution to it. On the other hand,

a problem is in NP

2

, if it is ﬁrst efﬁcient to guess a solution and then efﬁcient to check that

this solution is correct. It is conjectured (and not known) that P 6= NP. This is one of the

great problems in modern mathematics and theoretical computer science. If the guessing in

NP-problems can be replaced by an efﬁcient systematic search for a solution, then P=NP. For

any one NP-complete problem, if it is in P, then necessarily P=NP.

1

Solvable – by an algorithm – in polynomially many steps on the size of the problem instances.

2

Solvable nondeterministically in polynomially many steps on the size of the problem instances.

1.1 Graphs and their plane ﬁgures 4

1.1 Graphs and their plane ﬁgures

Let V be a ﬁnite set, and denote by

E(V ) = {{u, v} | u, v ∈ V, u 6= v} .

the subsets of V of two distinct elements.

DEFINITION. A pair G = (V, E) with E ⊆ E(V ) is called a graph (on V ). The elements

of V are the vertices, and those of E the edges of the graph. The vertex set of a graph G is

denoted by V

G

and its edge set by E

G

. Therefore G = (V

G

, E

G

).

In literature, graphs are also called simple graphs; vertices are called nodes or points; edges

are called lines or links. The list of alternatives is long (but still ﬁnite).

A pair {u, v} is usually written simply as uv. Notice that then uv = vu. In order to

simplify notations, we also write v ∈ G instead of v ∈ V

G

.

DEFINITION. For a graph G, we denote

ν

G

= |V

G

| and ε

G

= |E

G

| .

The number ν

G

of the vertices is called the order of G, and ε

G

is the size of G. For an edge

e = uv ∈ E

G

, the vertices u and v are its ends. Vertices u and v are adjacent or neighbours,

if e = uv ∈ E

G

. Two edges e

1

= uv and e

2

= uw having a common end, are adjacent with

each other.

A graph G can be represented as a plane ﬁgure by drawing

a line (or a curve) between the points u and v (representing

vertices) if e = uv is an edge of G. The ﬁgure on the right is

a drawing of the graph G with V

G

= {v

1

, v

2

, v

3

, v

4

, v

5

, v

6

}

and E

G

= {v

1

v

2

, v

1

v

3

, v

2

v

3

, v

2

v

4

, v

5

v

6

}.

v

1

v

2

v

3

v

4

v

5

v

6

Often we shall omit the identities (names v) of the vertices in our ﬁgures, in which case

the vertices are drawn as anonymous circles.

Graphs can be generalized by allowing loops vv and parallel (or multiple) edges between

vertices to obtain a multigraph G = (V, E, ψ), where E = {e

1

, e

2

, . . . , e

m

} is a set (of

symbols), and ψ : E → E(V ) ∪ {vv | v ∈ V } is a function that attaches an unordered pair of

vertices to each e ∈ E: ψ(e) = uv.

Note that we can have ψ(e

1

) = ψ(e

2

). This is drawn in the

ﬁgure of G by placing two (parallel) edges that connect the

common ends. On the right there is (a drawing of) a multi-

graph G with vertices V = {a, b, c} and edges ψ(e

1

) = aa,

ψ(e

2

) = ab, ψ(e

3

) = bc, and ψ(e

4

) = bc.

a

b

c

剩余98页未读，继续阅读

内容反馈

allen-99

2014-09-21

很给力，老师推荐的，对于研究图论的的同学帮助很大。

CommanderKiller

粉丝: 0
资源: 9

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip