CSE 21 Chapter Notes - Chapter 7: Directed Graph
11 May 2018
School
Department
Course
Professor
Graphs and Graph models
Graph = ordered pair (nonempty set of vertices, set of edges)
loops areedges that connect a vertex to itself
a edge has either one (self loop) or two vertices associated with it called endpoints
an edge connects endpoints
Usually graphs are visualized with dots as vertices and line segments as edges.
"The way we drawca graph is arbitrary, as long as the correct connections between vertices are depicted."
Simple graph
each edge connects 2 different vertices
no 2 edges connect the same pair of vertices
Multigraphs
may have multiple edges connecting the same vertices
Directed graph = digraph is an ordered pair (nonempty set of vertices, set of direct edges or arcs)
Simple directed graph contains no loops and has no multiple directed edges
Although the terminology used to describe graphs may vary, three key questions can help us understand the
structure of a graph:
1. Are the edges of the graph undirected or directed (or both)?
2. If the graph is undirected, are multiple edges present that connect the same pair of vertices? If the graph is
directed, are multiple directed edges present?
3. Are loops present?
