论文部分内容阅读
控制是图论中的重要概念，由于它在计算机科学，化学等的广泛应用，对图的各类控制参数以及对控制参数与其它参数之间关系的研究已成为图论研究中一个非常重要的领域．本文主要研究两种控制数（控制数和成对控制数）与图的边数极值之间的关系．
本文分为三部分．在第一部分，首先我们介绍了图论的历史背景和现实中的应用，接着我们给出了图论的一些基本概念；在第二部分，首先我们给出了有关控制的一些概念，其次我们给出了有关控制参数与边数极值的主要结论．从主要结论中我们知道，当k＞3时，边数等于1/4(n-k+2)2的二部图中必含孤立点，而我们在电路板制作和资源分配等问题中常会遇到连通二部图和成对控制与边数极值的情况，于是对连通二部图的控制数与边数极值的研究和对二部图的成对控制数与边数极值的研究都是很有意义的．在第三部分第一节我们主要研究就是连通二部图的控制数与边数极值问题，在这一节中我们给出了当连通二部图的控制数k(≥4)给定时，边数的上界为「1/4(n-k)2+(n-k)」，且这个界是紧的；在第二节我们主要研究成对控制数和边数极值问题，在这一节中，我们给出了当二部图的成对控制数k(＞2)给定时，边数的上界为1/4((n-k/2)2+2(n-k/2))，且这个界是紧的.