Graduate
  1. Real Analysis  1.1. Set Theory and Logic  1.1.1. Sets and Operations  1.1.2. Relations and Functions  1.1.3. Logic and Quantifiers  1.1.4. Cardinality of Sets  1.2. Metric Spaces  1.2.1. Open and Closed Sets  1.2.2. Convergence of Sequences  1.2.3. Continuous Functions in Metric Spaces  1.2.4. Compactness and Completeness in Metric Spaces in Real Analysis  1.3. Sequence and Series  1.3.1. Convergence of Sequences  1.3.2. Infinite Series  1.3.3. Uniform Convergence  1.3.4. Power Series  1.4. Differentiation  1.4.1. Mean Value Theorems  1.4.2. Taylor Series  1.4.3. Functions of Several Variables  1.4.4. Partial Derivatives  1.5. Integration  1.5.1. Riemann and Lebesgue Integration  1.5.2. Improper Integrals  1.5.3. Measure Theory  1.5.4. Fubini’s Theorem  1.6. Functional Analysis  1.6.1. Banach Spaces  1.6.2. Hilbert Spaces  1.6.3. Operators on Spaces  1.6.4. Spectral Theory
  2. Abstract Algebra  2.1. Groups  2.1.1. Definitions and Examples in Groups in Abstract Algebra  2.1.2. Group Homomorphisms  2.1.3. Normal Subgroups  2.1.4. Sylow Theorems  2.2. Rings and Fields  2.2.1. Ideals and Factor Rings  2.2.2. Field Extensions  2.2.3. Galois Theory  2.2.4. Polynomial Rings  2.3. Modules  2.3.1. Module Homomorphisms  2.3.2. Free Modules  2.3.3. Tensor Products  2.3.4. Exact Sequences  2.4. Linear Algebra  2.4.1. Vector Spaces  2.4.2. Eigenvalues and Eigenvectors  2.4.3. Inner Product Spaces  2.4.4. Diagonalization
  3. Topology  3.1. General Topology  3.1.1. Open and Closed Sets  3.1.2. Compactness and Connectedness  3.1.3. Continuous Maps  3.1.4. Separation Axioms  3.2. Algebraic Topology  3.2.1. Fundamental Groups  3.2.2. Homotopy and Homology  3.2.3. Simplicial Complexes  3.2.4. Exact Sequences in Homology  3.3. Differential Topology  3.3.1. Manifolds  3.3.2. Smooth Functions  3.3.3. Tangent and Cotangent Spaces  3.3.4. Vector Bundles
  4. Differential Equations  4.1. Ordinary Differential Equations  4.1.1. First-Order Equations  4.1.2. Second-Order Linear Equations  4.1.3. Systems of Differential Equations  4.1.4. Stability Analysis  4.2. Partial Differential Equations  4.2.1. Classification of PDEs  4.2.2. Fourier Series  4.2.3. Green's Functions  4.2.4. Method of Characteristics  4.3. Dynamical Systems  4.3.1. Stability Theory  4.3.2. Limit Cycles  4.3.3. Chaos Theory  4.3.4. Bifurcation Theory
  5. Probability and Statistics  5.1. Probability Theory  5.1.1. Random Variables  5.1.2. Probability Distributions  5.1.3. Law of Large Numbers  5.1.4. Central Limit Theorem  5.2. Statistical Inference  5.2.1. Hypothesis Testing  5.2.2. Confidence Intervals  5.2.3. Bayesian Methods  5.2.4. Maximum Likelihood Estimation  5.3. Stochastic Processes  5.3.1. Markov Chains  5.3.2. Brownian Motion  5.3.3. Poisson Processes  5.3.4. Martingales
  6. Numerical Analysis  6.1. Numerical Solutions of Equations  6.1.1. Root Finding  6.1.2. Iterative Methods  6.1.3. Convergence Analysis  6.1.4. Error Bounds in Numerical Solutions of Equations  6.2. Numerical Linear Algebra  6.2.1. Matrix Factorizations  6.2.2. Eigenvalue Computations  6.2.3. Sparse Matrices  6.2.4. Preconditioning Techniques  6.3. Numerical Integration and Differentiation  6.3.1. Quadrature Methods  6.3.2. Finite Differences  6.3.3. Error Analysis in Numerical Integration and Differentiation  6.3.4. Adaptive Methods
  7. Complex Analysis  7.1. Complex Numbers  7.1.1. Polar Form  7.1.2. Complex Conjugates  7.1.3. Exponential Form  7.1.4. Roots of Unity  7.2. Analytic Functions  7.2.1. Cauchy-Riemann Equations  7.2.2. Power Series  7.2.3. Conformal Mappings  7.2.4. Harmonic Functions  7.3. Integration in the Complex Plane  7.3.1. Cauchy’s Theorem  7.3.2. Residue Theorem  7.3.3. Contour Integration  7.3.4. Integral Transforms
  8. Mathematical Logic and Foundations  8.1. Propositional Logic  8.1.1. Truth Tables  8.1.2. Logical Equivalences  8.1.3. Proof Techniques in Propositional Logic  8.1.4. Resolution  8.2. Predicate Logic  8.2.1. Quantifiers in Predicate Logic  8.2.2. Formal Systems in Predicate Logic  8.2.3. Completeness and Soundness  8.2.4. Model Theory  8.3. Set Theory  8.3.1. Cardinality and Ordinality  8.3.2. Axiomatic Systems  8.3.3. Zermelo-Fraenkel Set Theory  8.3.4. Forcing
  9. Optimization  9.1. Linear Programming  9.1.1. Simplex Method  9.1.2. Duality in Linear Programming  9.1.3. Sensitivity Analysis  9.1.4. Interior Point Methods  9.2. Nonlinear Programming  9.2.1. Gradient Descent  9.2.2. Lagrange Multipliers  9.2.3. Convex Optimization  9.2.4. Quadratic Programming  9.3. Combinatorial Optimization  9.3.1. Graph Algorithms  9.3.2. Integer Programming  9.3.3. Network Flows  9.3.4. Approximation Algorithms
  10. Discrete Mathematics  10.1. Graph Theory  10.1.1. Graph Representations  10.1.2. Planarity and Coloring  10.1.3. Shortest Path Algorithms  10.1.4. Network Flows  10.2. Combinatorics  10.2.1. Permutations and Combinations  10.2.2. Generating Functions  10.2.3. Recurrence Relations  10.2.4. Inclusion-Exclusion Principle  10.3. Cryptography  10.3.1. Number Theory Applications in Cryptography  10.3.2. Symmetric and Asymmetric Cryptography  10.3.3. RSA and Elliptic Curve Cryptography  10.3.4. Post-Quantum Cryptography

