The mathematician Euler pointed out,
The problem with remain insoluble
unless each piece of land could be
connected with even numbers of bridges.
A
B
C
D
A
D
B C
§ 16-1 Notations and definitions
Seven-bridge problem:
You are asked to set off from
any piece of the lands and pass
through all the seven bridges
under the condition that each
bridge can be used only once,so
that you can finally return to
the starting point.
Graph of network
The graph of network is simply a diagram showing the
interconnection of network elements,in this diagram every two-
terminal network element is represented,regardless of its nature,
by a line segment called a branch,and each end point of element
is denoted by a dot called a node,The collection （ 集合） of
these branches and nodes is called the graph of the network.
1b 2b
3b
4b
5b
6b
7b
2n
1n
0n
4n3n 5n
(directed graph)
2n
1b 2b 3b
4b
5b
6b
7b
1n
0n
3n 4n 5n
Definitions:
1,Node--A node,ni,is defined to be an end point of a
line segment or an isolated（ 孤立） point.
2,Branch--A branch,bk,is a line segment associated
with two nodes ni and nj at its end points.
3,Graph--A graph,G,is a collection of nodes and
branches with the condition that branches intersect
one another only at the nodes.
4,Degree（ 度） of a node--The degree of a node is the
number of the branches incident to it.
5,Path-- A path of length m is a sequence (序列 )of m
distinct branches together with m+1 distinct nodes
such that every node is of degree 2 except the initial
and terminal nodes,which are of degree 1.
6,Loop--A loop of length m is a path such that its initial
and terminal nodes coincide（ 重合）,
7,Connected（ 连通） Graph--A graph G is said to be
connected if there is least one path between any two of
this nodes.
8,Tree（ 树） --A tree T of a connected graph G is a
connected subgraph（ 子图） of G with the following
properties:
(a) T contains all the nodes of G;
(b) T does not contain any loop.
The branches of a tree are called tree branches.
The branches of G that are not tree branches are called links
or chords(弦）,
9,Cutset(割集 ) -- A cutset of a connected graph is a set
of minimum number of branches that when deleted
divide the graph into two separate subgraphs.
1C
3C
2C
6
10,Fundamental loop-- A fundamental loop of a graph
G with respect to a tree T is a loop that is made up of
one chord and a unique set of branches of T.
3l
1l 2l
11,Fundamental cutset -- A fundamental cutset of a
graph G with respect to a tree T is a cutset that is made
up of one tree branch and a unique set of chords.
3C
2C
1C 3C
1C
2C
The problem with remain insoluble
unless each piece of land could be
connected with even numbers of bridges.
A
B
C
D
A
D
B C
§ 16-1 Notations and definitions
Seven-bridge problem:
You are asked to set off from
any piece of the lands and pass
through all the seven bridges
under the condition that each
bridge can be used only once,so
that you can finally return to
the starting point.
Graph of network
The graph of network is simply a diagram showing the
interconnection of network elements,in this diagram every two-
terminal network element is represented,regardless of its nature,
by a line segment called a branch,and each end point of element
is denoted by a dot called a node,The collection （ 集合） of
these branches and nodes is called the graph of the network.
1b 2b
3b
4b
5b
6b
7b
2n
1n
0n
4n3n 5n
(directed graph)
2n
1b 2b 3b
4b
5b
6b
7b
1n
0n
3n 4n 5n
Definitions:
1,Node--A node,ni,is defined to be an end point of a
line segment or an isolated（ 孤立） point.
2,Branch--A branch,bk,is a line segment associated
with two nodes ni and nj at its end points.
3,Graph--A graph,G,is a collection of nodes and
branches with the condition that branches intersect
one another only at the nodes.
4,Degree（ 度） of a node--The degree of a node is the
number of the branches incident to it.
5,Path-- A path of length m is a sequence (序列 )of m
distinct branches together with m+1 distinct nodes
such that every node is of degree 2 except the initial
and terminal nodes,which are of degree 1.
6,Loop--A loop of length m is a path such that its initial
and terminal nodes coincide（ 重合）,
7,Connected（ 连通） Graph--A graph G is said to be
connected if there is least one path between any two of
this nodes.
8,Tree（ 树） --A tree T of a connected graph G is a
connected subgraph（ 子图） of G with the following
properties:
(a) T contains all the nodes of G;
(b) T does not contain any loop.
The branches of a tree are called tree branches.
The branches of G that are not tree branches are called links
or chords(弦）,
9,Cutset(割集 ) -- A cutset of a connected graph is a set
of minimum number of branches that when deleted
divide the graph into two separate subgraphs.
1C
3C
2C
6
10,Fundamental loop-- A fundamental loop of a graph
G with respect to a tree T is a loop that is made up of
one chord and a unique set of branches of T.
3l
1l 2l
11,Fundamental cutset -- A fundamental cutset of a
graph G with respect to a tree T is a cutset that is made
up of one tree branch and a unique set of chords.
3C
2C
1C 3C
1C
2C
