Lecture Discrete mathematics and its applications (7/e) – Chapter 10: Graphs. This chapter presents the following content: Graphs and graph models, graph terminology and special types of graphs, representing graphs and graph isomorphism, connectivity, euler and hamiltonian graphs, shortest-path problems. | Graphs Chapter 10 Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Graphs and Graph Models Graph Terminology and Special Types of Graphs Representing Graphs and Graph Isomorphism Connectivity Euler and Hamiltonian Graphs Shortest-Path Problems (not currently included in overheads) Planar Graphs (not currently included in overheads) Graph Coloring (not currently included in overheads) Graphs and Graph Models Section Section Summary Introduction to Graphs Graph Taxonomy Graph Models Graphs Definition: A graph G = (V, E) consists of a nonempty set V of vertices (or nodes) and a set E of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints. Remarks: The graphs we study here are unrelated to graphs of functions studied in Chapter 2. We have a lot of freedom when we draw a picture of a graph. All that matters is the connections made by the edges, not the particular geometry depicted. For example, the lengths of edges, whether edges cross, how vertices are depicted, and so on, do not matter A graph with an infinite vertex set is called an infinite graph. A graph with a finite vertex set is called a finite graph. We (following the text) restrict our attention to finite graphs. a c b d Example: This is a graph with four vertices and five edges. Some Terminology In a simple graph each edge connects two different vertices and no two edges connect the same pair of vertices. Multigraphs may have multiple edges connecting the same two vertices. When m different edges connect the vertices u and v, we say that {u,v} is an edge of multiplicity m. An edge that connects a vertex to itself is called a loop. A pseudograph may include loops, as well as multiple edges connecting the same pair of vertices. Remark: There is no standard terminology for graph theory. So, it is crucial that you . | Graphs Chapter 10 Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Graphs and Graph Models Graph Terminology and Special Types of Graphs Representing Graphs and Graph Isomorphism Connectivity Euler and Hamiltonian Graphs Shortest-Path Problems (not currently included in overheads) Planar Graphs (not currently included in overheads) Graph Coloring (not currently included in overheads) Graphs and Graph Models Section Section Summary Introduction to Graphs Graph Taxonomy Graph Models Graphs Definition: A graph G = (V, E) consists of a nonempty set V of vertices (or nodes) and a set E of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints. Remarks: The graphs we study here are unrelated to graphs of functions studied in Chapter 2. We have a lot of freedom when we draw a picture of a graph. All
