摘要：给出了停机位分配问题顶点着色模型及其分解算法．通过改良一种时间冲突算法，构建了航班使用停机位的时间冲突集合．以“先到先服务”原则为基础，把停机位分配问题转化为顶点着色问题，并建立了相应模型．利用笔者独创的分解算法，停机位的作业能力可得到改善．算法的计算复杂度为O（n^2）．该算法的特点在于：1）将顶点、颜色划分为若干个不同等级的集合；2）将顶点按照所属集合的等级、度进行分解，得到顶点的分解序列．在用一种颜色ck（1≤k≤K；K是可用颜色数）给顶点着色时，优先给这样一个顶点着色：该顶点能被着ck色，且其分解序列号最大．最后将该算法应用于一个算例，得到了最优解．

关键词：停机位分配 机场 图论 顶点着色 算法 

单位：中南大学交通运输工程学院; 长沙410075; 广州大学商学院; 广州510006