图作为一种常用的数据结构,可以灵活且直观地描述世界上的各种实体以及实体之间繁杂多样的关系,因此被广泛地应用于多个行业和学科领域。譬如,在生物学领域,可以用蛋白质相互作用网络模拟一个生物系统中各种蛋白质之间的相互作用;在金融学领域,可以用市场图来描述股票市场的结构特性;在传播学领域,可以用社交网络图表示个体之间的亲属、朋友、同事等关系。在图结构中寻找高密度区域,即密集子图的挖掘问题,是一个理论和实践上都很重要的问题。例如,在蛋白质互作网络中寻找重要蛋白,在引文网络中发现有影响力的研究者,在社交网络中检测垃圾邮件等实际问题,都可以通过密集子图的挖掘得到实现。然而,在对密集子图查询问题的研究中,以往的研究中很少考虑到顶点和边的权值。随着研究的发展,研究者们开始考虑群组之间的关系密集程度等方面的研究。因此,需要研究顶点和边都加权图的最密集子图问题。以前的求解顶点和边都加权图的最密集子图问题的算法,局限于权值为自然数的情况。对于更一般的情况,如果权值为实数,该如何设计算法进行求解?这是一个公开问题。本文设计了基于线性规划的算法解决了该问题。本文梳理了最密集子图查询问题的研究背景和研究现状,在此基础上,对加权无向图的最密集子图问题及其变体问题进行探究,并提出了两个算法。第一,以顶点和边都加权的无向图为研究对象,针对寻找其最密集子图的问题,提出了一种基于线性规划的算法,并给出了算法的证明。该算法可以处理顶点和边的权值为实数的情况。第二,以顶点和边都加权的无向图为研究对象,针对寻找其包含指定k个顶点的最密集子图问题,提出了一种基于线性规划的算法,并证明了算法的正确性。该算法同样可以处理顶点和边权值为实数的情况。