一些圖的笛卡爾乘積的全控制數(shù)和成對(duì)控制數(shù).pdf

1、圖論是應(yīng)用數(shù)學(xué)的一個(gè)分支，它以圖為研究對(duì)象，圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系.
　　圖論是歐拉在1763年解決柯尼斯堡七橋問(wèn)題的過(guò)程中創(chuàng)立的，而在在過(guò)去的的三十年里，圖的“控制”的研究是圖論中發(fā)展最快的領(lǐng)域.這一研究領(lǐng)域出現(xiàn)之所以這么迅速，主要因素有以下三點(diǎn):（一）它在現(xiàn)實(shí)世界和諸如“覆蓋”“位置確定”類(lèi)

2、數(shù)學(xué)問(wèn)題中有著廣泛而深刻的應(yīng)用.例如目前編碼理論中正在研究的碼長(zhǎng)為n覆蓋半徑為r的二進(jìn)制碼的最小數(shù)K(n，r)正是圖的控制集理論中超立方圖的r-距離控制數(shù)，顯然，圖論中的距離控制數(shù)更具有一般意義.現(xiàn)在，人們已發(fā)現(xiàn)圖的控制集理論可廣泛應(yīng)用于編碼理論，計(jì)算機(jī)科學(xué)，通信網(wǎng)絡(luò)，監(jiān)視系統(tǒng)和社會(huì)網(wǎng)絡(luò)等理論與實(shí)踐中.（二）控制參數(shù)定義類(lèi)型的多樣性.根據(jù)實(shí)際背景的不同，現(xiàn)已定義的控制參數(shù)有幾十種之多，隨著研究的深入和應(yīng)用的激發(fā)，新的參數(shù)如雨后春筍，不斷

3、涌現(xiàn).（三）圖的控制參數(shù)確定問(wèn)題的NP-完全性與其它組合優(yōu)化中NP-完全問(wèn)題緊密而自然的關(guān)系.
　　確定一般圖的控制參數(shù)（控制數(shù)，全控制數(shù)和成對(duì)控制數(shù)）的問(wèn)題一般都是NP困難的(NP-hard).因此，確定一些較特殊圖的控制參數(shù)也具有較為重要的意義.
　　本文首先介紹了圖，笛卡爾乘積，全控制，控制數(shù)，成對(duì)控制及成對(duì)控制數(shù)的基本概念，還有圖的一些表示符號(hào)以及有關(guān)全控制數(shù)，成對(duì)控制的結(jié)論，并借鑒了圖與圖的笛卡爾乘積，圖的控制和全