UNIT-4
GRAPHS
Graph
Graph is composed of a set of vertices( V ) and a set of edges( E ). The graph is denoted
by G(V, E).The graph is used to solve the most challenging and complex programming
problems.
EXAMPLE 2:
Vertices and edges of above graph???
Applications of graphs:
1.Computer science:
Social Networks: Represent users as nodes and friendships/follows as edges.
Web Page Ranking (e.g., Google’s PageRank): Webpages as nodes, hyperlinks as directed
edges.
Recommendation Systems: Graphs help suggest friends, products, or movies based on
connections.
Compilers and Parsers: Use syntax trees and dependency graphs.
Routing Algorithms: Used in network routing (e.g., Dijkstra's algorithm, Bellman-Ford).
2.Computer networks:
Internet and LAN Topology: Devices (nodes) and connections (edges).
3.Transportation and Navigation
Maps and GPS: Cities or intersections as nodes, roads as edges (often weighted by distance
or time).
Airline Routes: Airports as nodes, flights as directed edges.
4.Electrical Engineering
Circuit Analysis: Electrical networks modeled as graphs.
Logic Gates and Digital Circuits: Modeled using directed acyclic graphs (DAGs)
Graph Terminology
Graphs has following terminology.
Vertex
Individual data element of a graph is called as Vertex. Vertex is also known as node. In above
example graph, A, B, C, D & E are known as vertices.
Edge
An edge is a connecting link between two vertices. Edge is also known as Arc. An edge is
represented as (startingVertex, endingVertex). For example, in above graph the link between
vertices A and B is represented as (A,B). In above example graph, there are 7 edges (i.e., (A,B),
(A,C),(A,D),(B,D),(B,E),(C,D),(D,E)).
Edges are three types.
1. Undirected Edge - An undirected egde is a bidirectional edge. If there is undirected edge
between vertices A and B then edge (A , B) is equal to edge (B , A).
2. Directed Edge - A directed egde is a unidirectional edge. If there is directed edge between
vertices A and B then edge (A , B) is not equal to edge (B , A).
3. Weighted Edge - A weighted egde is a edge with value (cost) on it.
Adjacent
If there is an edge between vertices A and B then both A and B are said to be adjacent. In other
words, vertices A and B are said to be adjacent if there is an edge between them.
Outgoing Edge
A directed edge is said to be outgoing edge on its origin vertex.
Incoming Edge
A directed edge is said to be incoming edge on its destination vertex.
Degree
Total number of edges connected to a vertex is said to be degree of that vertex.
Degree Sequence
The degree sequence of a graph is a list of the degrees of its vertices, typically arranged in non-
increasing order (from largest to smallest). The degree of a vertex is the number of edges
connected to it.
1. Identify all vertices: Start by listing all the vertices (nodes) in the graph.
2. Determine vertex degrees: For each vertex, count the number of edges that connect to
it. This count is the vertex's degree.
Create the sequence: List the degrees of all vertices. It's common to arrange them in non-
increasing order (largest degree first, smallest degree last).
A ----- B
| /
C
Degree of A = 2 (connected to B, C)
Degree of B = 2 (connected to A, C)
Degree of C = 2 (connected to A, B)
Degree sequence = (2, 2, 2)
Example 2:
A -- B
|
C
Indegree
Total number of incoming edges connected to a vertex is said to be indegree of that vertex.
Outdegree
Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex.
Self-loop
A self-loop in a graph is an edge that connects a vertex to itself.
Path
A path is a sequence of alternate vertices and edges that starts at a vertex and ends at other vertex
such that each edge is incident to its predecessor and successor vertex.
Cycle
A Cycle in a graph is a path that starts and ends at the same vertex, with no repetitions of vertices
(except the starting and ending vertex, which are the same).
Origin
• If an edge is directed, its first endpoint is said to be origin of it.
Destination
• If an edge is directed, its first endpoint is said to be origin of it and the other endpoint is
said to be the destination of the edge.
Types of Graphs:
1. Directed Graph (Digraph):
A Directed Graph consists of nodes (vertices) connected by directed edges (arcs). Each edge
has a specific direction, meaning it goes from one node to another. Examples include social
media follower relationships, web page links, and transportation routes with one-way
streets.
2. Undirected Graph:
In an Undirected Graph, edges have no direction.. For example, a social network where
friendships exist between people, or a map of cities connected by roads (where traffic can
flow in both directions).
3. Weighted Graph:( Labelled Graph)
Weighted graphs assign numerical values (weights) to edges. These weights represent some
property associated with the connection between nodes. For example, road networks with
varying distances between cities, or airline routes with different flight durations, are examples of
weighted graphs.
5. Connected Graph:
A graph is connected if there is a path between any pair of nodes. In other words, you can
reach any node from any other node.For larger graphs, there’s always a way to move from one
node to another.
6.. Simple Graph
A graph G=(V, E) is said to be a simple graph if there is one and only one edge between each
pair of vertices.
7.Null Graph
• A graph G= (V, E) is said to be a null graph if there are n number of vertices exist, but
no Edge exists that connects them.
8.Trivial Graph
A graph G= (V, E) is said to be trivial if there is only single vertex in the graph without any
edge.
9.Complete Graph
• Each vertex contains same number of edges is known as complete graph
A complete graph is also called a Full Graph.
10.Pseudo Graph
• A graph G= (V, E) is said to pseudo graph in case it contains a self-loop along with other
edges.
11. Bipartite Graph(Bigraph)
A bipartite graph is a graph where the vertices can be divided into two separate groups,
typically denoted as X and Y, such that all edges connect vertices from group X to group Y. No
edges connect vertices within the same group
G={v1,v2,v3,v4,v5,v6}
X={v1,v2,v3} y={v4,v5,v6}
12.Cyclic Graph:
A cyclic graph has at least one cycle. You can traverse edges and eventually return to the same
node. For example: circular road system.
13.. Finite Graph:
A graph is said to be finite if it has finite number of vertices and finite number of edges.
14. Infinite Graph
A graph is said to be infinite if it has infinite number of vertices as well as infinite number of
edges.
15.Graph Complements
The complement of a graph G, denoted as G̅ or G', is a new graph formed by keeping the same
vertices as G, but adding edges where they are not in G and removing edges where they are in
G.
Given a simple undirected graph G=(V,E)the complement graph G’=(V,E’)
Keep the same set of vertices.
Add an edge between every pair of non-adjacent vertices in the original graph.
No loops or multiple edges allowed.
Matrix Representations Graphs:
Graph data structure is represented using following representations...
1. Adjacency Matrix
2. Incidence Matrix
Adjacency Matrix
An adjacency matrix is a square matrix used to represent a graph—showing which vertices are
connected to which.
In this matrix, both rows and columns represent vertices. This matrix is filled with either 1 or 0. Here,
1 represents that there is an edge from row vertex to column vertex and 0 represents that
there is no edge from row vertex to column vertex.
For example, consider the following undirected graph representation.
Directed graph representation...
Incidence Matrix
An incidence matrix is a way of representing a graph using a matrix to show the relationship
between vertices and edges.
Definition:
For a graph with n vertices and m edges, the incidence matrix is an n × m matrix.
Each row represents a vertex. Each column represents an edge.
This matrix is filled with 0 or 1 or -1. Here, 0 represents that the row edge is not connected to
column vertex, 1 represents that the row edge is connected as the outgoing edge to column
vertex and -1 represents that the row edge is connected as the incoming edge to column
vertex.
For example, consider the following directed graph representation...
Graph Isomorphism
In graph theory, two graphs are considered isomorphic if they have the same structure, meaning
they are identical except for the labeling of their vertices
Two graphs G1 and G2 are said to be isomorphic if −
Their number of components (vertices and edges) are same.
Both the graphs contain same degree sequence
One to one correspondence between the vertices of two graphs must be same i.efor
every vertex in graph1 there should be equivalent vertex in graph2.
Edge preserving should be satisfied I,e each edge in graph1 is equivalent to an edge
in graph2
Adjacency matrixes of both graphs must be same.
if two graphs with different numbers of vertices or edges cannot be
isomorphic
Graph isomorphism is a fundamental concept in graph theory, used in various areas,
including computer science, data analysis, and network theory.
Example:
GRAPH COMBINATIONS:
A combination graph (also known as a combo chart) displays multiple data series within the
same visualization by combining different chart types. For example, a combination graph
might display a bar chart for one set of data and a line graph for another, both on the same
axes. This allows for more complex and insightful data presentations compared to individual
charts.
Example: In a manufacturing company, a combination chart can be used to analyze the
number of units sold over the last few months and the total revenue generated. The
number of units sold can be represented by a bar chart, while the total revenue can
be shown as a line graph. This visualization helps in understanding the relationship
between sales volume and revenue over time.
Common Applications of Combination Graphs:
Sales Analysis: Comparing actual sales with target sales or projected sales.
Financial Data: Analyzing revenue, expenses, and profit trends.
Market Research: Comparing different market segments or customer groups.
Environmental Data: Monitoring temperature, precipitation, and other environmental factors.
Eulerian circuit:(Euler cycle)
Check the following graphs are Euler graphs or not
Graph-1 Graph-2
Hamiltonian Cycle:
Each vertex of the graph will be visited exactly once except start vertex.
Start and end vertex must be same.
The graph contains Hamiltonian circuit then the graph called as Hamiltonian graph.
Konigsberg Bridge Problem
The Königsberg Bridge Problem is a famous historical problem in graph theory and mathematics.
The city(Königsberg) was set on both sides of the Pregel River, with two islands connected by seven
bridges.
Problem: "Is it possible to walk through the city in such a way that you cross each of the seven bridges
exactly once?" or
“Cross each bridge once, no repeats
In 1736, Leonhard Euler proved:
It is NOT possible to cross all the bridges exactly once without repeating any.
He represented the land areas as vertices and the bridges as edges in a graph.
Euler found:
If more than two vertices have an odd degree (odd number of connecting edges), then
it's not possible to have a walk that uses every edge exactly once (called an Eulerian
Path).
In Königsberg, all four land areas had odd degrees
Touring a graph: In graph theory, touring a graph is a systematic way to visiting or traversing all
the vertices or edges of a graph in some organized way
1.Walk: For a walk you can traverse the graph as you want(Traverse in anyway) .When you perform a
walk vertices and edges can be repeated.
1-2-4-5-3-2-1-3
1-3-2-4-5-3-1-2
2.Trail: In graph theory, a trail is a type of walk with a specific condition:
A trail is a walk in a graph in which no edge is repeated.
Vertices may repeat
Edges must be distinct
Ex1: 1-3-4-5-3-2 is valid
Ex2: 1-3-4-3 is not valid
3.Path:
A path is a sequence of alternate vertices and edges that starts at a vertex and ends at other
vertex: in which no vertex and no edge is repeated.
All vertices are distinct
All edges are distinct
Ex: 1-2-3-6-5
4. Eulerian Tour:
A tour that visits every edge exactly once and starts and ends at the same vertex.
Only possible if the graph is connected and all vertices have even degree.
5.Hamiltonian Tour (or Cycle):
A Hamiltonian Tour is a closed loop in a graph that Edges may or may not repeat, but vertices
cannot repeat (except the start/end)
Ex:A salesman visiting every city exactly once and returning to the starting city”
This is the famous Traveling Salesman Problem (TSP) — based on Hamiltonian tours
