二部圖的控制參數(shù)研究.pdf

1、控制是圖論中的重要概念，由于它在計算機科學(xué)，化學(xué)等的廣泛應(yīng)用，對圖的各類控制參數(shù)以及對控制參數(shù)與其它參數(shù)之間關(guān)系的研究已成為圖論研究中一個非常重要的領(lǐng)域．本文主要研究兩種控制數(shù)（控制數(shù)和成對控制數(shù)）與圖的邊數(shù)極值之間的關(guān)系．
　　 本文分為三部分．在第一部分，首先我們介紹了圖論的歷史背景和現(xiàn)實中的應(yīng)用，接著我們給出了圖論的一些基本概念；在第二部分，首先我們給出了有關(guān)控制的一些概念，其次我們給出了有關(guān)控制參數(shù)與邊數(shù)極值的主要結(jié)論．

2、從主要結(jié)論中我們知道，當(dāng)k＞3時，邊數(shù)等于1/4(n-k+2)2的二部圖中必含孤立點，而我們在電路板制作和資源分配等問題中常會遇到連通二部圖和成對控制與邊數(shù)極值的情況，于是對連通二部圖的控制數(shù)與邊數(shù)極值的研究和對二部圖的成對控制數(shù)與邊數(shù)極值的研究都是很有意義的．在第三部分第一節(jié)我們主要研究就是連通二部圖的控制數(shù)與邊數(shù)極值問題，在這一節(jié)中我們給出了當(dāng)連通二部圖的控制數(shù)k(≥4)給定時，邊數(shù)的上界為「1/4(n-k)2+(n-k)」，且這個