8 16-1 Notations and definitions Seven-bridge problem A You are asked to set off from any piece of the lands and pass B through all the seven bridges under the condition that each bridge can be used only once, so hat you can finally return to the starting point. The mathematician Euler pointed out: B The problem with remain insoluble unless each piece of land could be D connected with even numbers of bridges
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 (A) of these branches and nodes is called the graph of the network nl if b2 (directed grap
Graph of network The graph of network is simply a diagram showing the interconnection of network elements, in this diagram every twoterminal 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. 1 b b2 3 b 4 b 5 b 6 b 7 b n2 n1 n0 n4 n3 n5 (directed graph) n2 1 b 2 b 3 b 4 b 5 b 6 b 7 b n1 n0 n3 n4 5 n
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 n; and n; 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 (E) of a node--The degree of a node is the number of the branches incident to it
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
5Path- a path of length m is a sequence(序列)ofm distinct branches together with m+l 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
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(*f)--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 g that are not tree branches are called links or chords(弦) The branches of a tree are called tree branches
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(J)--a cutset of a connected graph is a set of minimum number of branches that when deleted divide the graph into two separate subgraphs
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. C1 C3 C2 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
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. 3 l 1 l 2 l
11. Fundamental cutset --A fundamental cutset of a graph G with respect to a tree Tis a cutset that is made up of one tree branch and a unique set of chords
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. C3 C2 C1 C3 C1 C2