本文選題：笛卡爾乘積圖　切入點：控制數　出處：《浙江師范大學》2015年碩士論文

【摘要】：設圖G=(V,E)是一個沒有孤立點的無向簡單圖.如果V的一個非空子集D滿足V\D中的每個頂點都有一個鄰點在D中,則稱D是圖G的一個控制集.進一步,如果D是圖G的一個控制集并且由D導出的子圖G[D]中有一個完美匹配,則稱D是圖G的一個配對控制集.一個圖G的配對控制數,即圖G的最小的配對控制集的大小,記為γp(G).配對控制數最初是由Haynes和Slater提出的,同時他們證明了對于一般圖,確定其配對控制數是NP-完全的.本文確定了一些特殊圖的配對控制數,主要內容分為四章.第一章介紹了配對控制數的背景以及本論文所涉及的有關定義,并對路和圈的笛卡爾乘積的配對控制數的研究現狀做了一個綜述.第二章根據圈和圈的笛卡爾乘積的結構,利用反證法,確定了n圈和5圈的笛卡爾乘積的笛卡爾乘積的配對控制數.第三章給出n圈和m(m=2,3)路和n路和m(m=3,4,5)圈的配對控制數.第四章對本文進行了總結并給出笛卡爾乘積圖配對控制數的一些可研究問題.
[Abstract]:璁懼浘G=(V,E)鏄竴涓病鏈夊绔嬬偣鐨勬棤鍚戠畝鍗曞浘.濡傛灉V鐨勪竴涓潪絀哄瓙闆咲婊¤凍VD涓殑姣忎釜欏剁偣閮芥湁涓，

本文編號：1673303