GRAPH THEORY

FINAL YEAR PROJECT

PRESENTED BY:
Saba Kiran Shakoor
Mahnoor Anwer
Hadiqa Shafqat
Haani Fatima
Umama Tanveer
 Contents

o Background Of Graph Theory

o Introduction Of Group Theory
o Basic Concepts In Graph Theory
o Types Of Graphs
o Applications Of Graph Theory
o Topological Indices In
Chemical Graph Theory
o Types OF Topological Indices
o Silicate Triangle Fractal Network (Sin)
o Conclusion
•.

Background Of Graph Theory

The history of graph theory may be specifically traced to 1735, when the
Leonhard Euler solved the Königsberg bridge problem.

The Königsberg bridge problem:

 Historical Background:
• Originated in 18th-century Königsberg (now Kaliningrad, Russia).
• Involved seven bridges connecting different parts of the city.
• Challenge: devise a walk that crossed each bridge exactly once.
 Background Of Graph Theory Contd..
 Euler's Contribution:
• Eulerian Path: A path that visits every edge exactly once.
• Eulerian Circuit: An Eulerian path that starts and
ends at the same vertex.
 Euler's Theorem:
A connected graph has an Eulerian circuit if and only if:
• All vertices have an even degree (even number
of edges connected).
 Eulerian Path:
 A connected graph has an Eulerian path if and only if:
• two vertices have an odd degree.
• All other vertices have even degrees.
 Background Of Graph Theory Contd..

 Königsberg Bridge Problem Result:

In the Königsberg graph:
• Since more than two vertices have an odd
degree:
• It is impossible to have an Eulerian path or
circuit
Therefore, crossing all bridges exactly once is
impossible.
 Introduction of Group Theory

 Graph theory is a branch of mathematics that studies the properties and

relationships of graphs.
 A graph is a collection of vertices (or nodes) connected by edges (or links).
 Introduction of Group Theory
Examples:
 Social Networks:
In Facebook, users (vertices) are connected by friendships (edges).
Edges: Friendships or connections between users.
Vertices: Users.

 Molecular structures:
For a molecule like ethylene (C₂H₄), we can represent it as a graph
Vertices: C (carbon) and H (hydrogen) atoms.
Edges: Single bonds between atoms (e.g., C-C, C-H).
 Basic Concepts In Graph Theory

GRAPH

DEGREE
VERTEX

EDGE WALK
ORDER OF
GRAPH PATH

SIZE OF CYCLE
GRAPH
 Basic Concepts in Graph Theory
 Graph: A collection of vertices (nodes) and edges (connections between nodes).
 Vertex (Node): A fundamental unit of a graph, representing an entity.
 Edge: A connection between two vertices, can be directed (one-way) or undirected (two-
way).
 Order Of A Graph :refers to the number of vertices (or nodes) in the graph.
 Size Of A Graph :refers to the number of edges (or connections) in the graph.
 Basic Concepts in Graph Theory Contd..
Degree:
 The number of edges connected to a vertex.

Walk:
 sequence of vertices and edges of a graph.
 Edge and Vertices can both be repeated.
 Walk can be open(starting and ending vertices are different)
or closed(starting and ending vertices are identical ).
 Basic Concepts in Graph Theory Contd..
Path :
• A walk with no repeated vertex and no repeated edges.
Cycle:
• A graph such that we do not repeat a vertex,
nor we repeat an edge
but the starting and ending vertex must be same
 Types of Graphs
There are various types of graphs in graph theory, some of these are:
 Null Graph:
A null graph, is a type of graph in which we have vertices but there is no edge.

 Trivial Graph:
A trivial graph is the simplest graph, consisting of exactly one vertex and no edges.

 Simple Graph:
A simple graph is a graph in which each pair of vertices is connected by at most one edge,
and no vertex has an edge to itself.
 Directed Graph: A directed graph, also known as a digraph,
is a type of graph where the edges have a direction.

 Undirected Graph: An undirected graph is a type of graph in which the edges have no
direction.

 Complete Graph: If every vertex in a graph G is linked to every other vertex in the
graph, then the graph is said to be complete.
 Weighted Graphs: A weighted graph is a type of graph in which each edge is
