ConceptMathematics
Graph
A mathematical structure consisting of a set of nodes (vertices) and a set of edges representing relationships between them.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
7Each in their own terms, from the easiest level.
Gilbert Strang
A mathematical structure consisting of a set of nodes and a set of edges that connect pairs of nodes.Herbert Gross
A picture of a relationship obtained by plotting the input along a horizontal line and the output at right angles to it.Tom Leighton
A bunch of dots and lines connecting the dots, formally defined as a pair of sets (V, E) where V is a nonempty set of vertices or nodes.Erik Demaine
A mathematical structure consisting of a set of vertices and a set of edges connecting them.Colva Roney-Dougal
A visual representation of a problem consisting of vertices representing people and edges representing acceptable seating pairings.Julian Shun
A graph contains vertices and edges, where vertices model objects of interest and edges model relationships between them.
Lectures that assume it
68The first 12 are shown.
- Course Overview, Interval Scheduling
- Matching Problems
- Rounding LP Solutions: Minimum Vertex Cover
- Harvard CS50’s Artificial Intelligence with Python – Full University Course
- Geometric Structures I
- Big Data: Spark
- Dijkstra's Shortest Path Algorithm: Graph Theory and Optimization
- Goemans-Williamson Algorithm: Rounding the Max-Cut SDP
- Hardness within P
- Bentley Rules for Optimizing Work
- Depth-First Search (DFS), Topological Sort
- The Immerman-Szelepcsényi Theorem
Connections
83The lectures that define it or assume it, and the concepts next to it.
Concepts7
Show 1 moreShow fewer
Lectures76
- Preface: MIT Calculus Revisited - Single Variable Calculus
- Graph Theory and Coloring
- Breadth-First Search (BFS)
- Graphs, Networks, Incidence Matrices
- Graph Optimization
- Matrix Spaces; Rank 1; Small World Graphs
Show 70 moreShow fewer
- How Hard is too Hard? An Introduction to Complexity
- Pigeonhole Principle
- Course Overview, Interval Scheduling
- Matching Problems
- Rounding LP Solutions: Minimum Vertex Cover
- Harvard CS50’s Artificial Intelligence with Python – Full University Course
- Geometric Structures I
- Big Data: Spark
- Dijkstra's Shortest Path Algorithm: Graph Theory and Optimization
- Goemans-Williamson Algorithm: Rounding the Max-Cut SDP
- Hardness within P
- Bentley Rules for Optimizing Work
- Depth-First Search (DFS), Topological Sort
- The Immerman-Szelepcsényi Theorem
- P and NP, SAT, Poly-Time Reducibility
- Linear-size ℓ₁ Sparsifiers
- On-Chip Interconnect Topologies, Buffering & Flow Control
- Course Overview and Formal Definition of Computation
- Graph Theory II: Minimum Spanning Trees
- Dijkstra's Algorithm: Greedy Single-Source Shortest Paths
- Incremental Improvement: Matching
- Arch4Health: 4th Workshop on Architecture for Health
- The Complexity Class NP
- Reductions
- NP-Completeness Reductions
- Architectures: Graphs
- Completing a Rank-One Matrix and Circulants
- Interactive Proofs: IP=PSPACE
- Constraint Satisfaction Problems (CSPs) Part 1/2
- On the Measure of Intelligence: Program Synthesis and Fluid Abstraction
- Hard Lefschetz Theorem and Hodge-Riemann Relations for Combinatorial Geometries
- Dynamic Programming: All-Pairs Shortest Paths
- Dynamic Graphs II
- Extremal Combinatorics Meets Algorithms and Data Structures
- Toda's 1st Theorem and the Permanent
- How to Train a Neural Net
- Nodal surplus and the spectral decomposition of the cycle space
- Force Laws, Lewis Structures and Resonance
- Bellman-Ford
- Greedy Algorithms: Minimum Spanning Tree
- Graph Theory III
- Hierarchy Theorems
- Savitch's Theorem and NL
- Inner Simplicity vs. Outer Simplicity
- Chopping Binary Executables: Object File Recovery and Modular Decomposition
- Shortest Paths
- Convex Optimization II: Model Predictive Control
- Approximation Algorithms: Traveling Salesman Problem
- k-wise Independent Generators
- Treewidth Definitions
- Digital vs. Biological Intelligence (Vienna Gödel Lecture)
- L and NL, NL = coNL
- Problems in P
- Building the Blueprint of Life: Genome Assembly
- A Living Planet
- Synchronous Distributed Algorithms: Symmetry-Breaking and Shortest-Paths Spanning Trees
- Spectral Graph Theory Beyond the Standard Graph Laplacian
- Recovering Riemannian Metric Distance from Random Geometric Graphs
- Nodal Geometry and Perturbations of the Laplace-Beltrami Operator
- Depth-First Search (DFS) (MIT 6.006, Recitation 14)
- Dynamic Programming: Crazy Eights and Shortest Path (MIT 6.006, Recitation 19)
- Trees and Series-Parallel Graphs
- Double Minima, Earnshaw's Theorem and Plum-Puddings
- Join Ordering: Top-Down / Transformational
- Sampling-based (kinodynamic) motion planning
- A Physicist's Adventures in Virology: Physics for Public Health
- Hash All The Things / Get All The Sig(s): Automatic Function Detection for Reverse Engineers
- Quantum Computing Overview
- The Life and Times of Edsger Dijkstra
- Mathematics and Metamathematics of Our Physics Project