4元n方體完善匹配的若干性質(zhì).pdf

1、具有許多優(yōu)良特性的k元n方體是應(yīng)用非常廣泛的互連網(wǎng)絡(luò)之一.k元n方體Qkn（k≥2，n≥1）的頂點(diǎn)集V(Qkn)={u0u1…un-1:0≤ui≤k-1，0≤i≤n-1}，兩個(gè)不同的頂點(diǎn)u=u0u1…un-1和v=v0v1…vn-1相鄰當(dāng)且僅當(dāng)存在一個(gè)整數(shù)j∈{0，1，…，n-1}，滿足uj=vj±1(mod k)且ui=vi，i∈{0，1，…，n-1}\{j}.此時(shí)稱(u，v)為一條j維邊.若刪去Q4n的所有j維邊，其中，j∈{0，1

2、，2，…，n-1}，得到四個(gè)4元n-1立方體，分別設(shè)為Q[0]、Q[1]、Q[2]和Q[3].
　　設(shè)M是E的一個(gè)子集，它的元素是G中的邊，并且這些邊中的任意兩個(gè)在G中均不相鄰，則稱M為G的匹配.若匹配M的某條邊與頂點(diǎn)v關(guān)聯(lián)，則稱M飽和頂點(diǎn)v，并且稱v是M飽和的，否則稱v是M非飽和的.若G的每個(gè)頂點(diǎn)均為M飽和的，則稱M為G的完美匹配.
　　圖G的匹配圖記為M(G)，它的頂點(diǎn)集是G的所有完美匹配的集合，兩個(gè)頂點(diǎn)相鄰當(dāng)且僅當(dāng)兩個(gè)

3、頂點(diǎn)對(duì)應(yīng)的完美匹配的并構(gòu)成G的一個(gè)Hamilton圈.因此，M(G)的頂點(diǎn)與G的完美匹配是一一對(duì)應(yīng)的.
　　在網(wǎng)絡(luò)暴露攻擊中會(huì)用到完美匹配，當(dāng)通過(guò)一個(gè)混合閾值追蹤一個(gè)信息時(shí)，完美匹配暴露攻擊會(huì)起很大的作用.在一些網(wǎng)絡(luò)連通問(wèn)題中，匹配排除也起著關(guān)鍵作用.在本文中，我們主要研究4元n方體的完美匹配的一些問(wèn)題.本文共分三章:
　　第一章中，介紹一些本文將會(huì)用到的有關(guān)圖論的基本概念.
　　第二章中，研究4元n方體的一個(gè)匹配擴(kuò)展

4、成完美匹配的問(wèn)題.主要結(jié)果如下:
　　(1)設(shè)M是Q4n的任意一個(gè)匹配，且M中所含邊的數(shù)目不多于2n-1，則M可擴(kuò)成Q4n的一個(gè)完美匹配，且該結(jié)論是最優(yōu)的.
　　(2)設(shè)M是Q4n的任意一個(gè)匹配，M中所含邊的數(shù)目不多于2n-2，則存在d∈{0，1，…，n-1}，使得M中至多有一條d維邊.刪去Q4n中所有d維邊得到4個(gè)4元n-1方體，記為Q[0]，Q[1]，Q[2],Q[3].若x，y是某個(gè)Q[i]中兩個(gè)未被飽和的頂點(diǎn)，i∈{

5、0，1，2，3}，滿足x，y之間的距離為奇數(shù)，則M可以擴(kuò)成Q4n\{x，y}的一個(gè)完美匹配.
　　第三章中，研究4元n方體的匹配圖的一些性質(zhì).主要結(jié)果如下:記[n]={0，1，…，n-1}.對(duì)任意α∈[n]，記Iα1n={(u0u1…uα-11uα+1…un-1，u0u1…uα-12uα+1…un-1)|ui∈[4]，i∈[n]\{α}∪{(u0u1… uα-10uα+1…un-1,u0u1…uα-13uα+1…un-1)|ui∈

6、[4]，i∈[n]\{α}}，Iα2n={(u0u1…uα-12uα+1…un-1,u0u1…uα-13uα+1…un-1)|ui∈[4],i∈[n]\{α}}∪{(u0u1…uα-10uα+1…un-1,u0u1…uα-11uα+1…un-1)|ui∈[4]，i∈[n]\{α}}，則Iα1n和Iα2n都是Q4n的完美匹配.設(shè)Iαin，Iβjn是Q4n的兩個(gè)完美匹配，i，j∈{1，2}，α，β∈[n]，則在M(Q4n)中存在Iαin和I