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