Chapter 5 Graphs . the puzzle of the seven bridge in the Konigsberg, o on the Pregel B c 7777x D
Chapter 5 Graphs ❖ the puzzle of the seven bridge in the Königsberg, ❖ on the Pregel
B 画只日 D (b)的
.8 Kirchhoff 冷 Cayler Cnh2m 冷 The four colour problem四色间题 ☆ amiltonian circuits 8 1920s, KOnig: finite and infinite graphs & OS, Compiler, Al, Network
❖ Kirchhoff ❖ Cayler CnH2n+1 ❖ The four colour problem四色问题 ❖ Hamiltonian circuits ❖ 1920s,König: finite and infinite graphs ❖ OS,Compiler,AI, Network
5.1 Introduction to Graphs 5.1.1 Graph terminology Relation: digraph Definition 1: Let V is not empty set. A directed graph, or digraph, is an ordered pair of sets (ve) such that E is a subset of the set of ordered pairs of v. We denote by G(v,E) the digraph. The elements of v are called vertices or simply points", and v is called the set of vertices. Similarly, elements of e are called edge", and E is called the set of edges
5.1 Introduction to Graphs ❖ 5.1.1 Graph terminology ❖ Relation: digraph ❖ Definition 1 : Let V is not empty set. A directed graph, or digraph, is an ordered pair of sets (V,E) such that E is a subset of the set of ordered pairs of V. We denote by G(V,E) the digraph. The elements of V are called vertices or simply "points", and V is called the set of vertices. Similarly, elements of E are called "edge", and E is called the set of edges
Edge(a, b) 点ta: initial vertex, b:terminal vertex b CLA edges (a, b) incident with the vertices a and 图出因,(c,C),(f,f0loop g: isolated vertex。 &G=(V, E),Va, b, c, d, e, f, g, E=l(a, b),a, c), (b, c),(c, a), c, c),(c, e),(d, a),( d,c),(f,e),(f}
❖ G=(V,E),V={a,b,c,d,e,f,g}, ❖ E={(a,b),(a,c),(b,c),(c,a),(c,c),(c,e),(d,a),( d,c),(f,e), (f,f)}, Edge (a,b) a: initial vertex， b:terminal vertex edges (a,b) incident with the vertices a and b。 (c,c),(f,f) loop g: isolated vertex
,b) be edge in G. The a illed endvertices of edges 页()音点 C acent in G; the vertex a is cn8 edge(a, b), and the vertex vertex of this edge. The g cident with the vertices a s called loop The vertex rtex if a vertex is not adjacent to any vertex g is an isolated vertex,(c, c), f are loop. a and b are adjacent; c and d are adjacent
❖ Definition 2：Let (a,b) be edge in G. The vertices a and b are called endvertices of edges; a and b are called adjacent in G; the vertex a is called initial vertex of edge (a,b), and the vertex b is called terminal vertex of this edge. The edge (a,b) is called incident with the vertices a and b. The edge (a,a) is called loop。The vertex is called isolated vertex if a vertex is not adjacent to any vertex. g is an isolated vertex, (c,c) ,(f,f) are loop. a and b are adjacent; c and d are adjacent;
1 not empty set. An undirected air of sets(V,E) such that E multiset of unordered pairs y G(V,E)the graph. The .v6 called vertices or simply called the set of vertices E are called " edge", and E 3 v4 es V={v1,V2V3,V4v52V6},E={V1,2},{v1,v5},{v2,V2 25V3j9V294 25V59 55{3V45V495jj edges v1v2, incidents with the vertices Vi and v2 loop isolated vertex edge (v2,v5) multiple edge
❖ Definition 3: Let V is not empty set. An undirected graph is an ordered pair of sets (V,E) such that E is a sub-multiset of the multiset of unordered pairs of V. We denote by G(V,E) the graph. The elements of V are called vertices or simply "points", and V is called the set of vertices. Similarly, elements of E are called "edge", and E is called the set of edges. V={v1 ,v2 ,v3 ,v4 ,v5 ,v6 }，E={{v1 ,v2 },{v1 ,v5 ,}，{v2 ,v2 }, {v2 ,v3 },{v2 ,v4 },{v2 ,v5 },{v2 ,v5 },{v3 ,v4 },{v4 ,v5 }}， edges {v1 ,v2 } incidents with the vertices v1 and v2 loop ; isolated vertex edge {v2 ,v5 } multiple edge
Definition 4: These edges are called multiple edges if they incident with the same two vertices. The graph is called multigraph. The graph is called a simple graph, if any two vertices in the graph, may connect at most one edge (i.e, one edge or no edge) and the graph has no loop. The complete graph on n vertices, denoted by Kn, is the simple graph that contains exactly one edge between each pair of distinct vertices
❖ Definition 4 ： These edges are called multiple edges if they incident with the same two vertices. The graph is called multigraph. The graph is called a simple graph, if any two vertices in the graph, may connect at most one edge (i.e., one edge or no edge) and the graph has no loop. The complete graph on n vertices, denoted by Kn , is the simple graph that contains exactly one edge between each pair of distinct vertices
undirected graph: graph 冷 finite graph 冷 finite digraph
❖ undirected graph: graph ❖ finite graph ❖ finite digraph
%o Definition 5: The degree of a vertex v in an undirected graph is the number of edges incident with it except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by d(v). A vertex is pendent if only if it has degree one The minimum degree of the vertices of a graph G is denoted b yδ (G)Eminveyd(v))) and the maximum degree by A(G)maxed(v] b=a, a, al
❖ Definition 5：The degree of a vertex v in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by d(v). A vertex is pendent if only if it has degree one. The minimum degree of the vertices of a graph G is denoted by (G)(=minvV {d(v)}) and the maximum degree by (G)(=maxvV {d(v)} ❖ b=a,{a,a}