Graphs in Mathematics and Computer Science
A
graph
is an abstract data type that is meant to
implement the undirected graph and directed
graph concepts from mathematics.
A graph data structure consists of a finite (and possibly
mutable) set of
vertices
or
nodes
or
points
, together with a
set of unordered pairs of these vertices for an undirected
graph or a set of ordered pairs for a directed graph. These
pairs are known as
edges
,
arcs
, or
lines
for an undirected
graph and as
arrows
,
directed edges
,
directed arcs
, or
directed
lines
for a directed graph. The vertices may be part of the
graph structure, or may be external entities represented
by integer indices or references.
Definition
A graph G = (V, E) is composed of:
V: set of vertices
E: set edges connecting the vertices in V
An edge e=(u, v) is a pair of vertices
V = {a,b,c,d,e}E = {(a,b), (a,c), (a,d), (b,e),(c,d), (c,e), (d,e)}
Definition
Electric circuits
Networks
Roads
Flights
Communications
Applications
Basic primary operations of a Graph −
Add Vertex
− Adds a vertex to the graph.
Add Edge
− Adds an edge between the two vertices
of the graph.
Display Vertex
− Displays a vertex of the graph.
Basic Operations
Graphs are represented using following representations:
Adjacency Matrix
Incidence Matrix
Adjacency List
Graph Representations
Adjacency Matrix
Adjacency Matrix
Incidence Matrix
Adjacency List
If (v
0
, v
1
) is an edge in an undirected graph,
v
0
and v
1
are
adjacent
The edge (v
0
, v
1
) is incident on vertices v
0
and v
1
If < v
0
, v
1
> is an edge in a directed graph
v
0
is
adjacent to
v
1,
and v
1
is
adjacent from
v
0
The edge < v
0
, v
1
> is incident on v
0
and v
1
Adjacent and Incident
Degree of Vertex
Sequence of vertices v
1
, v
2
, v
3
,… v
n
such that
consecutive vertices v
i
and v
i+1
are adjacent
simple path
:
no repeated vertices
cycle path
: simple path, except that the last vertex is
the same as the first vertex
Path
connected graph
: any two vertices are connected by some
path
sub graph
: subset of vertices and edges forming a graph
connected component
: maximal connected subgraph
tree
: connected graph without cycles
forest
: collection of trees
Graph types
Let n = # of vertices and m = # of edges
A
complete graph
one in which all pairs of vertices are
adjacent
Each of n vertices incident to n-1 edges, however
each edge counted twice. Therefore
m=n(n-1)/2
If a graph is not complete
m<n(n-1)/2
If
m<n-1
Graph is not connected
Connectivity
An undirected graph is one which the pair of vertices
are not ordered,
(v
0
, v
1
)=(v
1
,
v
0
)
A directed graph is one which each edge is a directed
pair of vertices,
< v
0
, v
1
> != < v
1
, v
0
>
Directed vs. Undirected
Dijktra’s shortest path
Algorithm
Dijktra’s algorithm
between 2 nodes
Dijkstra’s algorithm based
on Euclidean distance
Graphs in mathematics and computer science are abstract data types used to represent relationships between objects. They consist of vertices connected by edges, which can be directed or undirected. Graphs find applications in various fields like electric circuits, networks, and transportation systems. Basic operations on graphs include adding vertices and edges. They can be represented using adjacency matrices, incidence matrices, or adjacency lists. Understanding concepts like adjacency and incidence is crucial for working with graphs effectively.
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
Definition A graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics. A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges, arcs, or lines for an undirected graph and as arrows, directed edges, directed arcs, or directed lines for a directed graph. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.
Definition A graph G = (V, E) is composed of: V: set of vertices E: set edges connecting the vertices in V An edge e=(u, v) is a pair of vertices V = {a,b,c,d,e} E = {(a,b), (a,c), (a,d), (b,e), (c,d), (c,e), (d,e)} a b c d e
Applications Electric circuits Networks Roads Flights Communications
Basic Operations Basic primary operations of a Graph Add Vertex Adds a vertex to the graph. Add Edge Adds an edge between the two vertices of the graph. Display Vertex Displays a vertex of the graph.
Graph Representations Graphs are represented using following representations: Adjacency Matrix Incidence Matrix Adjacency List
Adjacent and Incident If (v0, v1) is an edge in an undirected graph, v0 and v1 are adjacent The edge (v0, v1) is incident on vertices v0 and v1 If < v0, v1 > is an edge in a directed graph v0 is adjacent to v1, and v1 is adjacent from v0 The edge < v0, v1 > is incident on v0 and v1
Degree of Vertex The degree of a vertex is the number of edges incident to that vertex For directed graph, The in-degree of a vertex v is the number of edges that have v as the head The out-degree of a vertex v is the number of edges that have v as the tail If di is a degree of a vertex i in a graph G with n vertices and e edges, the number of edges is ? = ( ?=0 ? 1?? )/2
Path Sequence of vertices v1, v2, v3, vn such that consecutive vertices vi and vi+1 are adjacent simple path :no repeated vertices cycle path : simple path, except that the last vertex is the same as the first vertex a b c d e
Graph types connected graph : any two vertices are connected by some path sub graph : subset of vertices and edges forming a graph connected component : maximal connected subgraph tree : connected graph without cycles forest : collection of trees
Connectivity Let n = # of vertices and m = # of edges A complete graph one in which all pairs of vertices are adjacent Each of n vertices incident to n-1 edges, however each edge counted twice. Therefore m=n(n-1)/2 If a graph is not complete m<n(n-1)/2 If m<n-1 Graph is not connected
Directed vs. Undirected An undirected graph is one which the pair of vertices are not ordered, (v0, v1)=(v1,v0) A directed graph is one which each edge is a directed pair of vertices, < v0, v1 > != < v1, v0 >
Dijktras shortest path Algorithm
Dijktras algorithm between 2 nodes
Dijkstras algorithm based on Euclidean distance
