大學(xué)代數(shù)知識在互聯(lián)網(wǎng)絡(luò)中的應(yīng)用

　　大學(xué)代數(shù)知識在互聯(lián)網(wǎng)絡(luò)中的應(yīng)用

　　周進鑫

　�。ū本┙煌ù髮W(xué)數(shù)學(xué)系，北京100044）

　　摘要：代數(shù)方面的知識是數(shù)學(xué)工作者的必備基礎(chǔ)。本文通過討論大學(xué)代數(shù)知識在互聯(lián)網(wǎng)絡(luò)對稱性研究中的應(yīng)用，提出大學(xué)數(shù)學(xué)專業(yè)學(xué)生檢驗自己對已學(xué)代數(shù)知識的掌握程度的一種新思路，即思考一些比較前沿的數(shù)學(xué)問題。

　　關(guān)鍵詞：代數(shù)；對稱；自同構(gòu)

　　基金項目：本文得到國家自然科學(xué)基金的資助（編號：11271012）

　　作者簡介：周進鑫（1979-），男（漢族），山西大同人，北京交通大學(xué)數(shù)學(xué)系副教授，碩士生導(dǎo)師，博士，研究方向：圖的對稱性、網(wǎng)絡(luò)的容錯性及可靠性。

　　一、引言與基本概念

　　《高等代數(shù)》（advanced algebra）和《近世代數(shù)》（abstractalgebra）是大學(xué)數(shù)學(xué)專業(yè)有關(guān)代數(shù)方面的兩門重要課程。前者是大學(xué)數(shù)學(xué)各個專業(yè)最重要的主干基礎(chǔ)課程之一，后者既是對前者的繼續(xù)和深入，也是代數(shù)方面研究生課程的重要先修課程之一。這兩門課程概念眾多，內(nèi)容高度抽象，是數(shù)學(xué)專業(yè)學(xué)生公認(rèn)的難學(xué)課程。甚至，很多學(xué)生修完《高等代數(shù)》之后，就放棄了繼續(xù)學(xué)習(xí)《近世代數(shù)》。即使對于那些堅持認(rèn)真學(xué)完這兩門課程的學(xué)生來講，也未必能做到“不僅知其然，還知其所以然”，而要做到“知其所以然，還要知其不得不然”就更是難上加難了。眾所周知，學(xué)習(xí)數(shù)學(xué)，不僅邏輯上要搞懂，還要做到真正掌握，學(xué)以致用，也就是“學(xué)到手”。當(dāng)然，做課后習(xí)題和考試是檢驗是否學(xué)會的一個重要手段。然而，利用所學(xué)知識獨立地去解決一些比較前沿的數(shù)學(xué)問題，也是檢驗我們對于知識理解和掌握程度的一個重要方法。這樣做，不僅有助于鞏固和加深對所學(xué)知識的理解，也有助于培養(yǎng)學(xué)生的創(chuàng)新意識和自學(xué)能力。筆者結(jié)合自己所從事的教學(xué)和科研工作，在這方面做了一些嘗試。

　　互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可以用圖來表示。為了提高網(wǎng)絡(luò)性能，考慮到高對稱性圖具有許多優(yōu)良的性質(zhì)，數(shù)學(xué)與計算機科學(xué)工作者通常建議使用具有高對稱性的圖來做互聯(lián)網(wǎng)絡(luò)的模型。事實上，許多著名的網(wǎng)絡(luò)，如：超立方體網(wǎng)絡(luò)、折疊立方體網(wǎng)絡(luò)、交錯群圖網(wǎng)絡(luò)等都具有很強的對稱性。(m.panasonaic.com)而且這些網(wǎng)絡(luò)的構(gòu)造都是基于一個重要的代數(shù)結(jié)構(gòu)即“群”。它們的對稱性也是通過其自同構(gòu)群在其各個對象（如：頂點集合、邊集合等）上作用的傳遞性來描述的。

　　下面介紹一些相關(guān)的概念。一個圖G是一個二元組（V，E），其中V是一個有限集合，E為由V的若干二元子集組成的集合。稱V為G的頂點集合，E為G的邊集合。E中的每個二元子集{u，v}稱為是圖G的連接頂點u與v的一條邊。圖G的一個自同構(gòu)f是G的頂點集合V上的一個一一映射（即置換），使得{u，v}為G的邊當(dāng)且僅當(dāng){uf，vf}也為G的邊。圖G的全體自同構(gòu)依映射的合成構(gòu)成一個群，稱為G的全自同構(gòu)群，記作Aut（G）。圖G稱為是頂點對稱的，如對于G的任意兩個頂點u與v，存在G的自同構(gòu)f使得uf=v。圖G稱為是邊對稱的，如對于G的任意兩條邊{u，v}和{x，y}，存在G的自同構(gòu)f使得{uf，vf}={x，y}。

　　設(shè)n為正整數(shù)，令Z2n為有限域Z2={0，1}上的n維線性空間。由《近世代數(shù)》知識可知，Z2n的加法群是一個初等交換2群。在Z2n中取出如下n個單位向量：

