"In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects."
Graph theory has many real-world applications, such as modeling social networks, computer networks, transportation networks, and more.
Basic Definitions: Simple graphs, directed graphs, weighted graphs, degree of a vertex, adjacency matrix and degree matrix.
Eulerian Graphs and Hamiltonian Graphs: This topic deals with the theory behind traversing all edges of a graph.
Planar Graphs: Planar graphs are those which can be drawn on a plane with no edges crossing. Hence, this topic is all about the theory behind drawing such graphs.
Trees and Forests: Graphs without cycles are known as trees, and a forest is a collection of trees. This topic delves into the basics of trees and their properties.
Connectivity: Graphs which are connected, which means there is a path between any two vertices, are known as connected graphs. This topic deals with how to determine if a graph is connected or not.
Coloring: Coloring in graph theory refers to the assignment of colors to the vertices of a graph. This topic deals with finding the minimum number of colors for a graph and also explores different types of colorings like edge coloring, face coloring etc.
Matching: Finding a set of edges which do not share any vertex is called a matching in graph theory. This topic deals with finding maximum and minimum matching in a graph.
Flows and Cuts: Finding a flow between two vertices in a graph and partitioning the graph into two disjoint subsets is the focus of this topic.
Spanning Trees: A spanning tree of a graph is a subgraph which is a tree and contains all vertices of the original graph. This topic delves into finding spanning trees in a graph.
Graph Algorithms: There are many algorithms that can be applied on graphs like Dijkstra's algorithm, Kruskal and Prim's algorithm, Depth First Search (DFS) and Breadth First Search (BFS) which are used to solve several optimization problems.
Computer Networks: Graph theory is used to analyze and design computer networks such as the Internet, peer-to-peer networks, and wireless sensor networks.
Social Networks: Social networks can be modeled using graph theory, and many studies have been done to analyze properties and behaviors of social networks.
Transportation Networks: Graph theory has many applications in the analysis and design of transportation networks, such as road networks, train networks, and airline routes.
Electrical Networks: Graph theory is used in the analysis and design of electrical networks such as power grids and circuits.
Biological Networks: Many biological systems can be modeled using graph theory, such as neural networks, protein interaction networks, and gene regulation networks.
Business Networks: Graph theory can be used to analyze and design business networks such as supply chains and financial networks.
Chemical Networks: Graph theory is used in the analysis and design of chemical networks such as reaction networks and molecular structures.
Communication Networks: Graph theory can be used to analyze and design communication networks such as telephone networks and broadcast networks.
Computer Science: Graph theory has many applications in computer science such as algorithms and data structures, visualization, and machine learning.
Optimization: Graph theory can be used for optimization problems such as finding the shortest path, maximum flow, and minimum spanning tree.
"A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines)."
"Vertices are connected by edges."
"A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically."
"Undirected graphs have symmetric edges."
"Directed graphs have asymmetric edges."
"Graphs are one of the principal objects of study in discrete mathematics."