《離散數(shù)學》ch(4)

1、整理課件Chapter 9 Graphs9.1 Introduction to Graphs9.2 Graph Terminology9.3 Representing Graphs and Graph Isomorphism9.4 Connectivity9.5 Euler and Hamilton Paths9.6 Shortest-Path Problems9.7 Planar Graphs9.8 Graph Coloring整理課件9.1 Introduction to GraphsTypes of Graphs (1) Definition 1 (page 589) A simple

2、graph G=(V,E) consists of V, a nonempty set of vertices (頂點頂點), and E, a set of unordered pairs of distinct elements of V called edges. Example: See Figure 1 (page 590).整理課件 (2) Definition 2 (page 590)A multigraph G=(V,E) consists of a set V of vertices, a set E of edges, and a function from E to u,

3、v | u,v V, uv. The edges e1 and e2 are called multiple or parallel edges if f(e1)=f(e2).Example: See Figure 2 (page 590)整理課件 (3) Definition 3 (page 590)A pseudograph G=(V, E) consists of a set V of vertices, a set E of edges, and a function f from E to u,v | u,vV . An edge is a loop if f(e)=u,u=u fo

4、r some uV.Example: See Figure 3 (page 590).整理課件 (4) Definition 4 (page 591) A directed graph G=(V, E) consists of a set of vertices V and a set of edges E that are ordered pairs of elements of V.Remark: the edge from u to v-(u,v)Example: See Figure 4 (page 591).整理課件 (5) Definition 5 (page 591) A dir

5、ected multigraph G=(V, E) consists of a set V of vertices, a set E of edges, and a function f from E to (u,v) | u, vV . The edges e1 and e2 are multiple edges if f(e1)=f(e2).Example: See Figure 5 (page 591).整理課件 (6) Summary (Graph Terminology, page 592)Type Edges Multiple Edge? Loops?Simple Graph Undirected No NoMultigraph Undirected Yes NoPseudograph Und