Combinatorics Graph theory: basic notions Concept
Graph
Summary
A graph is a set of vertices together with a set of edges, each edge joining two distinct vertices. Graphs model networks, relations and maps, and they are the main object of graph theory. The node graph gives the precise definition.
Where this leads
45 pages build on this one.
- Graph of groups
- Tutte polynomial
- Structural rigidity
- Cuthill–McKee algorithm
- Amalgamation property
- Steinitz's theorem
- Crossing number inequality
- Lovász local lemma
- Minimum degree algorithm
- Markov random field
- Percolation theory
- Effective resistance
- Graph enumeration
- Liouville property of graphs
- Nested dissection
- Right-angled Artin group
- Gaussian free field
- Detailed balance
- Generalized polygon
- Extremal graph theory
- Unit distance problem
- Szemerédi regularity lemma
- Cycle double cover conjecture
- Digital topology
- Erdős–Rényi model
- Graphical model
- Discrete harmonic function
- Hammersley–Clifford theorem
- Sidorenko's conjecture
- Zarankiewicz problem
- Train track
- Electrical network
- Erdős–Hajnal conjecture
- Rado graph
- Loop-erased random walk
- Comparability graph
- Geometric graph
- Penny graph
- Triangle removal lemma
- Erdős–Stone theorem
- Percolation threshold
- Balinski's theorem
- Discrete Dirichlet problem
- Hadwiger–Nelson problem
- Graceful tree conjecture
Further reading
About this page
| Tag | 00C0BR7D7H |
|---|---|
| URI | m2://00C0BR7D7H |
| Kind | concept |
| Writing | W1 stated |
| MSC | 05C99 |
| Same as |
Markdown · JSON · Edit on GitHub
What this page needs for W2
- edge not_instance_of in: at least one non-example (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
Instances
Special cases
- Forest
- Hamiltonian graph
- Connected graph
- Complement graph
- Planar graph
- Regular graph
- Acyclic graph
- Subgraph
- K-colourable graph
- Laman graph
Definitions
Used by
- Graph of groups
- Tutte polynomial
- Structural rigidity
- Cuthill–McKee algorithm
- Amalgamation property
- Steinitz's theorem
- Crossing number inequality
- Lovász local lemma
- Minimum degree algorithm
- Markov random field
- Percolation theory
- Graph enumeration
- Liouville property of graphs
- Nested dissection
- Right-angled Artin group
- Gaussian free field
- Detailed balance
- Generalized polygon
- Extremal graph theory
- Szemerédi regularity lemma
- Cycle double cover conjecture
- Digital topology
- Erdős–Rényi model
- Graphical model
- Discrete harmonic function
- Hammersley–Clifford theorem
- Sidorenko's conjecture
- Train track
- Electrical network
- Erdős–Hajnal conjecture
- Rado graph
- Loop-erased random walk
- Comparability graph
- Geometric graph
- Penny graph
- Triangle removal lemma
- Erdős–Stone theorem
- Percolation threshold
- Balinski's theorem
- Discrete Dirichlet problem
- Hadwiger–Nelson problem
- Graceful tree conjecture