Undergraduate
  1. Algebra  1.1. Linear Algebra  1.1.1. Matrices  1.1.2. Determinants  1.1.3. Systems of Linear Equations  1.1.4. Vector Spaces  1.1.5. Linear Transformations  1.1.6. Eigenvalues and Eigenvectors  1.1.7. Diagonalization  1.1.8. Inner Product Spaces  1.1.9. Orthogonality and Orthonormal Bases  1.1.10. Singular Value Decomposition  1.2. Abstract Algebra  1.2.1. Groups  1.2.2. Subgroups  1.2.3. Cyclic Groups  1.2.4. Permutation Groups  1.2.5. Homomorphisms  1.2.6. Normal Subgroups  1.2.7. Rings  1.2.8. Fields  1.2.9. Ideals and Quotient Rings  1.2.10. Polynomial Rings  1.2.11. Vector Spaces over Fields  1.2.12. Modules  1.2.13. Galois Theory
  2. Calculus  2.1. Differential Calculus  2.1.1. Limits  2.1.2. Continuity  2.1.3. Derivatives  2.1.4. Chain Rule  2.1.5. Implicit Differentiation  2.1.6. Applications of Derivatives  2.1.7. Optimization Problems  2.1.8. Mean Value Theorem  2.2. Integral Calculus  2.2.1. Definite Integrals  2.2.2. Indefinite Integrals  2.2.3. Techniques of Integration  2.2.4. Improper Integrals  2.2.5. Applications of Integration  2.2.6. Arc Length and Surface Area  2.3. Multivariable Calculus  2.3.1. Partial Derivatives  2.3.2. Gradient  2.3.3. Divergence and Curl  2.3.4. Multiple Integrals  2.3.5. Line Integrals  2.3.6. Surface Integrals  2.3.7. Green's Theorem  2.3.8. Stokes' Theorem  2.3.9. Divergence Theorem  2.3.10. Jacobians
  3. Differential Equations  3.1. Ordinary Differential Equations  3.1.1. First Order Differential Equations  3.1.2. Higher Order Differential Equations  3.1.3. Systems of Differential Equations  3.1.4. Series Solutions  3.1.5. Numerical Methods for ODEs  3.2. Partial Differential Equations  3.2.1. Heat Equation  3.2.2. Wave Equation  3.2.3. Laplace Equation  3.2.4. Separation of Variables  3.2.5. Fourier Transform Methods
  4. Real Analysis  4.1. Sequences and Series  4.1.1. Convergence of Sequences  4.1.2. Series Tests  4.1.3. Power Series  4.1.4. Uniform Convergence  4.2. Functions of Real Variables  4.2.1. Limits and Continuity  4.2.2. Uniform Continuity  4.2.3. Differentiation in Functions of Real Variables  4.2.4. Riemann Integration  4.2.5. Lebesgue Integration
  5. Complex Analysis  5.1. Complex Numbers  5.1.1. Polar Form  5.1.2. Exponential Form  5.2. Functions of a Complex Variable  5.2.1. Analytic Functions  5.2.2. Cauchy-Riemann Equations  5.2.3. Contour Integrals  5.2.4. Cauchy's Integral Theorem  5.2.5. Residue Theorem  5.2.6. Conformal Mapping
  6. Probability and Statistics  6.1. Probability Theory  6.1.1. Basic Probability Concepts  6.1.2. Random Variables  6.1.3. Probability Distributions  6.1.4. Expectation and Variance  6.1.5. Conditional Probability and Bayes' Theorem  6.2. Statistics  6.2.1. Descriptive Statistics  6.2.2. Inferential Statistics  6.2.3. Hypothesis Testing  6.2.4. Regression Analysis  6.2.5. ANOVA
  7. Numerical Methods  7.1. Root-Finding Algorithms  7.2. Numerical Integration  7.3. Numerical Differentiation  7.4. Numerical Solutions to Differential Equations  7.5. Matrix Computations  7.6. Interpolation and Extrapolation
  8. Discrete Mathematics  8.1. Logic and Proof  8.2. Combinatorics  8.3. Graph Theory  8.4. Boolean Algebra  8.5. Recurrence Relations
  9. Linear Programming and Optimization  9.1. Simplex Method  9.2. Duality  9.3. Integer Programming  9.4. Nonlinear Optimization
  10. Topology  10.1. Metric Spaces  10.2. Topological Spaces  10.3. Continuity and Homeomorphisms  10.4. Compactness  10.5. Connectedness
  11. Geometry  11.1. Euclidean Geometry  11.2. Differential Geometry  11.3. Non-Euclidean Geometry  11.4. Projective Geometry
  12. Mathematical Physics  12.1. Fourier Series  12.2. Laplace Transforms  12.3. Applications of Differential Equations  12.4. Special Functions
  13. Set Theory and Logic  13.1. Sets and Subsets  13.2. Relations and Functions  13.3. Cardinality  13.4. Formal Logic  13.5. Zermelo-Fraenkel Set Theory
  14. Functional Analysis  14.1. Normed Spaces  14.2. Banach Spaces  14.3. Hilbert Spaces  14.4. Linear Operators

