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

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

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