Second level
Third level
Fourth level
Fifth level
‹date/time›
‹footer›
‹#›
------=_NextPart_01C586BD.B5F06A20
Content-Location: file:///C:/26832652/ch12_files/master04.xml
Content-Transfer-Encoding: quoted-printable
Content-Type: text/xml; charset="utf-8"
Graphs
Chapter 12
Chapter 12: Graphs
2
Graph Terminology
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•A graph i=
s a data
structure that consists of a set of vertices and a set of edges between pa=
irs
of vertices
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•Edges rep=
resent
paths or connections between the vertices
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•The set of
vertices and the set of edges must both be finite and neither one be empty=
Chapter 12: Graphs
3
Visual Representation of Graphs
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•Vertices =
are
represented as points or labeled circles and edges are represented as lines
joining the vertices
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•The physi=
cal
layout of the vertices and their labeling are not relevant
![](3D"slide0007_image002.jpg")
Chapter 12: Graphs
4
Directed and Undirected Graphs
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•The edges=
of a
graph are directed if the existence of an edge from A to B does not
necessarily guarantee that there is a path in both directions
<=
/div>
•A graph wi=
th
directed edges is called a directed graph
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•A graph w=
ith
undirected edges is an undirected graph or simply a graph
<=
nobr>
![](3D"slide0008_image004.jpg")
Chapter 12: Graphs
5
Directed and Undirected Graphs
(continued)
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•The edges=
in a
graph may have values associated with them known as their weights
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•A graph w=
ith
weighted edges is known as a weighted graph
![](3D"slide0009_image006.jpg")
Chapter 12: Graphs
6
Paths and Cycles
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•A vertex =
is
adjacent to another vertex if there is an edge to it from that other
vertex
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•A path is=
a
sequence of vertices in which each successive vertex is adjacent to its
predecessor
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•In a simp=
le path,
the vertices and edges are distinct except that the first and last vertex =
may
be the same
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•A cycle i=
s a
simple path in which only the first and final vertices are the same
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•If a grap=
h is not
connected, it is considered unconnected, but will still consist of connect=
ed
endpoints
Chapter 12: Graphs
7
![](3D"slide0011_image008.jpg")
![](3D"slide0011_image011.gif")
Paths and Cycles (continued)
Chapter 12: Graphs
8
The Graph ADT and Edge Class
&#=
8226;In
making our own, we need to be able to do the following
&=
#8226;Create
a graph with the specified number of vertices
&=
#8226;Iterate
through all of the vertices in the graph
•Iterate
through the vertices that are adjacent to a specified vertex
&=
#8226;Determine
whether an edge exists between two vertices
&=
#8226;Determine
the weight of an edge between two vertices
&=
#8226;Insert
an edge into the graph
Chapter 12: Graphs
9
The Graph ADT and Edge Class
(continued)
![](3D"slide0013_image013.jpg")
Chapter 12: Graphs
10
Implementing the Graph ADT
&#=
8226;Because
graph algorithms have been studied and implemented throughout the history =
of
computer science, many of the original publications of graph algorithms and
their implementations did not use an object-oriented approach and did not =
even
use abstract data types
•Edges are represented by an array of lists call=
ed adjacency
lists, where each list stores the vertices adjacent to a particular
vertex
&#=
8226;Edges
are represented by a two dimensional array, called an adjacency matrix
Chapter 12: Graphs
11
Adjacency List
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•An adjace=
ncy list
representation of a graph uses an array of lists
<=
nobr>
Chapter 12: Graphs
12
Adjacency List (continued)
![](3D"slide0016_image015.jpg")
Chapter 12: Graphs
13
Adjacency List (continued)
![](3D"slide0037_image017.jpg")
Chapter 12: Graphs
14
Adjacency Matrix
<=
nobr>•Uses a
two-dimensional array to represent a graph
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•For an un=
weighted
graph, the entries can be Boolean values
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•For a wei=
ghted
graph, the matrix would contain the weights
<=
nobr>
![](3D"slide0017_image019.jpg")
Chapter 12: Graphs
15
Traversals of Graphs
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•Most graph
algorithms involve visiting each vertex in a systematic order
<=
/div>
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•Most comm=
on
traversal algorithms are the breadth first and depth first search
<=
nobr>
Chapter 12: Graphs
16
Breadth-First Search
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•In a
breadth-first search, we visit the start first, then all nodes that are
adjacent to it next, then all nodes that can be reached by a path from the
start node containing two edges, three edges, and so on
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•Must visi=
t all
nodes for which the shortest path from the start node is length k before we
visit any node for which the shortest path from the start node is length
k+1
Chapter 12: Graphs
17
Depth-First Search
•In depth-first search, you start at a
vertex, visit it, and choose one adjacent vertex to visit; then, choose a
vertex adjacent to that vertex to visit, and so on until you go no further; then back up a=
nd see
whether a new vertex can be found
![](3D"slide0026_image021.jpg")
‹header›
‹date/time›=
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
‹footer›
‹#›
------=_NextPart_01C586BD.B5F06A20
Content-Location: file:///C:/26832652/ch12_files/master04_stylesheet.css
Content-Transfer-Encoding: base64
Content-Type: text/css
Ym9keQ0KCXt3aWR0aDo1MzRweDsNCgloZWlnaHQ6NDAwcHg7fQ0KLlRCDQoJe21zby1zcGVjaWFs
LWZvcm1hdDpub2J1bGxldFwyMDIyO30NCi5UDQoJe3RleHQtYWxpZ246Y2VudGVyOw0KCWZvbnQt
ZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFyaWFsOw0KCWNvbG9yOmJsYWNr
Ow0KCW1zby1jb2xvci1pbmRleDozOw0KCWZvbnQtc2l6ZToxNTIlOw0KCW1zby1jaGFyLXdyYXA6
MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5CQg0KCXttc28tc3BlY2lhbC1mb3JtYXQ6
YnVsbGV0XDIwMjI7fQ0KLkINCgl7dGV4dC1hbGlnbjpqdXN0aWZ5Ow0KCWZvbnQtZmFtaWx5OkFy
aWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFyaWFsOw0KCWNvbG9yOmJsYWNrOw0KCW1zby1j
b2xvci1pbmRleDoxOw0KCWZvbnQtc2l6ZToxMTQlOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28t
a2luc29rdS1vdmVyZmxvdzoxO30NCi5CMUINCgl7bXNvLXNwZWNpYWwtZm9ybWF0OmJ1bGxldFwy
MDIyO30NCi5CMQ0KCXt0ZXh0LWFsaWduOmxlZnQ7DQoJZm9udC1mYW1pbHk6QXJpYWw7DQoJbXNv
LWJpZGktZm9udC1mYW1pbHk6QXJpYWw7DQoJY29sb3I6YmxhY2s7DQoJbXNvLWNvbG9yLWluZGV4
OjE7DQoJZm9udC1zaXplOjExNCU7DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1zby1raW5zb2t1LW92
ZXJmbG93OjE7fQ0KLkIyQg0KCXttc28tc3BlY2lhbC1mb3JtYXQ6YnVsbGV0XDIwMjI7fQ0KLkIy
DQoJe3RleHQtYWxpZ246bGVmdDsNCglmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250
LWZhbWlseTpBcmlhbDsNCgljb2xvcjpibGFjazsNCgltc28tY29sb3ItaW5kZXg6MTsNCglmb250
LXNpemU6OTUlOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30N
Ci5CM0INCgl7bXNvLXNwZWNpYWwtZm9ybWF0OmJ1bGxldFwyMDEzO30NCi5CMw0KCXt0ZXh0LWFs
aWduOmxlZnQ7DQoJZm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJp
YWw7DQoJY29sb3I6YmxhY2s7DQoJbXNvLWNvbG9yLWluZGV4OjE7DQoJZm9udC1zaXplOjg1JTsN
Cgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9DQouQjRCDQoJe21z
by1zcGVjaWFsLWZvcm1hdDpidWxsZXRcMDBCQjt9DQouQjQNCgl7dGV4dC1hbGlnbjpsZWZ0Ow0K
CWZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFyaWFsOw0KCWNvbG9y
OmJsYWNrOw0KCW1zby1jb2xvci1pbmRleDoxOw0KCWZvbnQtc2l6ZTo3NiU7DQoJbXNvLWNoYXIt
d3JhcDoxOw0KCW1zby1raW5zb2t1LW92ZXJmbG93OjE7fQ0KLk5CDQoJe21zby1zcGVjaWFsLWZv
cm1hdDpub2J1bGxldFwyMDIyO30NCi5ODQoJe3RleHQtYWxpZ246bGVmdDsNCglmb250LWZhbWls
eTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWlseTpBcmlhbDsNCgljb2xvcjpibGFjazsNCglt
c28tY29sb3ItaW5kZXg6MTsNCglmb250LXNpemU6NTclOw0KCW1zby1jaGFyLXdyYXA6MTsNCglt
c28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5OMUINCgl7bXNvLXNwZWNpYWwtZm9ybWF0Om5vYnVs
bGV0XDIwMjI7fQ0KLk4xDQoJe3RleHQtYWxpZ246bGVmdDsNCglmb250LWZhbWlseTpBcmlhbDsN
Cgltc28tYmlkaS1mb250LWZhbWlseTpBcmlhbDsNCgljb2xvcjpibGFjazsNCgltc28tY29sb3It
aW5kZXg6MTsNCglmb250LXNpemU6NTclOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29r
dS1vdmVyZmxvdzoxO30NCi5OMkINCgl7bXNvLXNwZWNpYWwtZm9ybWF0Om5vYnVsbGV0XDIwMjI7
fQ0KLk4yDQoJe3RleHQtYWxpZ246bGVmdDsNCglmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlk
aS1mb250LWZhbWlseTpBcmlhbDsNCgljb2xvcjpibGFjazsNCgltc28tY29sb3ItaW5kZXg6MTsN
Cglmb250LXNpemU6NTclOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1vdmVyZmxv
dzoxO30NCi5OM0INCgl7bXNvLXNwZWNpYWwtZm9ybWF0Om5vYnVsbGV0XDIwMjI7fQ0KLk4zDQoJ
e3RleHQtYWxpZ246bGVmdDsNCglmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZh
bWlseTpBcmlhbDsNCgljb2xvcjpibGFjazsNCgltc28tY29sb3ItaW5kZXg6MTsNCglmb250LXNp
emU6NTclOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5O
NE4NCgl7bXNvLXNwZWNpYWwtZm9ybWF0Om5vYnVsbGV0XDIwMjI7fQ0KLk40DQoJe3RleHQtYWxp
Z246bGVmdDsNCglmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWlseTpBcmlh
bDsNCgljb2xvcjpibGFjazsNCgltc28tY29sb3ItaW5kZXg6MTsNCglmb250LXNpemU6NTclOw0K
CW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5PQg0KCXttc28t
c3BlY2lhbC1mb3JtYXQ6bm9idWxsZXRcMjAyMjt9DQouTw0KCXt0ZXh0LWFsaWduOmxlZnQ7DQoJ
Zm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7DQoJY29sb3I6
YmxhY2s7DQoJbXNvLWNvbG9yLWluZGV4OjE7DQoJZm9udC1zaXplOjg1JTsNCgltc28tY2hhci13
cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9DQouTzENCgl7Zm9udC1mYW1pbHk6QXJp
YWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1z
by1raW5zb2t1LW92ZXJmbG93OjE7fQ0KLk8yDQoJe2ZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1i
aWRpLWZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1v
dmVyZmxvdzoxO30NCi5PMw0KCXtmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZh
bWlseTpBcmlhbDsNCgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9
DQouTzQNCgl7Zm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7
DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1zby1raW5zb2t1LW92ZXJmbG93OjE7fQ0KLkNCQg0KCXtt
c28tc3BlY2lhbC1mb3JtYXQ6bm9idWxsZXRcMjAyMjt9DQouQ0INCgl7dGV4dC1hbGlnbjpjZW50
ZXI7DQoJZm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7DQoJ
Y29sb3I6YmxhY2s7DQoJbXNvLWNvbG9yLWluZGV4OjE7DQoJZm9udC1zaXplOjExNCU7DQoJbXNv
LWNoYXItd3JhcDoxOw0KCW1zby1raW5zb2t1LW92ZXJmbG93OjE7fQ0KLkNCMUINCgl7bXNvLXNw
ZWNpYWwtZm9ybWF0Om5vYnVsbGV0XDIwMjI7fQ0KLkNCMQ0KCXtmb250LWZhbWlseTpBcmlhbDsN
Cgltc28tYmlkaS1mb250LWZhbWlseTpBcmlhbDsNCglmb250LXNpemU6MTE0JTsNCgltc28tY2hh
ci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9DQouQ0IyDQoJe2ZvbnQtZmFtaWx5
OkFyaWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFyaWFsOw0KCWZvbnQtc2l6ZTo5NSU7DQoJ
bXNvLWNoYXItd3JhcDoxOw0KCW1zby1raW5zb2t1LW92ZXJmbG93OjE7fQ0KLkNCMw0KCXtmb250
LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWlseTpBcmlhbDsNCglmb250LXNpemU6
ODUlOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5DQjQN
Cgl7Zm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7DQoJZm9u
dC1zaXplOjc2JTsNCgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9
DQouQ1RCDQoJe21zby1zcGVjaWFsLWZvcm1hdDpub2J1bGxldFwyMDIyO30NCi5DVA0KCXt0ZXh0
LWFsaWduOmNlbnRlcjsNCglmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWls
eTpBcmlhbDsNCgljb2xvcjpibGFjazsNCgltc28tY29sb3ItaW5kZXg6MzsNCglmb250LXNpemU6
MTUyJTsNCgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9DQouSEIN
Cgl7dGV4dC1hbGlnbjpqdXN0aWZ5Ow0KCWZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZv
bnQtZmFtaWx5OkFyaWFsOw0KCWZvbnQtc2l6ZTo5NSU7DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1z
by1raW5zb2t1LW92ZXJmbG93OjE7fQ0KLkhCMUINCgl7bXNvLXNwZWNpYWwtZm9ybWF0OmJ1bGxl
dFwyMDIyO30NCi5IQjENCgl7Zm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1p
bHk6QXJpYWw7DQoJZm9udC1zaXplOjk1JTsNCgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtpbnNv
a3Utb3ZlcmZsb3c6MTt9DQouSEIyDQoJe2ZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZv
bnQtZmFtaWx5OkFyaWFsOw0KCWZvbnQtc2l6ZTo4NSU7DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1z
by1raW5zb2t1LW92ZXJmbG93OjE7fQ0KLkhCMw0KCXtmb250LWZhbWlseTpBcmlhbDsNCgltc28t
YmlkaS1mb250LWZhbWlseTpBcmlhbDsNCglmb250LXNpemU6NzYlOw0KCW1zby1jaGFyLXdyYXA6
MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5IQjQNCgl7Zm9udC1mYW1pbHk6QXJpYWw7
DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7DQoJZm9udC1zaXplOjY2JTsNCgltc28tY2hh
ci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9DQouUUINCgl7dGV4dC1hbGlnbjpq
dXN0aWZ5Ow0KCWZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFyaWFs
Ow0KCWZvbnQtc2l6ZTo4NSU7DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1zby1raW5zb2t1LW92ZXJm
bG93OjE7fQ0KLlFCMUINCgl7bXNvLXNwZWNpYWwtZm9ybWF0OmJ1bGxldFwyMDIyO30NCi5RQjEN
Cgl7Zm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7DQoJZm9u
dC1zaXplOjg1JTsNCgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9
DQouUUIyDQoJe2ZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFyaWFs
Ow0KCWZvbnQtc2l6ZTo3NiU7DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1zby1raW5zb2t1LW92ZXJm
bG93OjE7fQ0KLlFCMw0KCXtmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWls
eTpBcmlhbDsNCglmb250LXNpemU6NjYlOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29r
dS1vdmVyZmxvdzoxO30NCi5RQjQNCgl7Zm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9u
dC1mYW1pbHk6QXJpYWw7DQoJZm9udC1zaXplOjU3JTsNCgltc28tY2hhci13cmFwOjE7DQoJbXNv
LWtpbnNva3Utb3ZlcmZsb3c6MTt9DQouVGJsDQoJe3RleHQtYWxpZ246anVzdGlmeTsNCglmb250
LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWlseTpBcmlhbDsNCglmb250LXNpemU6
OTUlOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5UYmwx
Qg0KCXttc28tc3BlY2lhbC1mb3JtYXQ6bm9idWxsZXRcMjAyMjt9DQouVGJsMQ0KCXtmb250LWZh
bWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWlseTpBcmlhbDsNCglmb250LXNpemU6OTUl
Ow0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5UYmwyDQoJ
e2ZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFyaWFsOw0KCWZvbnQt
c2l6ZTo4NSU7DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1zby1raW5zb2t1LW92ZXJmbG93OjE7fQ0K
LlRibDMNCgl7Zm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7
DQoJZm9udC1zaXplOjc2JTsNCgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZs
b3c6MTt9DQouVGJsNA0KCXtmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWls
eTpBcmlhbDsNCglmb250LXNpemU6NjYlOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29r
dS1vdmVyZmxvdzoxO30NCi5kZWZhdWx0Qg0KCXttc28tc3BlY2lhbC1mb3JtYXQ6bm9idWxsZXRc
MjAyMjt9DQouZGVmYXVsdA0KCXt0ZXh0LWFsaWduOmxlZnQ7DQoJZm9udC1mYW1pbHk6QXJpYWw7
DQoJbXNvLWFzY2lpLWZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFy
aWFsOw0KCWZvbnQtd2VpZ2h0Om5vcm1hbDsNCglmb250LXN0eWxlOm5vcm1hbDsNCgl0ZXh0LWRl
Y29yYXRpb246bm9uZTsNCgl0ZXh0LXNoYWRvdzpub25lOw0KCXRleHQtZWZmZWN0Om5vbmU7DQoJ
bXNvLWZhcmVhc3QtaGludDpubzsNCglsYXlvdXQtZmxvdzpob3Jpem9udGFsOw0KCWNvbG9yOmJs
YWNrOw0KCW1zby1jb2xvci1pbmRleDoxOw0KCWZvbnQtc2l6ZTo4NSU7DQoJbXNvLXRleHQtcmFp
c2U6MCU7DQoJbXNvLWxpbmUtc3BhY2luZzoiMTAwIDAgMCI7DQoJbXNvLW1hcmdpbi1sZWZ0LWFs
dDowOw0KCW1zby10ZXh0LWluZGVudC1hbHQ6MDsNCgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtp
bnNva3Utb3ZlcmZsb3c6MTsNCglkaXJlY3Rpb246bHRyOw0KCW1zby13b3JkLXdyYXA6MTsNCglt
c28tdmVydGljYWwtYWxpZ24tc3BlY2lhbDpiYXNlbGluZTsNCgltc28tYW5zaS1sYW5ndWFnZTpF
Ti1VUzt9DQphOmxpbmsNCgl7Y29sb3I6IzAwOTk5OSAhaW1wb3J0YW50O30NCmE6YWN0aXZlDQoJ
e2NvbG9yOiMzMzMzOTkgIWltcG9ydGFudDt9DQphOnZpc2l0ZWQNCgl7Y29sb3I6Izk5Q0MwMCAh
aW1wb3J0YW50O30NCn==
------=_NextPart_01C586BD.B5F06A20
Content-Location: file:///C:/26832652/ch12_files/script.js
Content-Transfer-Encoding: quoted-printable
Content-Type: application/javascript; charset="us-ascii"
function LoadSld()
{
var sld=3DGetObj("SlideObj")
if( !g_supportsPPTHTML ) { =09
sld.style.visibility=3D"visible"
return
}
if( MakeNotesVis() ) return
runAnimations =3D _InitAnimations();
=09
if( IsWin("PPTSld") )
parent.SldUpdated(GetSldId())
g_origSz=3DparseInt(SlideObj.style.fontSize)
g_origH=3Dsld.style.posHeight
g_origW=3Dsld.style.posWidth
g_scaleHyperlinks=3D(document.all.tags("AREA").length>0)
if( g_scaleHyperlinks )
InitHLinkArray()
if( g_scaleInFrame||(IsWin("PPTSld") && parent.IsFullScrMode() ) )
document.body.scroll=3D"no"
_RSW()
if( IsWin("PPTSld") && parent.IsFullScrMode() )
FullScrInit();
=09
MakeSldVis();
ChkAutoAdv()
if( runAnimations )
{
if( document.all("NSPlay") )
document.all("NSPlay").autoStart =3D false;
if( sld.filters && sld.filters.revealtrans )
setTimeout( "document.body.start()", sld.filters.revealtrans.duration * =
1000 );
else
document.body.start();
}
}
function MakeSldVis()=20
{
var fTrans=3Dg_showAnimation && SldHasTrans()
if( fTrans )=09
{
if( g_bgSound ) {
idx=3Dg_bgSound.indexOf(",");
pptSound.src=3Dg_bgSound.substr( 0, idx );
pptSound.loop=3D -(parseInt(g_bgSound.substr(idx+1)));
}
SlideObj.filters.revealtrans.Apply()=09
}
SlideObj.style.visibility=3D"visible"
if( fTrans )
SlideObj.filters.revealtrans.Play()
}
function MakeNotesVis()=20
{
if( !IsNts() ) return false=20
SlideObj.style.display=3D"none"
nObj =3D document.all.item("NotesObj")
parent.SetHasNts(0)
if( nObj ) {=20
nObj.style.display=3D""
parent.SetHasNts(1)
}
return 1
}
function ChkAutoAdv()
{
if(SldHasTrans())
SlideObj.onfilterchange=3DAutoAdv
else
AutoAdv()
}
function AutoAdv()
{
if(!IsWin("PPTSld") || !gUseSldTimings )return
var sld=3DGetCurSld()
if( (sld.mAdvDelay>0) && !parent.IsFramesMode() )
setTimeout("parent.GoToNextSld()",sld.mAdvDelay)
}
function GetObj(id)
{
if(g_supportsPPTHTML) return document.all(id);
else return document.getElementById(id);
}
function SldHasTrans() { return SlideObj.style.filter !=3D ""; }
function GetSldId() { return sId=3Dlocation.href.substring(location.href.la=
stIndexOf('/')+1) }
function HideMenu() { if( frames["PPTSld"] && PPTSld.document.all.item("ctx=
tmenu") && PPTSld.ctxtmenu.style.display!=3D"none" ) { PPTSld.ctxtmenu.styl=
e.display=3D'none'; return true } return false }
function IsWin( name ) { return window.name =3D=3D name }
function IsNts() { return IsWin("PPTNts") }
function IsSldOrNts() { return( IsWin("PPTSld")||IsWin("PPTNts") ) }
function SupportsPPTAnimation() { return( navigator.platform =3D=3D "Win32"=
&& navigator.appVersion.indexOf("Windows")>0 ) }
function SupportsPPTHTML()
{
var appVer=3Dnavigator.appVersion, msie=3DappVer.indexOf("MSIE "), ver=3D0
if( msie >=3D 0 )
ver=3DparseFloat( appVer.substring( msie+5, appVer.indexOf(";",msie) ) )
else
ver=3DparseInt(appVer)
return( ver >=3D 4 && msie >=3D 0 )
}
function _RSW()
{
if( !g_supportsPPTHTML || IsNts() ||
( !g_scaleInFrame && (!IsWin("PPTSld") || !parent.IsFullScrMode()) ) )
return
var padding=3D0;
if( IsWin("PPTSld") && parent.IsFramesMode() ) padding=3D6
cltWidth=3Ddocument.body.clientWidth-padding
cltHeight=3Ddocument.body.clientHeight-padding
factor=3D(1.0*cltWidth)/g_origW
if( cltHeight < g_origH*factor )
factor=3D(1.0*cltHeight)/g_origH
newSize =3D g_origSz * factor
if( newSize < 1 ) newSize=3D1
s=3DSlideObj.style
s.fontSize=3DnewSize+"px"
s.posWidth=3Dg_origW*factor
s.posHeight=3Dg_origH*factor
s.posLeft=3D(cltWidth-s.posWidth+padding)/2
s.posTop=3D(cltHeight-s.posHeight+padding)/2
if( g_scaleHyperlinks )
ScaleHyperlinks( factor )
}
function _InitAnimations()
{
animRuntimeInstalled =3D ''+document.body.localTime !=3D 'undefined';
isFullScreen =3D (window.name =3D=3D "PPTSld") && !parent.IsFramesMode();
g_animUseRuntime =3D g_showAnimation && animRuntimeInstalled && !(isFullSc=
reen && parent.IsSldVisited());
if( g_animUseRuntime ) {
collSeq =3D document.all.tags("seq");
if( collSeq !=3D null ) {
for(ii=3D0;ii
' + ENDSHOW_MESG + '
![](3D"notes_flag.gif")
No=
tes![](3D"buttons.gif")
![](3D"slide0007_image001.png"){kind=link}
![](3D"slide0008_image003.png"){kind=link}
![](3D"slide0009_image005.png"){kind=link}
![](3D"slide0011_image007.png"){kind=link}
![](3D"slide0011_image009.png"){kind=link}
![](3D"slide0011_image010.png"){kind=link}
![](3D"slide0013_image012.png"){kind=link}
![](3D"slide0016_image014.png"){kind=link}
![](3D"slide0037_image016.png"){kind=link}
![](3D"slide0017_image018.png"){kind=link}
![](3D"slide0026_image020.png"){kind=link}