Undergraduate → Discrete Mathematics ↓


Graph Theory


Graph theory is a fascinating field of mathematics that deals with the study of graphs. Graphs are mathematical structures used to model paired relationships between objects. They are composed of vertices, also called nodes, and edges, which connect pairs of vertices. Graph theory has applications in various fields such as computer science, biology, social sciences, transportation, and many more.

Basic concepts

Top and sides

In graph theory, a graph G is defined as an ordered pair G = (V, E), where:

  • V is a set of vertices.
  • E is a set of edges, where each edge is a pair of vertices.

For example, consider a graph in which the vertices represent cities and the edges represent roads connecting the cities.

Visual example

In the above example, the circles represent vertices, and the lines represent edges connecting the vertices.

Types of graphs

  • Undirected Graph: In an undirected graph, edges have no direction. Edge (u, v) is the same as (v, u).
  • Directed Graph (Digraph): In a directed graph, each edge has a direction. Here, edge (u, v) is different from (v, u).

Visual example: guided vs. unguided

The left side of the above visual illustration shows a directed graph, while the right side shows an undirected graph.

Paths and cycles

On the way of

A path in a graph is a sequence of vertices connected by edges. A path is defined as v1, v2, v3, ..., vn where (vi, vi+1) is an edge for all i. Paths are fundamental concepts in determining how entities are connected in a graph.

Bicycle

A cycle is a path that starts and ends at the same vertex. It is a closed path. Cycles are important in many algorithms, especially in detecting infinite loops.

Example in graph

In the graph shown above, a graph represents a cycle that spans the vertices. This cycle starts and ends at the same vertex.

Affiliations and components

A graph is said to be connected if there is a path from any vertex in the graph to any other vertex. If a graph is not connected, it has many connected components, where each component is a subgraph in which any two vertices are connected to each other, but there is no relationship between vertices in different subgraphs.

Visual example of connected components

The two sets of connected vertices in the above visualization represent the concept of graph components. Each pair forms a separate connected subgraph within the larger graph.

Directed acyclic graphs (DAGs)

A directed acyclic graph, or DAG, is a type of directed graph with no cycles. This property makes DAGs suitable for representing structures with dependencies, such as task scheduling, dependency resolution, and Bayesian networks.

An important feature of DAGs is topological ordering, where we arrange the vertices in a linear order such that for every directed edge (u, v), the vertex u comes before the vertex v.

Example of a DAG

The above demonstration shows a directed acyclic graph without any cycles, which shows its function for applications such as dependency management.

Graph coloring

Graph coloring is the process of assigning colors to the vertices of a graph such that no two adjacent vertices share the same color. The minimum number of colors required to color a graph is called the chromatic number of the graph. This concept is important in solving problems where resources need to be allocated without any conflict.

Graph coloring example

Consider the task of scheduling classes by deadline. You have to ensure that no two classes are scheduled at the same time that have the same students. This is similar to coloring a graph.

The above example uses three colors to ensure that no two adjacent vertices have the same color, thus demonstrating the graph coloring process.

Trees and forests

A tree is a special type of graph that is connected and acyclic. A tree with n vertices has exactly n - 1 edges. Trees are essential structures in graph theory, widely used in data structures, algorithms, and network design.

  • Rooted tree: A rooted tree is a tree in which one vertex is designated as the root, and each edge is directed away from the root.
  • Forest: A forest is a disjoint group of trees.

Tree example

The above graph shows a tree with a single root node, from which all branches extend directly.

Conclusion

Graph theory is a wide and interesting field in discrete mathematics. It enables us to understand and unravel complexities in networks, whether they are social connections, communications, or computing systems. This comprehensive exploration of the fundamental concepts of graph theory, augmented with simple illustrations, provides insights into limitless applications spanning various domains. Whether rendering the web, optimizing logistics, designing algorithms, or delving into the structures of proteins and DNA, graph theory remains a cornerstone for innovation and problem-solving in the modern world.


Undergraduate → 8.3


U
username
0%
completed in Undergraduate

← Prev (8.2)
Combinatorics
Next (8.4) →
Boolean Algebra

Comments 



Graph Theory

https://www.buddymath.com/ug/8.3?bmal=en