I am forced to study this goddamn course as a requirement, and I hate the outdated overly verbose nonsense textbook, but I need to do it. I need to pass this damn course.
I have literally been joyless these days-- very depressed. Anyways, I hate school, I hate everything.
Note: Graph defaults to undirected, simple graph
Chapter 1
- 简单图: no loops, no more than one edge between any two vertices.
- 完全图: a graph in which each vertex is connected to every other vertex.
- 生成子图: subgraph that includes all the vertices of the original graph
- 导出子图: induced subgraph (subgraph but you can't erase edges)
- 行迹: a path with no redundant edge
- 轨道: a path with no redundant vertex
- 回路: a path with the same starting and ending point
- 圈: cycle
- 有向图: directed graph
- Dijkstra: loop: find min dist unvisited and update dist for unvisited, O(|E|+|V|log|V|)
- Bellman-Ford: (negative weight) loop: relax all edges (at most |V|-1 times), O(|V||E|)
Chapter 2
- 树: connected, acyclic graph
- 树叶: nodes where degree is 1
- 分支点: nodes where degree is greater than 1
- 森林: acyclic graph
- 生成树: spanning tree
- Kruskal: sort the edge, loop: add smallest edge in the graph(if acyclic), O(|E|log|V|)
- Prim: basically Dijkstra (you can aggregate all paths after Dijkstra, very trivial), O(|E|+|V|log |V|)
- Huffman 树: combing smallest node each time
Chapter 3
- 割集:a partition of the vertices of a graph into two disjoint subsets
- Menger Theorem
- Whitney Theorem
- k 扇形: k disjoint path from X to Y
- k-connected-graph: has more than k vertices and remains connected whenever fewer than k vertices are removed
- Dirac Theorem
Chapter 4
- 平面图: Planar graph, a graph that can be embedded in the plane(<=> on a sphere) without any edges crossing
- 桥: an edge if deleted, connected components increases
- Thm(generalized Euler): V-E+F-C= 1, f: area, c: component, prove: induction (trivial)
- Thm: sum(deg(F))= 2 * |E(G)| (trivial)
- Corollary: In planar graph E <= 3V-6 (trivial)
- Corollary: In planar graph min(degree(V))<= 5 (trivial)
- K5: 5 vertices complete graph (WHY SO CONFUSING??????)
- K3,3: complete bipartite graph with set of 3 vertices each (WHY SO CONFUSING??????)
- 极大平面图: planar but adding any edge would not be planar
- Thm: If V>3, then maximum planar graph <=> all faces are triangles (trivial) <=> E = 3V-6
- 同胚: both can be obtained from the same graph by subdivisions of edges
Chapter 5
- 匹配: set of edges, no two sharing a vertex
- 完备匹配: all nodes are included
- 最大匹配: match with most edges
- 交错轨道: a path that alternates between edges in and not in the matching
- 可增广轨道: a path that starts and ends on free vertices, and alternates between edges in and not in the matching
- Berge: a matching M is maximum iff there is no augmenting path with M.
- Hall: there is an X perfect matching iff for every subset W of X, |W| <= |NG(W)|
- 覆盖: a set of vertices that includes at least one endpoint of every edge of the graph.
- Kőnig
- Tutte
- Hungarian Algorithm
Chapter 6
- Euler 迹: a path traversing every edge <=> at most 2 vertex degree is odd
- Euler 回路: a closed path travering very edge <=> no vertex degree is odd
- Euler 图: a graph with a Eulerian cycle
- Hamilton 轨道: a path traversing every vertex in the graph
- Hamilton 圈: a cycle traversing every vertex in the graph
- Hamilton 图: a graph with Hamilton cycle
- Bondy–Chvátal theorem Theorem
Chapter 7
- Thm: Bipartite graph with edges <=> Х(G)=2 (trivial)
- k 边着色: color edges with k different colors
- 正常 k 边着色: color edges with k different colors with different colors on adjacent edges
- Lemma: If G isn't an odd cycle, then exist a 2-coloring of edges, st every degree(vertex)>=2, 2 colors appear in the edges connected
- 改进:edge coloring using fewer colors
- 最佳边着色:edge coloring using fewest colors
- Δ: max(degree(vertex))
- Vizing: Graph minimum edge coloring is max(degree(vertex)) colors or max(degree(vertex))+1 colors, Proof: https://en.wikipedia.org/wiki/Vizing's_theoremt
- Planar graph five coloring: Induction -> '(if can't) one vertex degree=5 with different cyclic neighbors colors 1,2,3,4,5 -> 2 color subgraph G(1,3) (G(2,4)) with node 1,3 (node 2,4) on one path -> planarity contradiction
- Planar graph four coloring: computer needed
- 颜色多项式: Chromatic polynomial P(G, k) counts the number of its vertex at most k-colorings
- Thm: P(G, K) = P(G-e, K)- P (G combine u,v, k) for every simple graph G and edge e=(u,v) (trivial)
Chapter 8
- 底图: the undirected graph for directed graph
- 外邻定点: u->v, v is the external point
- 内邻集: all internal points
- 外邻集: all external points
- 强连通: u can go to v AND v can go to u
- 单项连通: either u can go to v or v can go to u (or both)
- 弱连通: the undirected path can reach each other
- 竞赛图: directed, complete graph
- Thm: Every k-chromatic graph has a k-chromatic subgraph of min degree at least k−1 (trivial)
- Thm: Every directed, complete graph is hamiltonian (trivial)
- Thm: Length of longest path in a directed graph is greater than smallest degrees inbound (and outbound) in all vertex (trivial)
- Thm: In a directed graph if minimal inbound and outbound of every vertex in a raph is greater or equal than vertex/2, it is hamiltonian (trivial)