　　e1=（1，0，…，0），e2=（0，1，0，…，0），…，en=（0，…，0，1）。

　　●n維超立方體網(wǎng)絡(luò)（記作Qn）是一個以Z2n為頂點集合的圖，對于Qn的任意兩個頂點u和v，{u，v}是Qn的一條邊當(dāng)且僅當(dāng)v-u=ei，其中1≤i≤n。

　　●n維折疊立方體網(wǎng)絡(luò)（記作FQn）是一個以Z2n為頂點集合的圖，對于Qn的任意兩個頂點u和v，{u，v}是Qn的一條邊當(dāng)且僅當(dāng)v-u=ei（1≤i≤n）或者v-u=e1+…+en。

　　●n維交錯群圖網(wǎng)絡(luò)（記作AGn）是一個以n級交錯群An為頂點集合的圖，對于AGn的任意兩個頂點u和v，{u，v}是AGn的一條邊當(dāng)且僅當(dāng)vu-1=ai或ai-1，這里3≤i≤n，ai=（1，2，i）為一個3輪換。

　　一個自然的問題是：這三類網(wǎng)絡(luò)是否是頂點對稱的？是否邊對稱的？但值得我們注意的是，這些問題都可以利用大學(xué)所學(xué)的代數(shù)知識得到完全解決。

　　二、三類網(wǎng)絡(luò)的對稱性

　　先來看n維超立方體網(wǎng)絡(luò)的對稱性。

　　定理一：n維超立方體網(wǎng)絡(luò)Qn是頂點和邊對稱的。

　　證明：對于Z2n中的任一向量x=（x1，…，xn），如下定義V（Qn）=Z2n上面的一個映射：f（x）：u→u+x，u取遍V（Qn）中所有元素。容易驗證f（x）是一個1-1映射。（注：這個映射在《高等代數(shù)》中已學(xué)過，即所謂的平移映射。）而{u，v}是Qn的一條邊，當(dāng)且僅當(dāng)v-u=ei（1≤i≤n），當(dāng)且僅當(dāng)vf（x）-uf（x）=ei（1≤i≤n），當(dāng)且僅當(dāng){v（f x），u（f x）}是Qn的一條邊。所以，f（x）也是Qn的一個自同構(gòu)。這樣，任取V（Qn）中兩個頂點u和v，則uf（v-u）=v。從而說明Qn是頂點對稱的。

　　下面證明Qn是邊對稱的。只需證明：對于Qn的任一條邊{u，v}，都存在Qn的自同構(gòu)g使得{ug，vg}={0，e1}，其中0為Z2n中的零向量。事實上，{uf（-u），vf（-u）}={0，v-u}，其中v-u=ei （1≤i≤n）。顯然，e1，…，ei-1，ei，ei+1，…，en和ei，…，ei-1，e1，ei+1，…，en是Z2n的兩組基向量。由《高等代數(shù)》知識可知存在Z2n上的可逆線性變換t使得t對換e1和ei而不動其余向量。此時易見，若{a，b}是Qn的一條邊，則a-b=ej （1≤j≤n）。若j=1，則at-bt=ei；若j=i，則at-bt=e1；若j≠1，i，則at-bt=ej；所以{at，bt}也是Qn的一條邊。由定義可知，t是Qn的一個自同構(gòu)。進一步，{0t，（v-u）t}={0，e1}，即{uf（-u）t，vf（-u）t}={0，e1}。結(jié)論得證。

　　利用和定理一相似的辦法，我們進一步可以得到如下定理。

　　定理二：n維折疊立方體網(wǎng)絡(luò)FQn是頂點和邊對稱的。

　　最后，來決定n維交錯群圖網(wǎng)絡(luò)的對稱性。

　　定理三：n維交錯群圖網(wǎng)絡(luò)AGn是頂點和邊對稱的。

　　證明：首先，來證明AGn是頂點對稱的。給定An中的一個元素g，如下定義一個映射：R（g）：x→xg，其中x取遍An中所有元素。容易驗證R（g）為AGn頂點集合上上的一個1-1映射。（注：這個映射在有限群論中是一個十分重要的映射，即所謂的右乘變換。）設(shè){u，v}是AGn的一條邊，則vu-1=ai或ai-1，這里1≤i≤n。易見，（vg）（ug）-1=vu-1。所以，{vR（g），uR（g）}是AGn的一條邊。因此，R（g）是AGn的一個自同構(gòu)。這樣，對于AGn的任意兩個頂點u和v，有uR（g）=v，這里g=u-1v。這說明AGn是頂點對稱的。

