CC 103 M14 GRAPHS

Graph

is a non-linear data structure consisting of vertices and edges.
composed of a set of vertices( V ) and a set of edges( E ). The graph is denoted by G(V, E).

Vertices

referred to as nodes or vertex

Edges

lines or arcs that connect any two nodes in the graph.

Vertices

Edges

Components of a Graph

Vertices

the fundamental units of the graph.

Every node/vertex

can be labeled or unlabeled.

Edges

are drawn or used to connect two nodes of the graph. It can be ordered pair of nodes in a directed graph. can connect any two nodes in any possible way. There are no rules.

Null Graph

Trivial Graph

Undirected Graph

Directed Graph

Connected Graph

Disconnected Graph

Regular Graph

Complete Graph

Cycle Graph

Cyclic Graph

Directed Acyclic Graph

Bipartite Graph

Weighted Graph

Types of Graph

Null Graph

there are no edges in the graph.

Trivial Graph

Graph having only a single vertex, it is also the smallest graph possible.

Undirected Graph

A graph in which edges do not have any direction. That is the nodes are unordered pairs in the definition of every edge.

Directed Graph

A graph in which edge has direction. That is the nodes are ordered pairs in the definition of every edge.

Connected Graph

The graph in which from one node we can visit any other node in the graph

Disconnected Graph

The graph in which at least one node is not reachable from a node

Regular Graph

The graph in which the degree of every vertex is equal to K is called K regular graph.

Complete Graph

The graph in which from each node there is an edge to each other node.

Cycle Graph

The graph in which the graph is a cycle in itself,  the degree of each vertex is 2.

Cyclic Graph

A graph containing at least one cycle

Directed Acyclic Graph

A Directed Graph that does not contain any cycle. 

Bipartite Graph

A graph in which vertex can be divided into two sets such that vertex in each set does not contain any edge between them.

Weighted Graph

A graph in which the edges are already specified with suitable weight

can be further classified as directed weighted graphs and undirected weighted graphs.

Adjacency Matrix

Adjacency List

Representation of Graphs (two ways to store a graph)

Adjacency Matrix

In this method, the graph is stored in the form of the 2D matrix where rows and columns denote vertices. Each entry in the matrix represents the weight of the edge between those vertices

Adjacency List

This graph is represented as a collection of linked lists. There is an array of pointer which points to the edges connected to that vertex.

Insertion of Nodes/Edges in the graph

Deletion of Nodes/Edges in the graph

Searching on Graphs

Traversal of Graphs

Basic Operations on Graphs

Maps

topological sort

State Transition Diagram

Usage of graphs

State Transition Diagram

•       Diagram represents what can be the legal moves from current states. In-game of tic tac toe this can be used.

Directed Acyclic Graph.

When various tasks depend on each other then this situation can be represented using a — and we can find the order in which tasks can be performed using topological sort.

pathfinding

data clustering

network analysis

machine learning

They can be used to model and solve a wide range of problems, including

graph theory or related algorithms.

Graphs can be complex and difficult to understand, especially for people who are not familiar with

Sports

Social media

transportation

cybersecurity

They can be used in a variety of fields such as