正則圖的xyth-變換圖的譜.pdf

1、圖論研宄中一個(gè)重要而活躍的領(lǐng)域就是圖譜理論，圖的譜可以用來(lái)刻畫(huà)圖的某些性質(zhì)。其中最為常見(jiàn)的是對(duì)圖的鄰接譜和拉普拉斯譜的研宄。由全圖演變而來(lái)的變換圖，因其譜可由原圖來(lái)刻畫(huà)，近來(lái)也是研宄的熱點(diǎn)。
　　設(shè)D是無(wú)環(huán)無(wú)重邊的有向圖，頂點(diǎn)集V(D)= V，邊集五(D)=E。則乃。表示頂點(diǎn)為V的無(wú)邊有向圖；D1表示頂點(diǎn)為V的完全有向圖；D+=D是D的補(bǔ)圖De。本文介紹了正則有向圖D有四個(gè)變量x,y,t,h E{+,-，0,1}的變換圖D21—，

2、其中t= h。D的xyth-變換圖是指有向圖D2^、Dxy00=Dx U Dy。且D2^=Dx U Dy UT UHh，其中，當(dāng)t=+時(shí)，丁*= T(D)；當(dāng)t=—時(shí)，丁*= Tcb(D)；當(dāng)t=1時(shí)，T*是以V和E為兩部分頂點(diǎn)集的二部圖，其邊集為V xE。當(dāng)h=+時(shí)，Hh= H(D)；當(dāng)h=—時(shí)，Hh=Hcd(D)；當(dāng)h=1時(shí)，Hh是以V和E兩部分為頂點(diǎn)集的二部圖，其邊集為E x V。
　　接著用r正則有向圖D的頂點(diǎn)數(shù)n，度數(shù)r

3、，以及D的鄰接譜來(lái)刻畫(huà)其變換圖D￥h所有的鄰接譜。重要的是文章應(yīng)用矩陣?yán)碚?，研宄了變換圖D＃h，Dy;rfh，(D—、-1之間的同構(gòu)關(guān)系，并由此找出了鄰接同譜的變換圖對(duì)，以及給出了鄰接同譜但不同構(gòu)的圖對(duì)。
　　本文還用r正則有向圖D的頂點(diǎn)數(shù)n，度數(shù)r，以及D的拉普拉斯譜來(lái)刻畫(huà)了變換圖Dx—所有的拉普拉斯譜。當(dāng)t或h為零時(shí)，由于度矩陣的變化，與鄰接譜可以按照;x與y相同來(lái)分類計(jì)算有所不同，其也需一一計(jì)算。
　　最后本文用D的頂