GRAPH THEORY Mathematics and Computer Science Project.pptx

This presentation basically tells us how the graph theory is applied on mathematics and computer science

1. GRAPH THEORY Department of Mathematics Dhenkanal Autonomous College Presented By : Kapileswar Sahoo BSc. 3 rd Year Exam roll no : 22MTS015

2. INTRODUCTION : Introduction to Graph Theory : Graphs are the way to formally repreasent a network or a collection of inter connected objects . In mathematics, graphs are defined as ordered pairs with two parts : Vertices & Edges . So What is Graph : It is a set of vertices (nodes) and edges (connections). It looks like this ! G=( V,E ) Where V is a set of nods ,also called vertices and E is a set of edges also called links

3. Basic terminology : 1. VERTEX (nodes): A fundamental unit of a graph . 2. EDGES (link): Connection between two vertices . 3. DEGREE : Number of edges connected to a vertex . 4. Path & Cycle : A sequence of vertices and edges (closed path = cycle). 5. Adjacency & Incidence : Relations between vertices and edges. EXAMPLE: V={ s,u,v,w,x,y,z } E= {( x,s ),( x,v ),( x,u ),( v,w ),( s,u ),( s,v ) ( s,w ),( s,y ),( w, y ) v x u s w z y e

4. Types of graphs : 1. Simple Graph A graph that does not have any loops (edges from a vertex to itself) and does not have multiple edges between any two vertices. 2. Multigraph A graph that allows multiple edges (more than one edge) between the same pair of vertices, but still no loops. 3. Complete Graph ( Kn ) A graph in which every pair of distinct vertices is connected by a unique edge. A complete graph with n vertices is denoted as Kn ​. 4. Weighted Graph A graph in which each edge is assigned a weight (or cost), typically represented as a number. 5. Directed Graph (Digraph) A graph in which edges have a direction, meaning they are ordered pairs of vertices. For example, an edge ( u,v )(u, v)( u,v ) indicates a directed edge from vertex u to vertex v. 6. Undirected Graph A graph in which edges have no direction. The edge between vertex u and vertex v is the same as the edge between vertex v and vertex u.

5. 17. Bipartite Graph A graph whose vertices can be divided into two disjoint sets, such that every edge connects a vertex from one set to a vertex in the other set. No edge exists between two vertices within the same set. 8. Tree A connected acyclic graph, meaning it is a graph with no cycles and is connected. A tree with nnn vertices has n−1n-1n−1 edges. 9. Forest A collection of disjoint trees. Essentially, a forest is an acyclic graph, but it can be disconnected. 10. Planar Graph A graph that can be embedded in the plane such that no edges cross each other. In other words, it can be drawn on a flat surface without any of its edges intersecting. 11. Cyclic Graph A graph that contains at least one cycle. A cycle is a path that begins and ends at the same vertex with no repeated edges or vertices (except for the start and end vertex). 12. Acyclic Graph A graph that contains no cycles. An acyclic graph can be either connected or disconnected. 13. Connected Graph A graph in which there is a path between every pair of vertices. In a connected graph, there is no isolated vertex. 14. Disconnected Graph A graph where at least two vertices have no path between them. It is not possible to travel from every vertex to every other vertex. 17. Bipartite Graph A graph whose vertices can be divided into two disjoint sets, such that every edge connects a vertex from one set to a vertex in the other set. No edge exists between two vertices within the same set. 8. Tree A connected acyclic graph, meaning it is a graph with no cycles and is connected. A tree with nnn vertices has n−1n-1n−1 edges. 9. Forest A collection of disjoint trees. Essentially, a forest is an acyclic graph, but it can be disconnected. 10. Planar Graph A graph that can be embedded in the plane such that no edges cross each other. In other words, it can be drawn on a flat surface without any of its edges intersecting. 11. Cyclic Graph A graph that contains at least one cycle. A cycle is a path that begins and ends at the same vertex with no repeated edges or vertices (except for the start and end vertex). 12. Acyclic Graph A graph that contains no cycles. An acyclic graph can be either connected or disconnected. 13. Connected Graph A graph in which there is a path between every pair of vertices. In a connected graph, there is no isolated vertex.

6. 15. Eulerian Graph A graph that contains an Eulerian circuit, meaning a closed trail that visits every edge exactly once. For a graph to be Eulerian, it must be connected, and all vertices must have an even degree. 16. Hamiltonian Graph A graph that contains a Hamiltonian cycle, meaning a cycle that visits every vertex exactly once and returns to the starting vertex. 17. Regular Graph A graph in which every vertex has the same degree (the same number of edges incident to it). For example, a 3-regular graph means every vertex has 3 edges. 18. Complete Bipartite Graph ( Km,n ) A special kind of bipartite graph where every vertex in the first set is connected to every vertex in the second set. The notation Km,nK _{ m,n } Km,n ​ represents a complete bipartite graph with mmm vertices in one set and nnn vertices in the other. 19. Subgraph A graph formed by a subset of the vertices and edges of another graph. If a graph GGG is a subgraph of graph HHH, then GGG contains some of the vertices and edges from HHH. 20. Self-Loop Graph A graph in which some of the vertices may have edges that connect to themselves. This type of graph is typically found in directed graphs. 15. Eulerian Graph A graph that contains an Eulerian circuit, meaning a closed trail that visits every edge exactly once. For a graph to be Eulerian, it must be connected, and all vertices must have an even degree. 16. Hamiltonian Graph A graph that contains a Hamiltonian cycle, meaning a cycle that visits every vertex exactly once and returns to the starting vertex. 17. Regular Graph A graph in which every vertex has the same degree (the same number of edges incident to it). For example, a 3-regular graph means every vertex has 3 edges. 18. Complete Bipartite Graph ( Km,n ) A special kind of bipartite graph where every vertex in the first set is connected to every vertex in the second set. The notation Km,nK _{ m,n } Km,n ​ represents a complete bipartite graph with mmm vertices in one set and nnn vertices in the other. 19. Subgraph A graph formed by a subset of the vertices and edges of another graph. If a graph GGG is a subgraph of graph HHH, then GGG contains some of the vertices and edges from HHH. 20. Self-Loop Graph A graph in which some of the vertices may have edges that connect to themselves. This type of graph is typically found in directed graphs.

7. Special types of graph

8. Graph representations 1. Adjacency Matrix Description : An adjacency matrix is a square matrix used to represent a graph, where each element of the matrix indicates whether pairs of vertices are adjacent or not in the graph. For a Directed Graph : If there is a directed edge from vertex iii to vertex j, the matrix entry ] [1 0 1] [0 1 0] is 1 (or the weight of the edge if it's a weighted graph), otherwise 0. For an Undirected Graph : The matrix is symmetric because if there is an edge from vertex iii to vertex j, it also exists from vertex j to vertex i .  

9. . Adjacency List Description : An adjacency list is a collection of lists or arrays, one for each vertex in the graph, where each list contains the neighbors (vertices connected by edges) of the corresponding vertex. For a Directed Graph : Each vertex has a list of vertices to which it is connected by outgoing edges. For an Undirected Graph : Each vertex's list contains the vertices it is connected to (without direction). Example : For the graph with vertices A,B,C and edges AB and BC, the adjacency list representation might look like this: 4. Incidence Matrix Description : An incidence matrix is a matrix that represents the relationship between vertices and edges in a graph. It is a binary matrix where each row represents a vertex, and each column represents an edge. If a vertex is incident to an edge, the matrix entry is 1; otherwise, it is 0. For a Directed Graph : For each directed edge, mark the corresponding row with 1 in the column of the destination vertex. For an Undirected Graph : For each edge, both vertices it connects will have a 1 in the corresponding column.

10. Shortest path algoritm 1. Dijkstra’s Algorithm Use case : Works for graphs with non-negative weights. Description : Dijkstra's algorithm finds the shortest path from a starting node to all other nodes in the graph. It uses a greedy approach, visiting nodes in increasing order of distance. Time complexity : O(V^2) with an adjacency matrix or O((V + E) log V) with a priority queue (binary heap). Steps : Set the distance to the starting node as 0 and all others as infinity. Select the node with the smallest tentative distance, mark it as visited, and update the distances to its neighbors . Repeat until all nodes are visited or the destination node is found.

11. 2. Bellman-Ford Algorithm Use case : Can handle graphs with negative edge weights, but no negative weight cycles. Description : The Bellman-Ford algorithm calculates the shortest paths from a source node to all other nodes, relaxing all edges up to V-1 times (where V is the number of vertices). Time complexity : O(V * E). Steps : Initialize distances to infinity, except for the source node, which is set to 0. Repeat V-1 times: for each edge (u, v), if the distance to v can be shortened by taking edge (u, v), update the distance. Check for negative weight cycles by trying to relax edges again; if any edge can still be relaxed, a negative cycle exists. 3. Floyd- Warshall Algorithm Use case : Finds shortest paths between all pairs of nodes. Description : A dynamic programming approach to find the shortest paths between all pairs of nodes in a graph. Time complexity : O(V^3). Steps : Create a distance matrix where the distance from node i to node j is initially set to the weight of the edge (if one exists), or infinity. For each intermediate node k, try to improve the distance between all pairs of nodes ( i , j) by considering whether a path through k is shorter. Repeat for all pairs of nodes.

12. 4. A (A-star) Algorithm * Use case : Works well for pathfinding in weighted graphs, particularly in games or navigation problems (e.g., map-based routing). Description : A* is a heuristic-based algorithm that uses both the actual cost to reach a node and a heuristic estimate of the cost to reach the goal. It is essentially a more optimized version of Dijkstra’s algorithm. Time complexity : O((V + E) log V) in the average case, depending on the quality of the heuristic. Steps : Initialize the open list (nodes to be evaluated) with the start node. At each step, pick the node with the lowest f-cost (g-cost + h-cost) and expand it. Repeat until the destination is reached or the open list is empty. 5. Breadth-First Search (BFS) Use case : Best for finding the shortest path in an unweighted graph. Description : BFS explores the graph level by level, ensuring the shortest path in terms of the number of edges. Time complexity : O(V + E). Steps : Start with the source node and mark it as visited. Explore all its neighbors , then explore the neighbors of those neighbors , and so on, ensuring that each node is only visited once. Keep track of the parent node to reconstruct the shortest path after reaching the destination.

13. APPLICATIONS OF GRAPH THEORY Computer network Social Network Search Engine Artificial intellince And machine Learnning Navigation And Transpotation Optimization etc.

14. THANK YOU