文献翻译模板

西安科技大学

< /p>

毕业设计

(

论文

)

文献翻译

题

目

图论知识在计算机科学中的应用研究与实现

院、系

(

部

)

计

算

机

学

院

专业及班级

信息与计算科学

080

班

姓

名

樊

璐

指

导教

师

宇

亚

卫

日

期

2012

年

2

月

英文

In

mathematics

and

computer

science,

graph

theory

is

the

study

of

graphs,

mathematical

structures

used

to

model

pairwise

relations

between

objects

from

a

certain collection. A

and a collection of edges that connect pairs of vertices. A graph may be undirected,

meaning

that

there

is

no

distinction

between

the

two

vertices

associated

with

each

edge, or its edges may be directed from one vertex to another; see graph (mathematics)

for more detailed definitions and for other variations in the types of graphs that are

commonly

considered.

The

graphs

studied

in

graph

theory

should

not

be

confused

with graphs of functions or other kinds of graphs.

Graphs are one of the prime objects of study in Discrete Mathematics. Refer to

Glossary of graph theory for basic definitions in graph theory.

History

The K?

nigsberg Bridge problem

The paper written by

Leonhard Euler on the Seven Bridges of K?

nigsberg and

published in 1736 is regarded as the first paper in the history of graph theory.

[1]

This

paper, as well as the one written by Vandermonde on the knight problem, carried on

with

the

analysis

situs

initiated

by

Leibniz.

Euler's

formula

relating

the

number

of

edges,

vertices,

and

faces

of

a

convex

polyhedron

was

studied

and

generalized

by

Cauchy

[2]

and L'Huillier,

[3]

and is at the origin of topology.

More

than

one

century

after

Euler's

paper

on

the

bridges

of

K?

nigsberg

and

while

Listing

introduced

topology,

Cayley

was

led

by

the

study

of

particular

analytical forms arising from differential calculus to study a particular class of graphs,

the

trees.

This

study

had

many

implications

in

theoretical

chemistry.

The

involved

techniques mainly concerned the enumeration of graphs having particular properties.

Enumerative graph theory then rose from the results of Cayley and the fundamental

results published by Pó

lya between 1935 and 1937 and the generalization of these by

De Bruijn in 1959. Cayley linked his results on trees with the contemporary studies of

chemical composition.

[4]

The fusion of the ideas coming from mathematics with those

coming from chemistry is at the origin of a part of the standard terminology of graph

theory.

In particular, the term

in

1878

in

Nature,

where

he

draws

an

analogy

between

invariants

and

[5]

precisely identical with a Kekulé

an diagram or chemicograph. [...] I give a rule

for the geometrical multiplication of graphs, i.e. for constructing a graph to the

product of in- or co- variants whose separate graphs are given. [...]

in the original).

One

of

the

most

famous

and

productive

problems

of

graph

theory

is

the

four

color

problem:

it

true

that

any

map

drawn

in

the

plane

may

have

its

regions

colored with four colors, in such a way that any two regions having a common border

have different colors?

its first written record is in a letter of De Morgan addressed to Hamilton the same year.

Many incorrect proofs have been proposed, including those by Cayley,

Kempe, and

others. The study and the generalization of this problem by Tait, Heawood, Ramsey

and Hadwiger led to the study of the colorings of the graphs embedded on surfaces

with

arbitrary

genus.

Tait's

reformulation

generated

a

new

class

of

problems,

the

factorization

problems,

particularly

studied

by

Petersen

and

K

?

nig.

The

works

of

Ramsey on colorations and more specially the results obtained by Turá

n in 1941 was

at the origin of another branch of graph theory, extremal graph theory.

The

four

color

problem

remained

unsolved

for

more

than

a

century.

In

1969

Heinrich Heesch published a method

for solving the problem using computers.

[6]

A

computer-aided

proof

produced

in

1976

by

Kenneth

Appel

and

Wolfgang

Haken

makes fundamental use of the notion of

[7][8]

The

proof involved checking the properties of 1,936 configurations by computer, and was

not fully accepted at the time due to its complexity. A simpler proof considering only

633 configurations was given twenty years later by Robertson, Seymour, Sanders and

Thomas.

[9]

The autonomous development of topology from 1860 and 1930 fertilized graph

theory

back

through

the

works

of

Jordan,

Kuratowski

and

Whitney.

Another

important

factor

of

common

development

of

graph

theory

and

topology

came

from

the use of the techniques of modern algebra. The first example of such a use comes

from

the

work

of

the

physicist

Gustav

Kirchhoff,

who

published

in

1845

his

Kirchhoff's circuit laws for calculating the voltage and current in electric circuits.

The introduction of probabilistic methods in graph theory, especially in the study

of Erd

?

s and Ré

nyi of the asymptotic probability of graph connectivity, gave rise to

yet another branch, known as random graph theory, which has been a fruitful source

of graph-theoretic results.

Drawing graphs

Main article: Graph drawing

Graphs are represented graphically by drawing a dot or circle for every vertex,

and

drawing

an

arc

between

two

vertices

if

they

are

connected

by

an

edge.

If

the

graph is directed, the direction is indicated by drawing an arrow.

A

graph

drawing

should

not

be

confused

with

the

graph

itself

(the

abstract,

non-visual structure) as there are several ways to structure the graph drawing. All that

matters is which vertices are connected to which others by how many edges and not

the exact layout. In practice it is often difficult to decide if two drawings represent the

same graph. Depending on the problem domain some layouts may be better suited and

easier to understand than others.

[edit] Graph-theoretic data structures

Main article: Graph (data structure)

There are different ways to store graphs in a computer system. The data structure

used depends on both the graph structure and the algorithm used for manipulating the

graph.

Theoretically

one

can

distinguish

between

list

and

matrix

structures

but

in

concrete applications the best structure is often a combination of both. List structures

are

often

preferred

for

sparse

graphs

as

they

have

smaller

memory

requirements.

Matrix

structures

on

the

other

hand

provide

faster

access

for

some

applications

but

can consume huge amounts of memory.

List structures

Incidence list

The edges are represented by an array containing pairs (tuples if directed)

of

vertices

(that

the

edge

connects)

and

possibly

weight

and

other

data.

Vertices connected by an edge are said to be adjacent.

Adjacency list

Much like the incidence list, each vertex has a list of which vertices it is

adjacent

to.

This

causes

redundancy

in

an

undirected

graph:

for

example,

if

vertices

A

and

B

are

adjacent,

A's

adjacency

list

contains

B,

while

B's

list

contains A. Adjacency queries are faster, at the cost of extra storage space.