網(wǎng)絡(luò)清理中若干問題的研究.pdf

1、本文將介紹一個(gè)用刷子逐點(diǎn)清理一個(gè)網(wǎng)絡(luò)的問題，我們將其轉(zhuǎn)化為清理圖的問題。首先清理一個(gè)頂點(diǎn)是指把該頂點(diǎn)清掃的同時(shí)將其所有被污染的鄰邊都恰好用一個(gè)刷子清理，且已經(jīng)被清理的邊不能讓刷子再次清理。清理完此頂點(diǎn)后，這些刷子都通過它們所清理的邊到達(dá)這個(gè)點(diǎn)相應(yīng)的鄰點(diǎn)處。而我們通過逐步清理圖中的頂點(diǎn)來達(dá)到清理整個(gè)圖的目的。現(xiàn)實(shí)中，人們?cè)谇謇硪粋€(gè)網(wǎng)絡(luò)時(shí)常常遇到的問題就是被清理過的地方過一段時(shí)間后會(huì)變的不整潔，本文研究這個(gè)問題中，考慮到現(xiàn)實(shí)情況，因此我們要

2、求清理能夠無限的進(jìn)行下去。
　　 以上為本文所依據(jù)的規(guī)則背景，接下來本文共分三個(gè)章節(jié)。第一章是本文綜述，給出圖論的基本概念和清理的定義，而后綜述相關(guān)的研究成果;第二章來解決無限清理的問題并給出清理一個(gè)一般無向簡(jiǎn)單圖所需最少刷子數(shù)的下界d/2，其中d為該圖奇度點(diǎn)的個(gè)數(shù)，以及關(guān)于圖的卡氏積下所需刷子數(shù)的上限問題;第三章為本文的重點(diǎn)章節(jié)，根據(jù)前面結(jié)論，解決卡氏積下清理Pm×Pn，Cm×Pn，Cm×Cn所需的最少刷子數(shù)，分別為m+n-2