Graphs in Discrete Mathematics
Section 13.1
Graphs
What are “Graphs”
•
Graphs are fundamental objects in discrete
mathematics that model relationships
between pairs of objects.
Graphs – Vocabulary
•
Vertex / Vertices
•
Edge(s)
•
Directed Graph
•
Undirected Graph
•
Parallel Edge
•
Self Loop
•
Adjacent
•
Endpoints
•
Incident
•
Neighbor
•
Degree
•
Total Degree
•
Regular Graph
•
Subgraph
Graphs – Vocabulary
•
Vertex / Vertices
•
Edge(s)
•
Directed Graph
•
Undirected Graph
Graphs — an overview
undirected
Graphs — an overview
labelled edges
Graphs — an overview
1987
2273
344
2145
2462
618
211
318
190
Graphs — an overview
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
undirected
Graphs — an overview
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)
Graphs – Definitions
•
Vertex / Vertices
•
Edge(s)
•
Directed Graph
•
Undirected Graph
•
Parallel Edge
•
Self Loop
•
Adjacent
•
Endpoints
•
Incident
•
Neighbor
Graphs – Definitions
•
Vertex / Vertices
•
Edge(s)
•
Directed Graph
•
Undirected Graph
•
Parallel Edge
•
Self Loop
•
Adjacent
•
Endpoints
•
Incident
•
Neighbor
•
Degree
•
Total Degree
Graphs – Definitions
•
Vertex / Vertices
•
Edge(s)
•
Directed Graph
•
Undirected Graph
•
Parallel Edge
•
Self Loop
•
Adjacent
•
Endpoints
•
Incident
•
Neighbor
•
Degree
•
Total Degree
•
Regular Graph
•
Subgraph
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.
Examples
- Roadmaps
- Communication networks
- WWW
- Electrical circuits
-
Task schedules
-
Facebook friends
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.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Section 13.1 Graphs
What are Graphs Graphs are fundamental objects in discrete mathematics that model relationships between pairs of objects.
Graphs Vocabulary Vertex / Vertices Edge(s) Directed Graph Undirected Graph Parallel Edge Self Loop Adjacent Endpoints Incident Neighbor Degree Total Degree Regular Graph Subgraph
Graphs Vocabulary Vertex / Vertices Edge(s) Directed Graph Undirected Graph
Graphs an overview labelled vertices BOS DTW SFO PIT JFK LAX
Graphs an overview labelled vertices BOS DTW SFO PIT JFK LAX edges undirected
Graphs an overview labelled vertices BOS 618 DTW SFO 2273 211 190 318 PIT 1987 344 JFK 2145 2462 LAX labelled edges
Graphs an overview labelled vertices BOS DTW SFO PIT JFK LAX directed edges
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
Graphs an overview labelled vertices BOS DTW SFO PIT JFK LAX edges undirected
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)
Graphs Definitions Vertex / Vertices Edge(s) Directed Graph Undirected Graph Parallel Edge Self Loop Adjacent Endpoints Incident Neighbor
Graphs Definitions Vertex / Vertices Edge(s) Directed Graph Undirected Graph Parallel Edge Self Loop Adjacent Endpoints Incident Neighbor Degree Total Degree
Graphs Definitions Vertex / Vertices Edge(s) Directed Graph Undirected Graph Parallel Edge Self Loop Adjacent Endpoints Incident Neighbor Degree Total Degree Regular Graph Subgraph
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.
Examples - Roadmaps - Communication networks - WWW - Electrical circuits - Task schedules - Facebook friends