1
assigned a weight (or cost).
4 2

 Bipartite Graphs: A bipartite graph is a type of graph where the every edge in a graph
connects a vertex in one set to a vertex in the other set.

 Cycle graph: A cycle graph, also known as a circular graph, is a type of graph that forms
a single cycle.
 APPLICATIONS OF GRAPH THEORY
 Material Science
 Description:
Fractal geometry helps us understand the properties of materials like silicates,
found in ceramics and glass.
 Example:
Fractal analysis of silicate structures improves ceramic strength and
thermal resistance.
 Applications of graph theory(contd..)
 Efficient Networks with Fractal Geometry
 Description:
Fractal structures enable optimal network design in telecommunications,
featuring:-
 Self-similar patterns for efficient data transfer
 Scalable and adaptable networks
 Reduced signal loss and interference
 Applications of graph theory(contd..)
 Fractal Geometry in Nature
 Description:
Fractal geometry reveals stunning patterns in nature,
such as:-
 Coastlines
 Snowflakes
 Mountain ranges
Applications of graph theory(contd..)
 Fractal Networks in Living Systems
 Description:
Fractal geometry models the branching patterns of:-
 Blood vessels: efficient oxygen delivery
 Nerve cells: complex signal transmission
 Tree roots: optimal nutrient absorption

These applications illustrate how graph theory and fractal

structures can provide insights and solutions across various fields.
 Topological Indices in Chemical
Graph Theory
Topological indices are numerical values that characterize the connectivity and
properties of chemical compounds, aiding in the understanding of their behavior.
Various indices, such as the Zagreb indices and the Randic index, are introduced as
important tools for analyzing molecular graphs.
 Types of Topological Indices
Degree-based Indices Edge-based Indices

First Zagreb Index Geometric Arthimetic Index

Second Zagreb Index Frogotton Index

Sum Connectivity Index Augmented Zagreb Index

Platt Index Exponential Atom Bond Connectivity

Randic Index Exponential Second Zagreb Index

Atom Bond Connectivity Exponential Platt Index

Harmonic Index
FIRST AND SECOND SUM CONNECTIVITY
ZAGREB INDICES INDEX
 Introduced by Gutman and  Proposed by Zhou and Trinajstić.
Trinajstić in 1972.  This index gives us a measure of
how connected the graph is.
 Applications
First Zagreb ABC
Second
Index connectivity
Zagreb index
 Drug design for  Establish relation Predict properties in
analyzing between molecular organic compounds
molecular structure and such as:
structure. properties such as: 1. Boiling points
 Lead compound 1. Boiling point 2. Melting points
optimization,
2. Melting point 3. Solubility
prediction of drug
likeness. 3. Viscosity 4. Surface tension.
4. Surface tension.
 PLATT INDEX RANDIC INDEX
 This index helps in  A more generalized index that
understanding the overall
can be adjusted using a real
connectivity of the graph.
number
 Applications

Platt Index Randic Index

Used to model several physical Predict biological activities and
properties of organic properties of molecules like:
compounds such as: 1. Model viscosity
1. Boiling and melting points 2. Melting and boiling points
2. Molecular surface area or 3. Surface tension
volume.
4. Solubility
5. Density.
 ATOM BOND HARMONIC
CONNECTIVITY INDEX
(ABC) INDEX
 This index measures how well  This index is useful in
the atoms (vertices) are studying the stability of
connected in a chemical chemical compounds.
structure.
 Applications

ABC connectivity Harmonic Index

 Complex Network Analysis  Boiling and Melting Points: The
• Social and Communication harmonic index is also applied to
Networks: In complex networks, the predict the boiling points and
ABC index is applied to measure the melting points of compounds by
connectivity of nodes within a correlating their molecular
network, such as social media connectivity with physical
platforms or communication properties. Molecules with higher
networks. It helps in understanding harmonic index values typically
how well-connected individuals or have stronger intramolecular
hubs are, which influences the forces, requiring more energy to
spread of information or influence.
change states.
 GEOMETRIC
ARITHMETIC (GA) FORGOTTEN
INDEX INDEX
 This index combines  This index helps in
geometric and arithmetic understanding the
means to provide insights into distribution of vertex degrees.
the graph's structure.
 Applications

