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

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

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

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