Understanding Graphs in Discrete Mathematics

Graphs are fundamental objects in discrete mathematics that model relationships between pairs of objects. This overview covers the vocabulary, formal definitions, and types of graphs, including directed and undirected graphs. Learn about vertices, edges, adjacency, and more essential concepts in graph theory.

• Discrete mathematics
• Graph theory
• Relationships
• Vertices
• Edges

hasbrouck_v Follow

Uploaded on Oct 11, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

2. Section 13.1 Graphs

3. What are Graphs Graphs are fundamental objects in discrete mathematics that model relationships between pairs of objects.

5. Graphs Vocabulary Vertex / Vertices Edge(s) Directed Graph Undirected Graph Parallel Edge Self Loop Adjacent Endpoints Incident Neighbor Degree Total Degree Regular Graph Subgraph

6. Graphs Vocabulary Vertex / Vertices Edge(s) Directed Graph Undirected Graph

7. Graphs an overview labelled vertices BOS DTW SFO PIT JFK LAX

8. Graphs an overview labelled vertices BOS DTW SFO PIT JFK LAX edges undirected

9. Graphs an overview labelled vertices BOS 618 DTW SFO 2273 211 190 318 PIT 1987 344 JFK 2145 2462 LAX labelled edges

10. Graphs an overview labelled vertices BOS DTW SFO PIT JFK LAX directed edges

11. Introduction: Formal Definition A graph G = (V,E) consists of a finite set of vertices, V, and a finite set of edges E. Each edge is a pair (v,w) where v, w V

12. Graphs an overview labelled vertices BOS DTW SFO PIT JFK LAX edges undirected

13. Introduction: Formal Definition A directed graph, or digraph, is a graph in which the edges are ordered pairs (v, w) (w, v) An undirected graph is a graph in which the edges are unordered pairs (v, w) == (w, v)

14. Graphs Definitions Vertex / Vertices Edge(s) Directed Graph Undirected Graph Parallel Edge Self Loop Adjacent Endpoints Incident Neighbor

15. Graphs Definitions Vertex / Vertices Edge(s) Directed Graph Undirected Graph Parallel Edge Self Loop Adjacent Endpoints Incident Neighbor Degree Total Degree

16. Graphs Definitions Vertex / Vertices Edge(s) Directed Graph Undirected Graph Parallel Edge Self Loop Adjacent Endpoints Incident Neighbor Degree Total Degree Regular Graph Subgraph

17. Degrees - directed out-degree of x: the number of edges (x,y) in-degree of x: the number of edges (y,x) degree: sum of in-degree and out-degree - undirected degree of x: the number of edges {x,y} Degrees are often important in determining the running time of an algorithm.

18. Examples - Roadmaps - Communication networks - WWW - Electrical circuits - Task schedules - Facebook friends