论文部分内容阅读
竞争图的概念是由著名生物学家Cohen在1968年研宄生态学问题时提出的.设 D=(V,A)为一个有向图,其中 V是点集,A是有向边集. D的竞争图C(D)为无向简单图,其点集与D的点集相同,对uG V,vG V,uv为C(D)的一条边的充要条件:存在点w∈ V,使得(u,w)∈ A且(u,w)∈ A.对于任意一个无向图G, G并上足够多的孤立点是某个无圈有向图的竞争图. Roberts在1978年发现,这样加进来的孤立点的最小个数称为图的竞争数,记作k(G).正如 Opsut指出,计算一个图的竞争数是一个NP-困难问题.图的竞争数与图的边团覆盖数密切相关.本文将通过讨论图的边团覆盖数来研宄几类球面三角剖分的竞争数,得到了一个二十四面体,一类十二面体和一个顶点数为3n的球面三角剖分的竞争数.在这里,二十四面体是通过在六面体的6个面内各加一个点并把每一个所加的点与它所在面的四个顶点连接而形成的,十二面体是通过在六面体的6个面内各连一条对角线而形成的.