　　下面來證明AGn是邊對稱的。只需證明對于AGn的任一條邊{u，v}，都存在AGn的自同構(gòu)g使得{ug，vg}={e，a3}，其中e為An中的單位元。給定對稱群Sn中的一個元素g，如下定義一個映射：C（g）：x→g-1xg，其中x取遍An中所有元素。由《近世代數(shù)》知識可知，交錯群An是對稱群Sn的正規(guī)子群。容易驗證C（g）是AGn的頂點集合上的一個1-1映射。（注：這個映射其實就是把An中任一元素x變?yōu)樗�在g下的共軛。這也是有限群論中一個十分常用的映射。）令x=（1，2），y（j）=（3，j），j=3，…，n。下面證明C（x）和C（y（j））都是AGn的自通構(gòu)。取{u，v}為AGn的任一條邊，則vu-1=ai或ai-1。從而，vC（x） （u-1） C（x）=（x-1vx）（x -1u-1x）=x-（1 vu-1）x=ai-1或ai。

　　因此，{uC（x），vC（x）}也是AGn的一條邊。從而說明C（x）是AGn的自通構(gòu)。同理，若j=i，有vC（y（j））（u-1）C（y（j））=a3-1或a3；若j≠i，則有vC（y（j））（u-1）C（y（j））=ai-1或ai。這說明{uC（y（j）），vC（y（j））}也是AGn的一條邊，從而C（y（j））是AGn的自通構(gòu)�，F(xiàn)在，對于AGn的任一條邊{u，v}，令g=u-1，則{uR（g），vR（g）}={e，vu-1}={e，ai}或{e，ai-1}。若i=3，則{e，a3-1}C（x）={e，a3}。而若i ≠3，則{e，ai}C（y（j））={e，a3}而{e，ai-1}C（y（j））={e，a3-1}。由此可見，總存在AGn的自同構(gòu)g使得{ug，vg}={e，a3}，結(jié)論得證。

　　至此，完全決定了這三類網(wǎng)絡(luò)的對稱性。不難看出，除了必要的圖論概念外，我們的證明主要利用了《高等代數(shù)》和《近世代數(shù)》的知識。做為上述問題的繼續(xù)和深入，有興趣的同學(xué)還可以考慮以下問題：

　　1.這些網(wǎng)絡(luò)是否具有更強的對稱性？比如：弧對稱性？距離對稱性？

　　2.完全決定這些網(wǎng)絡(luò)的全自同構(gòu)群。

　　實際上，利用與上面證明相同的思路，結(jié)合對圖的局部結(jié)構(gòu)的分析，利用一些組合技巧，這些問題也可以得到解決。

　　三、小結(jié)

　　大學(xué)所學(xué)代數(shù)知識在數(shù)學(xué)領(lǐng)域中的許多學(xué)科、乃至其他領(lǐng)域都有重要的應(yīng)用。筆者認(rèn)為任課教師可以根據(jù)自己所熟悉的科研領(lǐng)域，選取一些與大學(xué)代數(shù)知識有緊密聯(lián)系的前沿數(shù)學(xué)問題，引導(dǎo)一些學(xué)有余力的學(xué)生開展相關(guān)研究，甚至可以吸引一些本科生加入自己的課題組。當(dāng)然，教師要給予必要的指導(dǎo)，比如講解相關(guān)背景知識、必要的概念和方法等。指導(dǎo)學(xué)生從相對簡單的問題入手，循序漸進，由易到難，逐步加深對代數(shù)學(xué)知識的系統(tǒng)理解，積累一些經(jīng)驗，為考慮進一步的問題奠定基礎(chǔ)。

　　本文所提到的利用《高等代數(shù)》和《近世代數(shù)》的知識來研究網(wǎng)絡(luò)的對稱性就是筆者在教學(xué)工作中曾做過的一些嘗試。在該方面，筆者指導(dǎo)完成了由三名大三學(xué)生參加的國家級大學(xué)生創(chuàng)新實驗項目一項。這樣以來，學(xué)生在學(xué)習(xí)經(jīng)典數(shù)學(xué)知識的同時，也可以思考一些比較前沿的數(shù)學(xué)問題；學(xué)生在鞏固已學(xué)知識的同時，也可以激發(fā)其學(xué)習(xí)興趣，訓(xùn)練學(xué)生的邏輯思維，培養(yǎng)學(xué)生的創(chuàng)新思維，以及獨立發(fā)現(xiàn)問題和解決問題的能力。

【大學(xué)代數(shù)知識在互聯(lián)網(wǎng)絡(luò)中的應(yīng)用】相關(guān)文章：

代數(shù)初步知識08-16

密度知識的應(yīng)用08-17

人工智能在知識付費產(chǎn)業(yè)中的應(yīng)用研究08-19

網(wǎng)絡(luò)多媒體在大學(xué)英語寫作教學(xué)中的應(yīng)用08-20

“信息溝”在大學(xué)英語口語教學(xué)中的應(yīng)用08-27

比法在物理中的應(yīng)用08-17

生活中的化學(xué)在教學(xué)中的應(yīng)用08-23

小學(xué)六年級《代數(shù)初步知識 》教案08-16

詞匯軟件在大學(xué)英語詞匯教學(xué)中的應(yīng)用08-26

代數(shù)式08-17