Graph symbol table

$G(V,E)$. $|V|=n$, $|E|=m$. $k:$ #components

properties

  • simple, no self-loop, no dup. edges
  • bi-p.(bipartite), or $G(V_1, V_2)$.
  • con. connectivity.
  • euler. Eulerian, end at start, aka. cycle through each edge once.
  • semi-euler. aka. end not at start, Euler path.
  • planar.
  • orientable, draw direction, s.t. scc, e.g. euler. is orientable

$C$ cycle, $l$ length of path or cycle.

$B$, set of bridges

$K_n$, complete graph with $n$ nodes

$\chi(G)=j$, chromatic number. $j$-colorable, not $j-1$. called $j$-chromatic

tournament, $K_n$ paint direction.

Theorems

bi-p. $\Rightarrow$ $\forall C$, $l(C)$ even.

simple, $k$ $\Rightarrow$ $n-k \leq m \leq {n-k+1 \choose 2}$.

simple, $m > {n-1 \choose 2}$ $\Rightarrow$ con.

$\forall v, \text{deg}(v)\geq 2$ $\Rightarrow$ $\exists C$

con. : euler. $\Leftrightarrow$ $\forall v, \text{deg}(v)$ even.

con. : euler. $\Leftrightarrow$ $E$ can split into disjoint cycles.

con. : semi-euler $\Leftrightarrow$ exactly 2 $\text{deg}(v)$ odd

(Ore's) simple, $n\geq 3$, $\forall (u,v)\notin E$, $\text{deg}(u) + \text{deg}(v) \geq n$ $\Rightarrow$ Hami.

(Dirac's) simple, $n\geq 3$, $\forall v, \text{deg}(v) \geq n/2$ $\Rightarrow$ Hami.

tree $\Leftrightarrow$ $\nexists C$, $m=n-1$ $\Leftrightarrow$ con. $m=n-1$ $\Leftrightarrow$ con. $\forall e, e\in B$ $\Leftrightarrow$ $\forall u\neq v$, $\exists$ exactly one path. $\Leftrightarrow$ $\nexists C$, any new edge $|C|=1$

forest, $k$ $\Rightarrow$ $m=n-k$

$T$ is any spanning forest of $G$ $\Rightarrow$ (i) cut $\forall c\in G$, $c \cap E(T) \neq \emptyset$. (ii) $\forall C$, $C\cap E(\overline{T})\neq \emptyset$

(Cayley's) number of labelled trees $|L_n| = n^{n-2}$

number of spanning trees $|S(K_n)| = n^{n-2}$

$K_{3,3}, K_5$ are non-planar.

(Kuratowski's) planar. $\Leftrightarrow$ no sub$(G)$ homeomorphic to $K_{3,3}$ or $K_5$

planar. $\Leftrightarrow$ no sub$(G)$ contractible to $K_{3,3}$ or $K_5$

(Euler) con. planar. $\Rightarrow$ $n-m+f = 2$

polyhedral $\Rightarrow$ $n-m+f = 2$

planar. $\Rightarrow$ $n-m+f = k + 1$

simple, con. planar. $n\geq 3$ $\Rightarrow$ $m \leq 3n-6$. if $G$ no triangles, $m\leq 2n-4$

simple, planar. $\Rightarrow$ $\exists v$, $\text{deg}(v)\leq 5$.

dual $G^*$, con. planar. $\Rightarrow$ $n^*=f, m^*=m, f^*=n$

con. planar. $\Rightarrow$ $G^{**}$ isomorphic to $G$

planar. $G$: $C(G)$ $\Leftrightarrow$ $c(G^*)$.

$c(G)$ $\Leftrightarrow$ $C(G^*)$.

$G^*$ is abstract(dual) $\Rightarrow$ $G$ is abstract dual of $G^*$

planar. $\Leftrightarrow$ $\exists$ abstract

simple, $\max_v \text{deg}(v) = d$ $\Rightarrow$ $d+1$-colorable

(Brooks') simple, con. $G\neq K$, $\max_v \text{deg}(v) = d\geq 3$ $\Rightarrow$ $d$-colorable

(Appel and Haken) simple, planar. $\Rightarrow$ $4$-colorable

  • cubic map $\chi_e(G) = 3$

map $G$ is $2_f$-colorable $\Leftrightarrow$ euler.

planar. no loop: $G$ $k$-colorable $\Leftrightarrow$ $G^*$ $k_f$-colorable

(Vizing) simple, $\max_v \text{deg}(v) = d$ $\Rightarrow$ $d \leq \chi_e \leq d+1$

$\chi_e(K_n) = n$ odd($\neq 1$), $\chi_e(K_n) = n-1$ even

(Konig's) bi-p. $\max_v \text{deg}(v) = d$ $\Rightarrow$ $\chi_e = d$

$\chi_e (K_{r,s}) = \max(r, s)$

(Hall) $\exists$ complete matching for $V_1$, $G(V_1, V_2)$ $\Leftrightarrow$ for each $k$ girls in $V_1$, collectivly known at least $k$ boys in $V_2$.

  • more formal, $\forall A\subset V_1, |A|\leq |\varphi(A)|$

max-flow $=$ min-cut

directed

con.: (raw) orientable $\Leftrightarrow$ $\forall e, e\in C$

con.: euler. $\Leftrightarrow$ $\text{indeg}(v)=\text{outdeg}(v), \forall v$

scc. $\forall v, \text{indeg}(v)\geq n/2, \text{outdeg}(v)\geq n/2$ $\Rightarrow$ Hami.

non-Hami. tournament $\Rightarrow$ semi-Hami.

scc. tournament $\Rightarrow$ Hami.

Algorithm Insights

dijkstra. pick min-dist, update its neib.

0-1 bfs. neib. only two kinds dist, so use deque instead of heap.

kruskal. iter edge cost $\uparrow$, dsu maitain connectivity.

lca tarjan offline. dfs. before node end, calc query only when another visited. after visit a node, dsu with its father, update father's ancestor.

bridge. note $u \rightarrow v$, low is minimum of its dfs-after, also mini with begin time when reach a on-track vertex. So $u \rightarrow v$ is bridge iff v's low $>$ u's b.t., aka, those dfs-afters cannot reach back.

cut point. like bridge, but $u$ is c.p. iff v's low $\geq $ u, or $u$ is dfs root with $>1$ children.

toplogical sort. if exists, then by dfs end time. sort


In [ ]: