九至十二年级Discrete Mathematics课程已上线
Graphs
Graphs as vertices and edges, degree and the handshake lemma, paths and connectivity, Euler circuits, trees and graph isomorphism.
math.discrete.graph-basics
前置知识
11 项必需的前置知识（一直追溯到底）
你将学会
- Prove the handshake lemma and Euler's criterion for Eulerian circuits.
- Prove that a tree with n vertices has n − 1 edges.
- Decide whether two small graphs are isomorphic.
定义
- A simple graph consists of a set V of vertices and a set E of two-element subsets of V, called edges.
- A tree is a connected graph with no cycles.
- Graphs G and H are isomorphic if there is a bijection between their vertex sets that preserves adjacency in both directions.
定理
- Handshake lemma: the sum of the degrees of all vertices is 2|E|.
- A connected graph has an Eulerian circuit if and only if every vertex has even degree.
- A tree on n vertices has exactly n − 1 edges, and any two of its vertices are joined by a unique path.
常见误解
- Thinking a particular drawing determines the graph; very different drawings can show the same graph.
- Confusing Euler circuits (using each edge once) with Hamiltonian cycles (visiting each vertex once).
通向
可选发现
- Structure-preserving maps: homomorphisms and isomorphisms A graph isomorphism is a structure-preserving bijection whose inverse also preserves structure.
- Quivers and path algebras Directed graphs (quivers) give rise to path algebras, whose modules are the representations of the quiver.
学习路径
延伸阅读
- J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (1976)