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