G/A INDEX FORGOTTEN INDEX

 Eco-Toxicology: The GA index  Can be used to predict
also aids in predicting the toxicity
of new chemical compounds. By properties of polymers by
analyzing molecular connectivity, analyzing the connectivity
researchers can estimate how and complexicity of their
harmful these compounds might molecule structure.
be to organisms or ecosystems.
 F-index can be applied to
predict thermal stability,
access elasticity, model
viscosity.
 AUGMENTED EXPONENTIAL
ZAGREB INDEX INDICES
(AZI)  These indices include variations of the
ABC, second Zagreb, and Platt indices,
 This index is a more complex
where exponential functions are
measure of connectivity.
applied to the calculations.
 Applications
Exponential Indices
Exponential ABC index:
 Thermodynamic properties.
Exponential M2:
 Gene Regulatory Networks.
Exponential Platt index:
 Social Networks.
Silicate Triangle
Fractal Network
(Sin)
 Introduction to Fractal Geometry
Fractal geometry is a field of mathematics that deals with shapes and patterns that are self-similar
and exhibit complex structures at different scales.

 Key Features of Fractals:

1. Self-Similarity: Fractals look similar at various levels of magnification.
2. Infinite Complexity: The detail increases as you zoom in.
 Natural Examples:
Fractals appear in nature, such as:
1. Snowflakes: Each flake has a complex, repeating structure.
2. Trees: The branching pattern of trees often exhibits self-similarity.
3. Coastlines: The jagged outline of coastlines can appear similar at different scales.
 Formation of silicate triangle
fractal network (from si0 to sin)
 Drawing a Silicate triangle fractal network involves representing the
structural formation of silicon-oxygen tetrahedrons in a fractal pattern.
 To draw the n-th iteration of a Silicate triangle fractal network (Sin​), we
need to recursively construct the fractal pattern according to specific
rules.
 Formation Of Silicate Triangle Fractal
Network (From Si0 To Sin)
 Steps for Drawing (Sin)​:

1. Initiator Si0​:
 Draw a single silicon atom (Si) at the center with four oxygen atoms
around it in a tetrahedral configuration.
 Formation of silicate triangle fractal
network (from si0 to sin)
2. First Iteration (Si1)​:
 Connect a silicon atom to each of the oxygen atoms from the initiator
Si0​. Each silicon atom forms a new tetrahedron.
 Formation of silicate triangle fractal
network (from si0 to sin)
4. General n-th Iteration:
 Continue this process. For each oxygen atom that is not bonded to a silicon
atom in the previous iteration, add a new silicon atom and form new
tetrahedrons.
 The network expands in a fractal manner, with the number of tetrahedrons
growing exponentially with each iteration.
 Fractal dimension
 The fractal dimension is a way to measure how complex a fractal is. It tells us how the
detail in a pattern changes with the scale at which it is measured.
 The formula to calculate the fractal dimension (D) is: logN by log1/r , where N is the
number of boxes intersecting the object and r is the size of the box

Example:
For the silicate triangle fractal network

 If N = 3 (the number of boxes) and r = 1/2 (the size of the box),

we can estimate the fractal dimension: D ≈ N/1/r = 3/2 ≈ 1.584

 Formation of silicate triangle fractal
network (from si0 to sin)
Drawing Method
1. Manual Drawing:
 Start with a central point for Si0 and build outwards.
 For each iteration, systematically add more silicon atoms around the existing oxygen
atoms.
 Use geometric shapes to maintain the tetrahedral structure.
2. Using a Fractal Generator or Drawing Software:
 You can use software like Python with fractal libraries , CAD software, or graphic design
tools to create the fractal pattern programmatically.
 Future research opportunities
The paper on the silicate triangle fractal network (Si n) presents several avenues for future research that can
expand the understanding and application of topological indices in complex networks. Here are some
potential research opportunities derived from the paper's findings:
• Exploration of Additional Fractal Structures
• Correlation with Chemical Properties
• Advanced Computational Techniques
• Interdisciplinary Applications
• Investigation of Dynamic Properties
• Comparative Studies
These future research opportunities highlight the potential for further exploration and application of
topological indices in understanding complex networks, particularly in the context of fractal structures.