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

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

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