张智微，李 鹏

(重庆理工大学 理学院， 重庆 400054)

密尔顿圈(路)问题是图论中最熟知的NPC问题之一，而其最自然的推广就是最长圈(路)问题，即寻找给定图中所包含顶点个数(或边数)最多的简单圈(路)。最长圈(路)问题是图论的一个研究热点之一，围绕它有大量的工作出现，如研究最长圈(路)的结构性质[1，4，5，8-9，14]，研究最长圈的多项式算法[2，7，12-13]，研究最长圈的近似算法[3，6，15]以及其他相关问题[10-11]等。

弦图是不包含长度大于等于4的诱导圈的图，它是图论很重要的基础图类。区间图是这样的图类：它的顶点可以和数轴上的区间一一对应，2个顶点之间有边当且仅当它们对应的区间相交。熟知的是区间图是弦图的一个子类。

图论中一个很重要的猜想是：2连通的弦图的所有最长圈一定经过同1个顶点。围绕这个猜想，图论工作者进行了大量的研究，但始终无法解决这个猜想。与这个猜想紧密相关的另1个猜想是：2连通边赋权简单图(权值为正数)所有最长圈都经过同1个顶点。本文主要研究边赋权简单图(极大团不超过2个的图)的最长圈性质，证明了该猜想在2连通的边赋权简单图是正确的。

1 预备知识

在图论中，图中一条路径指的是一顶点序列：v1,v2,…,vn。序列中任何相邻的2顶点都可以在图中找到对应的边。一条路径的长度是这条路径所包含的边数。圈指的是在图中任选一个顶点，沿着不重复的边，经过不重复的顶点为途径，之后又回到起点的闭合途径。重边指的是具有一对顶点的多条边。……