关于弦图的团序列

设G=(V,E)是一个有限无向简单图,C_k是G中具有k个点的完备子图的数目。序列(C_1,C_2,…)称为图G的团序列。本文给出了整数序列是弦图的团序列的充分必要条件、两个弦图有相同的团序列的充分必要条件和弦图k连通的充分必要条件。     

箭线图的系统设计

箭线图的绘制是对大规模工程进行网络控制的基础。绘制箭线图一般都要用到引入虚工序,以帮助建立实工序的先后关系。由于虚工序的引入,使箭线图变得复杂,使得计算网络有关参数和对工程施实控制变得困难。在绘制箭线图时,怎样较少地引入虚工序,又能正确地表示工序的顺序关系呢?黄沛钧、程国平和李随成提出了简便有效的途径和方法。他们的方法改进了[3]中的方法。本文对箭     

关于图的领域复盖

图G＝（V，E）中一个点V的领域是点V及其邻点导出的G的子图。领域复盖问题就是求一级量小个的领域，使其复盖子G的每一条边。本文证明了无三角形图上和分离图上的领域复盖问题是NP－完全问题。通过研究集族的强Helly性质，得到了领域复盖问题可转化为团复盖问题的条件一图的领域二分具有强Helly性质。文中给出了弦图的领域二分图具有强Helly性质的禁用子图形式的充分必要条件。     

弦图上团划分数问题的复杂性

本文得到下述结果:(1)在无K_4图上或在弦图上,求团划分数问题是NP——困难的;(2)找到在无K_4弦图上求团划分数的线性算法和在弦图上求团覆盖数的线性算法。