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(弦）