SAS#18
Graph Theories and Applications
ITE048 – DISCRETE STRUCTURES
Graphs
• These are connected nodes (or vertex)
• These are any network related, routing, finding relation, path, etc.
• A visual representation of connected objects
Application of Graphs
• Connected friends accounts in a social media website
• GPS/Google Maps showing routes and path
Application of Graphs
• Website links and navigation
• E-commerce recommendation and customer transactions
Application of Graphs
• Internet connected devices
• Street maps and navigation
Application of Graphs
• Project Management
• Program design and flow
.
Application of Graphs
• Grammar checker and evaluating arithmetic expressions
Application of Graphs
• many more applications in medical research, engineering, finance,
management, etc.
Graphs Similarity
• It is used in computer science, network analysis, bioinformatics, and social
network analysis.
• Comparing and grouping graphs to identify how similar different graphs are
in terms of their structures and properties.
• This is important in understanding complex systems and patterns.
• Examples:
• In computer science, it helps identify similar structures or detecting anomalies.
• In network analysis, it uncovers common issues/concerns/milestone over time.
• In bioinformatics, it compares molecular structures, protein-protein interaction
networks, and gene regulatory networks.
• In social network analysis, it compares community structures, patterns, influential
nodes within social platforms.
Similarity Graphs
• Example: In programs/Codes:
• Properties are:
• Number of lines in the program
• Number of “return” statements
• Number of function calls
A graph G is constructed as follows:
V(G) is the set of programs {v1, v2, v3, v4, v5 }. A vertex is
denoted by (p1, p2, p3), where pi is
the value of property i.
v1 = (66, 20, 1)
v2 = (41, 10, 2)
v3 = (68, 5, 8)
v4 = (90, 34, 5)
v5 = (75, 12, 14)
Dissimilarity Graphs
• Dissimilarity Function:
• For each pair of vertices v = (p1, p2, p3) and w = (q1, q2, q3) let
• s(v,w) – is a measure of dissimilarity between any two programs v and w
• Example:
• N = 20
• v(1,2) =
• v(2,4) =
Sub-graphs
• These are graphs that are part/connected of a bigger graph
• The number of nodes (vertices) is smaller than the whole graph
Graph (G): Sub-graphs (G’):
• [Vertices]: V(G’) <= V(G)
• The number of vertices of sub-graph is lesser than the graph
• [Edges]: E(G’) <= E(G)
• The number of edges of sub-graph is lesser than the graph
Adjacent Vertices
• Adjacent Vertices has a direct edge with another vertex
- Vertex 1 and Vertex 2 are adjacent (because there are
arrows both ways: 1 -> 2 and 2 -> 1
- Vertex 2 and Vertex 3 are adjacent (because of the arrow):
2 -> 3
- Vertex 1 and Vertex 3 are NOT adjacent (because there is no
direct edge between them)
Incident Edges
• Incident Edges is the edge connecting 2 vertices
- Vertex 1 is incident to:
Edge 1 -> 2 (outgoing)
Edge 2 -> 1 (incoming)
- Vertex 2 is incident to:
Edge 1 -> 2 (incoming)
Edge 2 -> 1 (outgoing)
Edge 2 -> 3 (outgoing)
- Vertex 3 is incident to:
Edge 2 -> 3 (incoming)
Summary of
Adjacent Vertices and Incident Edges
Degree of Vertex
• In-degree: Number edges going in to the vertex
• Out-degree: Number of edges going out of the vertex
• Degree (Directed Graph): In-degree + Out-degree
• Degree (Un-directed Graph): Number of edges (incident) to the vertex
Path
• A collection of edges from a vertex to another
from a to e: a, c, e
a, b, c, e
a, c, d, e
a, b, c, d, e
* In a graph, multiple paths are possible
Graph vs Connected Graph
• Graph contains vertices whether connected or not
• Connected Graph contains connected vertices and no isolated vertex
Graph Connected Graph
Simple Path
• It is a path from v to w.
• It has no repeated vertices.
• Examples:
• Path: 6, 5, 2, 4, 3, 2, 1
• Is Simple Path? No
• Path: 5, 6, 2, 4
• Is Simple Path? Yes
• Path: 6, 5, 2, 4, 3, 2, 1
• Is Simple Path? No
• Path: 7
• Is Simple Path? Yes
Cycle
• It is a path from v to w.
• It is a path of non-zero length
• It has no repeated edges.
• Examples:
• Path: 1, 2, 6, 5, 2, 4, 3, 2, 1
• Is Cycle? No
• Path: 5, 6, 2, 5
• Is Cycle? Yes
• Path: 2, 6, 5, 2, 4, 3, 2
• Is Cycle? Yes
• Path: 7
• Is Cycle? No
Simple Cycle
• It is a path from v to v.
• Vertices v and v is the same
• It has no repeated vertex.
• Examples:
• Path: 6, 5, 2, 4, 3, 2, 1
• Is Simple Cycle? No
• Path: 5, 6, 2, 5
• Is Simple Cycle? Yes
• Path: 2, 6, 5, 2, 4, 3, 2
• Is Simple Cycle? No
• Path: 7
• Is Simple Cycle? No
Euler Path/Cycle
• Euler path is a path that contains every edge exactly once.
• Euler circuit is a circuit that contains every edge exactly once and
returns to the initial vertex.
• This definition works for all types of graphs, undirected or directed,
with or without parallel edges and loops.
Hamiltonian Cycle
• It is a cycle in the graph that contains
each vertex exactly once (except for the
starting and ending vertex that appears
twice).
• Sir William Rowan Hamilton marketed
puzzle in the mid-1800s in the form of
a dodecahedron.
Hamiltonian Cycle
Travelling Salesperson Problem
• This is an example of a cycle called a Hamiltonian cycle. Visit every
vertex of a graph G only once by a simple cycle (and return to the
starting vertex or node).
• A salesperson visited all cities exactly once.
Activities
Activities
Activities
Activities
Activities
Thank you!