本文選題：笛卡爾乘積圖　切入點(diǎn)：控制數(shù)　出處：《浙江師范大學(xué)》2015年碩士論文

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

本文編號(hào)：1673303