Graduate → Discrete Mathematics → Graph Theory ↓


Graph Representations


Graph theory is a fascinating field within discrete mathematics that studies the properties of graphs - mathematical structures used to model paired relationships between objects. Before diving into complex concepts, it is important to understand the basic idea of graph representation.

What is a graph?

A graph G consists of a set V called vertices or nodes, and a set E of edges or links connecting pairs of vertices. A graph can be defined mathematically as follows:

    g = (v, e)

Here, V is the collection of vertices, and E is the collection of edges.

Types of graphs

There are different types of graphs depending on their structure and properties. Some of the major categories are as follows:

  • Undirected graph: A graph whose edges have no direction.
  • Directed graph (digraph): A graph in which each edge has a direction.
  • Weighted graph: A graph that has weights associated with its edges.
  • Unweighted graph: All edges have the same weight, usually denoted as 1.
  • Multigraphs: Graphs where multiple edges are allowed between two nodes.
  • Simple graph: A graph with no loops and multiple edges.

Visual representation of the graph

Visual representations of graphs help in understanding and interpreting their structure. Consider an undirected graph G with vertices {A, B, C, D} and edges {(A, B), (A, C), (B, D), (C, D)}

    Vertex: { A, B, C, D }
    Edges: { (A, B), (A, C), (B, D), (C, D) }
A B C D

In the above figure the circles represent vertices and lines represent edges.

Adjacency matrix

One way to represent a graph is through an adjacency matrix. This is a square matrix used to represent a finite graph, where the elements indicate whether pairs of vertices in the graph are adjacent or not.

If A is an adjacency matrix of a graph G, and A[i][j] is equal to 1, it indicates that there is an edge from vertex i to vertex j. If A[i][j] is equal to 0, there is no edge. For undirected graphs, the matrix is symmetric.

    Adjacency matrix for the above graph:
    a B C D
  A 0 1 1 0
  B 1 0 0 1
  C 1 0 0 1
  D 0 1 1 0

Adjacency list

Another way to represent a graph is through an adjacency list. It is an array of lists that is used to represent a graph. The size of the array is equal to the number of vertices.

Each vertex in the array has a list of vertices to which it is connected. Adjacency lists are particularly useful for representing sparse graphs.

    Adjacency list for the above graph:
    
    A: B, C
    Bad
    C: a, d
    D: B, C

Incidence matrix

The incidence matrix is another way to represent a graph. In the incidence matrix, rows represent vertices and columns represent edges. Each edge is represented by specifying which vertices it connects.

For undirected graphs, each edge contributes two entries to the incidence matrix, one for each endpoint. If the graph is directed, a sign (+ or -) can be used to indicate the direction.

    Incidence matrix for the above graph:
    (a, b) (a, c) (b, d) (c, d)
  A 1 1 0 0
  B 1 0 1 0
  C 0 1 0 1
  D 0 0 1 1

Graph isomorphism

Two graphs are called isomorphic if there is a one-to-one correspondence between their vertex sets that preserves closeness. Essentially, isomorphic graphs are structurally identical, just with different labels.

Applications of graph representations

Graph representation is important in various fields such as computer science, biology, social sciences, and logistics. Here are some applications:

  • Network analysis: Representing computer or social networks.
  • Circuit design: Understanding and designing circuits through electrical networks.
  • Scheduling problems: Optimizing tasks and managing resources efficiently.
  • Biology: Modelling of ecosystems, genetic structure or neural networks.

Conclusion

Understanding graph representation is fundamental to studying more advanced topics in graph theory. Identifying different ways to describe and analyze graphs allows mathematicians and scientists to effectively apply this knowledge in a variety of domains. Graph theory remains a highly active and important area in mathematical research, with its applications continually growing with the development of technology and society.


Graduate → 10.1.1


U
username
0%
completed in Graduate

← Prev (10.1)
Graph Theory
Next (10.1.2) →
Planarity and Coloring

Comments 



Graph Representations

https://www.buddymath.com/g/10.1.1?bmal=en