亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        矩陣對角化在圖譜理論中的應用

        2015-08-05 16:48:51杜志斌
        科教導刊 2015年21期
        關鍵詞:圖譜

        杜志斌

        摘 要 矩陣對角化是高等代數中的一個重要內容,其在矩陣研究中起著非常重要的作用。圖譜理論主要運用線性代數方法來研究圖的各種性質。本文將給出矩陣對角化在圖譜理論中的一個應用。

        關鍵詞 矩陣對角化 圖譜 特征值重數

        中圖分類號:O151.21 文獻標識碼:A DOI:10.16400/j.cnki.kjdkx.2015.07.027

        Application of Diagonalization of Matrices in Spectral Graph Theory

        DU Zhibin

        (School of Mathematics and Statistics, Zhaoqing University, Zhaoqing, Guangdong 526061)

        Abstract Diagonalization of matrices is an important part in higher algebra, which plays an important role in the research of matrices. Spectral graph theory mainly uses the methods related to linear algebra to study various properties of graphs. In this paper, we will present an application of diagonalization of matrices in spectral graph theory.

        Key words diagonalization of matrices; spectra of graphs; multiplicity of eigenvalues

        0 引言

        記為階單位矩陣。對于任意實對稱陣,若是的一個特征值,則記()為的(代數)重數。此外,若不是的特征值,則習慣上記作() = 0。

        矩陣對角化是高等代數中的一個重要內容,其在矩陣研究中起著非常重要的作用。特別地,若階矩陣可對角化,則對于任意常數,總有

        秩() = () ? ?(1)

        參見[1]。

        本文將給出矩陣對角化在圖譜理論中的一個應用。所謂圖譜理論,它主要運用線性代數方法來研究圖的各種性質。

        作為數與形相互結合的一個典范,圖與矩陣有著緊密的聯系。給定一個圖,可定義出一些相應的矩陣,如鄰接矩陣、Laplacian矩陣等。通過研究這些由圖所導出的矩陣的特征多項式、特征值、特征向量等,學者們得到了一大批精彩的新理論和結果,并由此建立了圖譜理論。

        在圖譜理論的研究中,研究的核心內容之一是基于圖所導出的各類矩陣的特征值,其中以圖的鄰接矩陣的研究尤為突出。

        本文所考慮的圖皆為無向簡單圖。圖的鄰接矩陣()定義為[2]:

        圖的鄰接矩陣的特征值簡稱為圖的特征值,由這些特征值所組成的多重集稱為圖的鄰接譜。

        顯然圖的鄰接矩陣是一個實對稱陣,從而它可對角化。于是,我們很自然地提出一個問題:矩陣對角化的知識是否可運用到圖的鄰接譜的研究中。答案是肯定的。本文將給出矩陣對角化在計算圖的鄰接譜中的一個應用。

        1 矩陣對角化在計算圖的鄰接譜中的應用

        現有圖以及階方陣 = ()。若將圖的點集劃分為個點子集,,…,,且使得中的每個點都與中的個點相鄰,其中, = 1,2,…,,則稱為圖的因子(divisor)。特別地,若為圖的因子,根據[2,定理4.5],的特征值同時也是圖的鄰接矩陣()的特征值。

        下面我們將運用矩陣對角化(即式子(1))來計算一些具有低階因子(即因子階數為 = 2,3)的圖的鄰接譜。特別地,對于因子階數為 = 2的情形,我們定義了一類圖——完全分割圖(complete split graph),而對于因子階數為 = 3的情形,我們定義了另一類圖——廣義完全分割圖。

        記為行列零矩陣,且記為一個行列矩陣,其中每個元素皆為1。特別地,若 = ,則將簡記為,而將簡記為。

        1.1 完全分割圖的鄰接譜

        所謂完全分割圖(,)即為 ,其中表示個點的完全圖,表示個點的空圖,而 表示中的每個點與中的每個點皆為相鄰的。例如,圖1所示即為完全分割圖(5,2)。

        圖1 完全分割圖(5,2)

        我們不妨將(,)中的點劃分為兩部分,,其中是(,)的頭個點,對應著完全圖,而剩余的個點記作,對應著空圖。此外,為了方便起見,令 = ((,))。

        易見,圖存在一個2階因子

        即該矩陣的2個特征值亦為的特征值。對于剩余的個特征值,我們將利用式子(1)來求得。

        首先,根據完全分割圖(,)的構造及其點的編號,可知其鄰接矩陣的結構如下:

        顯然有秩(0) = 秩() = + 1。現根據(1),可得(0) = 。

        另一方面,由于

        從而有秩( + ) = + 1?,F根據(1),可得() = 。

        綜上所述,我們可求得完全分割圖(,)的鄰接矩陣的所有特征值。

        1.2 廣義完全分割圖的鄰接譜

        所謂廣義完全分割圖(,,)即為 (∩),其中與分別表示個點與個點的完全圖,表示個點的空圖,而 表示中的每個點與∪中的每個點皆為相鄰的,∪表示與點不交的并。例如,圖2所示即為廣義完全分割圖(8,2,3)。

        圖2 廣義完全分割圖(8,2,3)

        我們不妨將(,,)中的點劃分為三部分,,,其中是(,,)的頭個點,對應著完全圖,是(,,)的第 + 1個到第 + 個點,對應著完全圖,而剩余的個點記作,對應著空圖。此外,為了方便起見,令 = ((,,))。

        易見,圖存在一個3階因子

        即該矩陣的3個特征值亦為的特征值。對于剩余的個特征值,我們將利用式子(1)來求得。

        首先,根據廣義完全分割圖(,,)的構造及其點的編號,可知其鄰接矩陣的結構如下:

        顯然有秩(0) = 秩() = + + 1?,F根據(1),可得(0) = 。

        另一方面,由于

        從而有秩( + ) = + 2?,F根據(1),可得() = + 。

        綜上所述,我們可求得廣義完全分割圖(,,)的鄰接矩陣的所有特征值。

        1.3 總結

        上文介紹了如何運用矩陣對角化來計算完全分割圖與廣義完全分割圖的鄰接譜。特別地,完全分割圖具有一個2階因子,而廣義完全分割圖具有一個3階因子。事實上,對于其它具有因子的圖,我們亦可類似地求得其鄰接譜。

        此外,在圖譜理論的研究中,圖的Laplacian矩陣[4]、無符號Laplacian矩陣[5]、正規(guī)化Laplacian矩陣[6]、距離矩陣[7]等基于圖所導出的矩陣的譜也是關注的熱點。類似于上述方法,我們亦可求得這些基于圖所導出的矩陣的譜。

        參考文獻

        [1] 張和瑞,郝鈵新.高等代數[M](第五版).北京:高等教育出版社,2007.

        [2] D.Cvetkovi, M. Doob, H. Sachs, Spectra of Graphs-Theory and Application[M]. New York: Academic Press,1980.

        [3] A.E. Brouwer, W.H. Haemers, Spectra of graphs[M].New York: Springer,2012.

        [4] R.Grone, R.Merris, The Laplacian spectrum of a graph II[J].SIAM J.Discrete Math.,1994.7:221-229.

        [5] D.Cvetkovi, P. Rowlinson, S.K. Simi, Eigenvalue bounds for the signless Laplacian[J]. Publ. Inst. Math. (Beograd), 2007.81:11-27.

        [6] F. R. K. Chung, Spectral Graph Theory[M].Providence: American Math. Soc., 1997.

        [7] R. Merris, The distance spectrum of a tree[J].J. Graph Theory,1990.14:365-369.

        猜你喜歡
        圖譜
        高清大腦皮層發(fā)育新圖譜繪成
        軍事文摘(2022年24期)2022-12-30 11:44:08
        基于圖對比注意力網絡的知識圖譜補全
        中醫(yī)藥知識圖譜應用現狀分析及癡呆痰瘀互結證知識圖譜構建探索
        礞石滾痰丸HPLC指紋圖譜的研究
        繪一張成長圖譜
        清清顆粒HPLC-DAD指紋圖譜
        中成藥(2017年9期)2017-12-19 13:34:55
        淡豆豉UPLC指紋圖譜
        中成藥(2017年7期)2017-11-22 07:34:07
        補腎強身片UPLC指紋圖譜
        中成藥(2017年3期)2017-05-17 06:09:01
        主動對接你思維的知識圖譜
        熏硫與未熏硫白芷的體內外HPLC圖譜對比分析
        中藥與臨床(2015年5期)2015-12-17 02:39:23
        乱人伦中文字幕在线不卡网站 | 无码人妻人妻经典| 日日躁夜夜躁狠狠躁超碰97| 亚洲女同成av人片在线观看| 国产久久久自拍视频在线观看| 蜜桃av精品一区二区三区| 亚洲丁香五月天缴情综合| 日韩欧美国产亚洲中文| 国产一区二区三区av观看| 亚洲国产精品一区二区成人片国内| 四虎影视永久地址www成人| 亚洲制服无码一区二区三区| 亚洲一区二区三区最新视频| 欧洲美女黑人粗性暴交视频| 国产欧美日韩综合精品二区| 久久中文字幕日韩精品| 一区二区亚洲精品国产精| 99久久99久久久精品齐齐| 欧美喷潮久久久xxxxx| 人妻爽综合网| 久久精品国产亚洲av成人文字| 免费网站看v片在线18禁无码| 水蜜桃久久| 伊人久久大香线蕉综合av | 日日天干夜夜狠狠爱| 亚洲av成人一区二区三区av| 日本一区不卡高清在线观看| 国产三级视频不卡在线观看| 国产成人无码免费视频在线| 精品中文字幕久久久久久| 精品久久中文字幕一区| av免费不卡国产观看| 日韩AV不卡六区七区| 国产毛片一区二区三区| 亚洲大尺度无码无码专区| 性高朝久久久久久久| 天堂av无码大芭蕉伊人av孕妇黑人 | 午夜不卡无码中文字幕影院| 波多野结衣免费一区视频| 日韩极品视频在线观看| 色佬精品免费在线视频|