0%

网络的基本概念

  • 网络:弧带权的有向图
    • 弧的权又称弧的容量,记作$c(a)\geq 0$
    • 只讨论简单的有向图(无环弧、无并行弧)
    • 有一个特殊的源点,记作$s$
    • 有一个特殊的汇点,记作$t$
  • 流:
    • $f$:定义在弧上的非负实值函数
    • $f^+(v)$:顶点$v$的所有出弧的流量和
    • $f^-(v)$:顶点$v$的所有入弧的流量和
  • 可行流:
    • 容量约束:$\forall a\in A(G),0\leq f(a)\leq c(a)$
    • 守恒约束:$\forall v\in V(G)\setminus \{s,t\},f^+(v)=f^-(v)$
  • 对于任意网络,可行流总是存在的,比如:零值流
  • 流量:
    • $f^-(t)-f^+(t)$
  • 必有$f^-(t)-f^+(t)=f^+(s)-f^-(s)$
  • 最大流:流量最大的可行流
  • f增广路
    • 底图中的一条s-t路
    • 经过的每条正向弧$a\in A(G):f(a)<c(a)$
    • 经过的每条反向弧$a\in A(G):f(a)>0$
  • 增广路的“可增量”

有序对

  • 无序对:
    • 含有1个或2个元素的集合
    • $(v_1,v_2)=\{v_1,v_2\}$,$(v_2,v_2)={v_2}$
  • 有序对:$\langle a_1,b_1\rangle=\langle a_2,b_2\rangle$ 当且仅当 $a_1=a_2$ 且 $b_1=b_2$
  • 有序对的集合表示:$\langle a,b\rangle=\{\{a\},\{a,b\}\}$

有向图和弧

  • $G=\langle V,A \rangle$
    • $V$:顶点集
    • $A$:弧集,一个有向对的集合。弧又称为有向边
  • 一些术语
    • 弧的尾
    • 弧的头
    • 环弧:头尾相同的弧
    • 并行弧:具有相同头的相同尾的弧
    • 简单有向图:无环弧,无并行弧
    • 反向弧:简单有向图中头尾相反的弧

度和邻点

阅读全文 »

边染色

相关概念

  • 边$k$染色
    • $E(G)\rightarrow \{1,2,\cdots,k\}$
    • $E_i$:色为$i$的边集
  • 边正常$k$染色:相邻的边不同色
  • 边$k$色可染的: 能找到一个边正常$k$染色
  • 边色数:
    • 边$k$色可染的最小$k$
    • 记作$\chi’$
  • 只考虑无环图,可以有重边

边色数的性质和意义

  • $\Delta\leq \chi’ \leq \epsilon$
  • $\chi’$和匹配的联系:
    • $E(G)$至少要被划分成$\chi’(G)$个匹配
    • 如果$E(G)$能被划分为$m$个匹配,则$\chi’(G)\leq m$
阅读全文 »