Graph Theory
Graph Theory or Network Theory is a highly important field within discrete mathematics, and in recent times, it has been expanding its scope with endless applications. Naturally advantageous for visualization and algorithm-friendly, it is closely related to computer science and data science. Ironically, proofs often involve more words than equations, making it a subject that mathematics students sometimes find challenging. Regardless of personal preferences, studying it is never a waste of time, and since there are no particular prerequisites, it can be recommended to undergraduate freshmen without burden.
Basics
Spectral
Topology
- Set Representation of Graphs
- Distance, Neighborhood, Diameter, Girth $d$, $N$, $\text{diam}$, $\text{girth}$
- Graph Complement $\overline{G}$
Deterministic Graphs
Named Graphs
- Null Graph and Complete Graph $K_{n}$
- Regular Graph
- Bipartite Graph $G(A,B)$
- Infinite Graph
- Erdős–Gallai Theorem
- Havel–Hakimi Algorithm
- Tree Graph
- Integral Graph
- Perfect Graph
Path Problems
Four Color Problem
- Planar Graphs and Kuratowski’s Theorem
- Graph Coloring and Brooks’ Theorem
- k-Connectivity of Graphs and Menger’s Theorem
- Geometric Dual Graphs
- Abstract Dual Graphs
- Definition of Map in Graph Theory
- Five Color Theorem
- Four Color Map Problem
Nondeterministic Networks
Random Networks
- Families and Properties of Graphs $2^{\binom{n}{2}}$, $\mathscr{G}_{n,m}$
- Random Network $\mathbb{G}$
- Erdős–Rényi Model $\mathbb{G}_{n,m}$
- Scale-Free Networks
- Euclidean Networks
Centrality
Practice
- 🔒(24/10/07) Graph Layouts
- Gephi: Graph Visualization and Analysis Software
- NetworkX: Python Package for Graph Analysis
- Graphs.jl: Julia Package for Graph Analysis
References
- Albert, Barabási. (2002). Statistical mechanics of complex networks
- Barabási. (2016). Network Science
- Brouwer. (2011). Spectra of Graphs
- Frieze. (2015). Introduction to Random Graphs
- Newman. (2010). Networks: An Introduction
- Wilson. (1970). Introduction to Graph Theory
All posts
- Graphs and Networks in Mathematics
- Graph Isomorphism
- Graph Theory: Degree
- Handshaking Lemma Proof
- Shaking Hands Dilemma Proof
- Matrix Representation of Graphs
- Graphical Set Notation
- Subgraph
- Graph Complement
- Null Graphs and Complete Graphs
- Regular Graph
- Bipartite Graph
- Infinite Graph
- Walks, Trails, Paths, and Cycles in Graph Theory
- Distance, Neighborhood, Diameter, Perimeter in a Graph
- Orientation of Graphs
- Proof of Kőnig's theorem
- Euler Graph
- The Solution to the Bridges of Königsberg Problem
- Fleury's Algorithm Proof
- Hamiltonian Graph
- Proof of Dirac's Theorem in Graph Theory
- Tree Graph
- Label Tree and Cayley's Theorem
- Erdős–Gallai Theorem
- Havel-Hakimi Algorithm Proof
- Graph Coloring and Brooks' Theorem
- Graph Homomorphism
- Planar Graphs and Kuratowski's Theorem
- Proof of Euler's Polyhedron Formula
- Graph k-connectivity and Menger's Theorem
- Geometric Dual Graphs
- Abstract Dual Graphs
- Simple Properties of Planar Graphs
- Definition of Maps in Graph Theory
- Proof of the Five Color Theorem
- Four Color Map Problem
- Erdős–Rényi Graph
- Proof of the Anderson-Livingston Theorem
- Perfect Graph
- Graph Families and Properties
- Random Graphs
- Erdős–Rényi Model
- Gilbert Model
- Distribution of Degrees in Networks
- Scale-Free Network
- Blue-Loo Fitness Model
- Barabási-Albert Model
- Hub Nodes in Network Theory
- Graph (Network) Visualization and Analysis Program Gephi
- Graph (Network) Analysis Package NetworkX in Python
- Julia's Graph Analysis Package Graphs.jl
- Reading and Writing GEXF Files in NetworkX
- Euclidean Graph
- Degree Centrality in Network Theory
- Stress Centrality in Network Theory
- Network Mediation Centrality in Network Theory
- Proximity Centrality in Network Theory
- Eigenvector Centrality in Network Theory
- Definition of Hypergraph
- Mathematical Graph Layouts
- Spectral Distance Between Graphs
- Graph Edit Distance Between Graphs