Loading...

**CIA 1 A**

Unit-1 INTRODUCTION TO GRAPHS

NAME : ALAN SINGH

REGISTRATION NUMBER: 22215010

CLASS: 4 BCA - A

Loading...

Loading...

INDEX

1.) INTRODUCTION TO GRAPH

2.)COMPONENTS OF A GRAPH

3.)GRAPH ISOMORPHISM IN DISCRETE MATHEMATICS

4.)CONDITIONS OF GRAPH ISOMORPHISM

5.)CONDITIONS WHICH ARE DESCRIBED

6.)EXAMPLES

1.) INTRODUCTION TO GRAPH

2.)COMPONENTS OF A GRAPH

3.)GRAPH ISOMORPHISM IN DISCRETE MATHEMATICS

4.)CONDITIONS OF GRAPH ISOMORPHISM

5.)CONDITIONS WHICH ARE DESCRIBED

6.)EXAMPLES

**Introduction:**

A Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph is composed of a set of vertices(

**V**) and a set of edges(

**E**). The graph is denoted by

**G(V, E).**

Graph data structures are a powerful tool for representing and analyzing complex relationships between objects or entities. They are particularly useful in fields such as social network analysis, recommendation systems, and computer networks. In the field of sports data science, graph data structures can be used to analyze and understand the dynamics of team performance and player interactions on the field.

Imagine a game of football as a web of connections, where players are the nodes and their interactions on the field are the edges. This web of connections is exactly what a graph data structure represents, and it’s the key to unlocking insights into team performance and player dynamics in sports.

Components of a Graph

**Vertices:**Vertices are the fundamental units of the graph. Sometimes, vertices are also known as vertex or nodes. Every node/vertex can be labeled or unlabeled.**Edges:**Edges are drawn or used to connect two nodes of the graph. It can be ordered pair of nodes in a directed graph. Edges can connect any two nodes in any possible way. There are no rules. Sometimes, edges are also known as arcs. Every edge can be labelled/unlabeled.

**Graph isomorphism in Discrete Mathematics**

The isomorphism graph can be described as a graph in which a single graph can have more than one form. That means two different graphs can have the same number of edges, vertices, and same edges connectivity. These types of graphs are known as isomorphism graphs. The example of an isomorphism graph is described as follows:

**Graph isomorphism in Discrete Mathematics**

The isomorphism graph can be described as a graph in which a single graph can have more than one form. That means two different graphs can have the same number of edges, vertices, and same edges connectivity. These types of graphs are known as isomorphism graphs. The example of an isomorphism graph is described as follows:

*Conditions for graph isomorphism*Any two graphs will be known as isomorphism if they satisfy the following four conditions:

- There will be an equal number of vertices in the given graphs.
- There will be an equal number of edges in the given graphs.
- There will be an equal amount of degree sequence in the given graphs.
- If the first graph is forming a cycle of length k with the help of vertices {v1, v2, v3, …. vk}, then another graph must also form the same cycle of the same length k with the help of vertices {v1, v2, v3, …. vk}.

*Sufficient Conditions for Graph isomorphism*

*If we want to prove that any two graphs are isomorphism, there are some sufficient conditions which we will provide us guarantee that the two graphs are surely isomorphism. When the two graphs are successfully cleared all the above four conditions, only then we will check those graphs to sufficient conditions, which are described as follows:*- If the complement graphs of both the graphs are isomorphism, then these graphs will surely be an isomorphism.
- If the adjacent matrices of both the graphs are the same, then these graphs will be an isomorphism.
- If the corresponding graphs of two graphs are obtained with the help of deleting some vertices of one graph, and their corresponding images in other images are isomorphism, only then these graphs will not be an isomorphism.