- 相關(guān)推薦
大學代數(shù)知識在互聯(lián)網(wǎng)絡中的應用
大學代數(shù)知識在互聯(lián)網(wǎng)絡中的應用
周進鑫
�。ū本┙煌ù髮W數(shù)學系，北京100044）
摘要：代數(shù)方面的知識是數(shù)學工作者的必備基礎(chǔ)。本文通過討論大學代數(shù)知識在互聯(lián)網(wǎng)絡對稱性研究中的應用，提出大學數(shù)學專業(yè)學生檢驗自己對已學代數(shù)知識的掌握程度的一種新思路，即思考一些比較前沿的數(shù)學問題。
關(guān)鍵詞：代數(shù)；對稱；自同構(gòu)
基金項目：本文得到國家自然科學基金的資助（編號：11271012）
作者簡介：周進鑫（1979-），男（漢族），山西大同人，北京交通大學數(shù)學系副教授，碩士生導師，博士，研究方向：圖的對稱性、網(wǎng)絡的容錯性及可靠性。
一、引言與基本概念
《高等代數(shù)》（advanced algebra）和《近世代數(shù)》（abstractalgebra）是大學數(shù)學專業(yè)有關(guān)代數(shù)方面的兩門重要課程。前者是大學數(shù)學各個專業(yè)最重要的主干基礎(chǔ)課程之一，后者既是對前者的繼續(xù)和深入，也是代數(shù)方面研究生課程的重要先修課程之一。這兩門課程概念眾多，內(nèi)容高度抽象，是數(shù)學專業(yè)學生公認的難學課程。甚至，很多學生修完《高等代數(shù)》之后，就放棄了繼續(xù)學習《近世代數(shù)》。即使對于那些堅持認真學完這兩門課程的學生來講，也未必能做到“不僅知其然，還知其所以然”，而要做到“知其所以然，還要知其不得不然”就更是難上加難了。眾所周知，學習數(shù)學，不僅邏輯上要搞懂，還要做到真正掌握，學以致用，也就是“學到手”。當然，做課后習題和考試是檢驗是否學會的一個重要手段。然而，利用所學知識獨立地去解決一些比較前沿的數(shù)學問題，也是檢驗我們對于知識理解和掌握程度的一個重要方法。這樣做，不僅有助于鞏固和加深對所學知識的理解，也有助于培養(yǎng)學生的創(chuàng)新意識和自學能力。筆者結(jié)合自己所從事的教學和科研工作，在這方面做了一些嘗試。
互連網(wǎng)絡的拓撲結(jié)構(gòu)可以用圖來表示。為了提高網(wǎng)絡性能，考慮到高對稱性圖具有許多優(yōu)良的性質(zhì)，數(shù)學與計算機科學工作者通常建議使用具有高對稱性的圖來做互聯(lián)網(wǎng)絡的模型。事實上，許多著名的網(wǎng)絡，如：超立方體網(wǎng)絡、折疊立方體網(wǎng)絡、交錯群圖網(wǎng)絡等都具有很強的對稱性。(www.gymyzhishaji.com)而且這些網(wǎng)絡的構(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的邊當且僅當{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}。
設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)絡（記作Qn）是一個以Z2n為頂點集合的圖，對于Qn的任意兩個頂點u和v，{u，v}是Qn的一條邊當且僅當v-u=ei，其中1≤i≤n。
●n維折疊立方體網(wǎng)絡（記作FQn）是一個以Z2n為頂點集合的圖，對于Qn的任意兩個頂點u和v，{u，v}是Qn的一條邊當且僅當v-u=ei（1≤i≤n）或者v-u=e1+…+en。
●n維交錯群圖網(wǎng)絡（記作AGn）是一個以n級交錯群An為頂點集合的圖，對于AGn的任意兩個頂點u和v，{u，v}是AGn的一條邊當且僅當vu-1=ai或ai-1，這里3≤i≤n，ai=（1，2，i）為一個3輪換。
一個自然的問題是：這三類網(wǎng)絡是否是頂點對稱的？是否邊對稱的？但值得我們注意的是，這些問題都可以利用大學所學的代數(shù)知識得到完全解決。
二、三類網(wǎng)絡的對稱性
先來看n維超立方體網(wǎng)絡的對稱性。
定理一：n維超立方體網(wǎng)絡Qn是頂點和邊對稱的。
證明：對于Z2n中的任一向量x=（x1，…，xn），如下定義V（Qn）=Z2n上面的一個映射：f（x）：u→u+x，u取遍V（Qn）中所有元素。容易驗證f（x）是一個1-1映射。（注：這個映射在《高等代數(shù)》中已學過，即所謂的平移映射。）而{u，v}是Qn的一條邊，當且僅當v-u=ei（1≤i≤n），當且僅當vf（x）-uf（x）=ei（1≤i≤n），當且僅當{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)絡FQn是頂點和邊對稱的。
最后，來決定n維交錯群圖網(wǎng)絡的對稱性。
定理三：n維交錯群圖網(wǎng)絡AGn是頂點和邊對稱的。
證明：首先，來證明AGn是頂點對稱的。給定An中的一個元素g，如下定義一個映射：R（g）：x→xg，其中x取遍An中所有元素。容易驗證R（g）為AGn頂點集合上上的一個1-1映射。（注：這個映射在有限群論中是一個十分重要的映射，即所謂的右乘變換。）設{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)樗趃下的共軛。這也是有限群論中一個十分常用的映射。）令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)絡的對稱性。不難看出，除了必要的圖論概念外，我們的證明主要利用了《高等代數(shù)》和《近世代數(shù)》的知識。做為上述問題的繼續(xù)和深入，有興趣的同學還可以考慮以下問題：
1.這些網(wǎng)絡是否具有更強的對稱性？比如：弧對稱性？距離對稱性？
2.完全決定這些網(wǎng)絡的全自同構(gòu)群。
實際上，利用與上面證明相同的思路，結(jié)合對圖的局部結(jié)構(gòu)的分析，利用一些組合技巧，這些問題也可以得到解決。
三、小結(jié)
大學所學代數(shù)知識在數(shù)學領(lǐng)域中的許多學科、乃至其他領(lǐng)域都有重要的應用。筆者認為任課教師可以根據(jù)自己所熟悉的科研領(lǐng)域，選取一些與大學代數(shù)知識有緊密聯(lián)系的前沿數(shù)學問題，引導一些學有余力的學生開展相關(guān)研究，甚至可以吸引一些本科生加入自己的課題組。當然，教師要給予必要的指導，比如講解相關(guān)背景知識、必要的概念和方法等。指導學生從相對簡單的問題入手，循序漸進，由易到難，逐步加深對代數(shù)學知識的系統(tǒng)理解，積累一些經(jīng)驗，為考慮進一步的問題奠定基礎(chǔ)。
本文所提到的利用《高等代數(shù)》和《近世代數(shù)》的知識來研究網(wǎng)絡的對稱性就是筆者在教學工作中曾做過的一些嘗試。在該方面，筆者指導完成了由三名大三學生參加的國家級大學生創(chuàng)新實驗項目一項。這樣以來，學生在學習經(jīng)典數(shù)學知識的同時，也可以思考一些比較前沿的數(shù)學問題；學生在鞏固已學知識的同時，也可以激發(fā)其學習興趣，訓練學生的邏輯思維，培養(yǎng)學生的創(chuàng)新思維，以及獨立發(fā)現(xiàn)問題和解決問題的能力。
【大學代數(shù)知識在互聯(lián)網(wǎng)絡中的應用】相關(guān)文章：
代數(shù)初步知識08-16
密度知識的應用08-17
人工智能在知識付費產(chǎn)業(yè)中的應用研究08-19
“信息溝”在大學英語口語教學中的應用08-27
比法在物理中的應用08-17
生活中的化學在教學中的應用08-23
詞匯軟件在大學英語詞匯教學中的應用08-26
代數(shù)式08-17