区间图

区间图（interval graph）是实直线上有限一族区间的交图：每个区间对应一个顶点，两个不同顶点相邻，当且仅当相应区间有公共点。它把“时间上是否冲突”这样的连续关系，转换为一个有限图中的边关系。下文采用非空闭区间，图为无向简单图；因此只接触于一个端点也算相交。

例如，五项教学用任务占用的时间分别为 $I_a=[0,3]$、$I_b=[1,2]$、$I_c=[2,4]$、$I_d=[3.5,5]$、$I_e=[5,6]$。任务 $a,b,c$ 在时刻二同时占用资源；$d,e$ 在时刻五也冲突。若同一资源不能同时服务相交任务，把任务作为顶点、冲突作为边，资源分配就成为给相邻顶点分配不同颜色的问题。

区间表示与边集合

设顶点集合为 $V$，为每个 $v\in V$ 指定区间 $I_v=[{\ell }_v,r_v]$，其中 ${\ell }_v\le r_v$。所得图 $G=(V,E)$ 的边由下式完全确定： $$\{u,v\}\in E⟺u\ne v\text{且}max({\ell }_u,{\ell }_v)\le min(r_u,r_v).$$ 这里左端的最大值是两个区间较晚的起点，右端的最小值是较早的终点；前者不超过后者，正表示两区间之间仍留有共同部分。这组区间称为图的一个区间表示。同一图可以有许多不同表示，区间长度和端点数值并不是图本身附带的数据。

实心端点表示闭区间。竖虚线穿过三个区间，给出同时冲突数为三的具体证据。

逐对检查上述五区间，得到 $$E=\{ab,ac,bc,cd,de\}.$$ 这里 $ab$ 简记无向边 $\{a,b\}$。例如，$b,c$ 的交集只有 $\{2\}$，仍须保留边 $bc$；而 $a,d$ 满足 $3<3.5$，没有边。读下图时，线段只是表示邻接，线段在纸面上交叉并不增加顶点。

同一组区间的交图。区间的横坐标被舍去，只留下五条冲突关系。

两两相交与公共时刻

对一般集合族，“任意两集合相交”不保证所有集合有公共元素；有限闭区间族却具有这一性质。设一组区间两两相交，令 $$L=\underset{v}{max}{\ell }_v,R=\underset{v}{min}{r}_v.$$ 有限性保证存在区间 $I_p$ 取得最大的左端点 $L$，存在区间 $I_q$ 取得最小的右端点 $R$。若 $p=q$，区间非空直接给出 $L\le R$；若不同，它们相交也给出 ${\ell }_p\le r_q$，即 $L\le R$。对每个 $v$，又有 ${\ell }_v\le L\le R\le r_v$，故点 $L$ 属于所有区间。这完成了证明。

图中两两相邻的顶点集合称为团，团的最大顶点数记为 $\omega (G)$。上述证明说明：区间图中的每个团都对应一个共同时间点。因此 $$\omega (G)=\underset{t\in ℝ}{max}\mathrm{\#}\{v:t\in I_v\}.$$ 右端是同一时刻覆盖它的区间数的最大值。例中 $a,b,c$ 在二处共同出现，所以 $\omega (G)\ge 3$；逐个端点区段检查，没有四区间共同出现，因此恰为三。这个结论把“每一对冲突”加强成“所有任务确实有一个同时冲突的时刻”。

最少资源数与着色

一个正常顶点着色给每个顶点一种颜色，并使每条边的两端不同色。最少颜色数记为 $\chi (G)$。同一团内所有顶点都需不同颜色，故任意图都有 $\chi (G)\ge \omega (G)$。对于区间图可以证明等号。

证明。 按左端点非递减次序处理区间；左端点相同者用任意固定次序。处理区间 $I=[\ell ,r]$ 时，给它一个尚未被已处理邻居使用的颜色。若某个已处理区间 $J$ 与 $I$ 相交，排序保证 ${\ell }_J\le \ell$，相交保证 $r_J\ge \ell$，所以 $J$ 包含点 $\ell$。因此全部已处理邻居以及 $I$ 共同包含 $\ell$，组成一个团。邻居数量至多 $\omega (G)-1$，使用的颜色数量也至多如此；在 $\omega (G)$ 种颜色中一定有空闲颜色。逐个处理就得到至多 $\omega (G)$ 色的正常着色，结合下界得到 $$\chi (G)=\omega (G).$$ 证明真正使用的是按区间起点的顺序，而非任意给顶点排队。这里讨论区间表示已知时的结构；只给一个抽象图时，首先还须判断它是否有区间表示。

对主例可依次分配 $a:1,b:2,c:3,d:1,e:2$。所有五条边两端异色，三种资源足够；又因 $a,b,c$ 同时冲突，两种资源不够。这同时给出了可行分配和最优性证据。

变式。 将 $I_b$ 缩为 $[1,1.5]$，其余不动。此时边 $bc$ 消失，保留 $ab,ac,cd,de$；没有三个区间共同相交。可分配 $a:1,b:2,c:2,d:1,e:2$，故资源数从三降到二。改变一个端点不仅改变某个区间的长度，也可能改变图的组合结构。

端点约定与不能表示的图

在排班中，任务于时刻二结束，另一项于二开始，可能允许共用资源。此时应采用半开区间 $[\ell ,r)$ 并要求 $\ell <r$；相交条件改为严格不等式 $max({\ell }_u,{\ell }_v)<min(r_u,r_v)$。主例的 $bc,de$ 都会消失。问题条件决定端点约定，不能在同一模型中随意混用。

也不是每个图都能用区间表示。一个四顶点无弦环 $C_4$ 就不行。假设它有闭区间表示，取右端点最小的顶点 $v$，记该右端点为 $r_v$。与它相邻的两个区间各自左端点不超过 $r_v$；由于 $r_v$ 最小，它们的右端点也不小于 $r_v$。两者于是都包含 $r_v$，必相交，构成一条弦；这与无弦四环矛盾。这个反例也说明：仅有 $\chi =\omega$ 不足以识别区间图，因为 $C_4$ 的这两个数都是二。