圖“節(jié)點(diǎn)”，以及哪些節(jié)點(diǎn)之間有“邊”第1頁/共22頁作為一個(gè)數(shù)學(xué)概念的“圖”（graph）節(jié)點(diǎn)，邊（圓括號表示（x,y）中的元素次序無關(guān)）標(biāo)號圖（labeledgraph），無標(biāo)號圖（graph）同構(gòu)，異構(gòu)第2頁/共22頁（不一樣的）圖的個(gè)數(shù)（枚舉）給定節(jié)點(diǎn)數(shù)（n）標(biāo)號圖？無標(biāo)號圖？Polya定理告訴我們?nèi)绾斡?jì)算無標(biāo)號圖的個(gè)數(shù)如何判斷兩個(gè)圖是否“同構(gòu)”依然是圖論的最基本挑戰(zhàn)之一第3頁/共22頁無標(biāo)號圖的個(gè)數(shù)第4頁/共22頁無向圖，有向圖（directedgraph）也可以是標(biāo)號或者無標(biāo)號的<x,y>和<y,x>有可能同時(shí)存在第5頁/共22頁路，距離，連通，連通分量路（path，路徑，通路）：節(jié)點(diǎn)序列，相鄰兩個(gè)節(jié)點(diǎn)之間存在一條邊長度：節(jié)點(diǎn)數(shù)減1；或者，所涉及邊的條數(shù)簡單路徑，回路（僅端點(diǎn)相同的路徑）距離：兩個(gè)節(jié)點(diǎn)之間最短路徑的長度連通圖：任何兩個(gè)節(jié)點(diǎn)之間都存在一條路連通分量連通子圖不被真包含在任何其他連通子圖中第6頁/共22頁例子：路，距離，連通分量節(jié)點(diǎn)I和M之間有多少不同的路？有多少不同的簡單路徑？它們之間的距離？({A,B},{(A,B)})是不是連通分量？({H,L,M},{(H,L),(L,M),(H,M)})是不是連通分量？第7頁/共22頁大規(guī)模社會(huì)網(wǎng)絡(luò)中的超大連通分量第8頁/共22頁橋，捷徑（localbridge）橋：具有特別性質(zhì)的邊，刪除它，其兩個(gè)端點(diǎn)之間就不再有路刪除它，增加圖的連通分量的個(gè)數(shù)捷徑：也是一種邊，刪除它，其兩個(gè)端點(diǎn)之間的距離至少為3。橋可以看成是捷徑的一個(gè)特例第9頁/共22頁對于有向圖：有向路徑，強(qiáng)連通分量有向路徑：節(jié)點(diǎn)序列，相鄰節(jié)點(diǎn)之間有從前往后的有向邊強(qiáng)連通分量任意兩個(gè)節(jié)點(diǎn)之間存在有向路徑（兩個(gè)方向）的有向子圖不被真包含在任何其他滿足性質(zhì)(1)的子圖中({B,C,D},{<B,C>,<C,D>,<D,B>})第10頁/共22頁二部圖，圖上的廣度優(yōu)先搜索二部圖（bipartitegraph）：節(jié)點(diǎn)可以被分成兩組，組內(nèi)沒有邊圖上的廣度優(yōu)先搜索（breadth-firstsearch）從某一點(diǎn)開始，對圖的節(jié)點(diǎn)的一種“遍歷”方式第11頁/共22頁從LINC開始廣度優(yōu)先搜索{LINC}{MIT,CASE}{CARN,BBN,UTAH}{HARV,SDC,RAND,SRI}{UCSB,UCLA,STAN}BFS從概念上對圖中的節(jié)點(diǎn)進(jìn)行了一個(gè)“分層”，所涉及到的邊“自然形成了”一個(gè)二部圖第12頁/共22頁典型現(xiàn)實(shí)網(wǎng)絡(luò)（圖）合作圖例如，一群學(xué)者之間合著關(guān)系（co-authorship）節(jié)點(diǎn)：人；邊：當(dāng)且僅當(dāng)兩個(gè)人有合著的文章交流網(wǎng)例如，一所大學(xué)師生之間的電子郵件關(guān)系網(wǎng)節(jié)點(diǎn)：人；邊：兩人之間發(fā)過一定量的往返郵件信息鏈接網(wǎng)（有向）萬維網(wǎng)上的網(wǎng)頁之間的鏈接關(guān)系論文之間的引用關(guān)系…第13頁/共22頁網(wǎng)絡(luò)數(shù)據(jù)的計(jì)算機(jī)表示鄰接矩陣（adjacencymatrix）相鄰節(jié)點(diǎn)列表關(guān)聯(lián)矩陣（incidencematrix）邊序列相鄰節(jié)點(diǎn)列表1：2,3,42：1,43：1,44：1,2,3邊序列1,21,31,42,43,4第14頁/共22頁圖的展示與分析工具現(xiàn)實(shí)應(yīng)用中，圖一般都是首先從描述節(jié)點(diǎn)和邊的數(shù)據(jù)而來根據(jù)那些數(shù)據(jù)，適當(dāng)?shù)亟o出一個(gè)“形象表示”（即畫出一個(gè)圖），常常是很有必要的；而根據(jù)那些數(shù)據(jù)，得出某些結(jié)論更是網(wǎng)絡(luò)分析所追求的目標(biāo)為此，人們開發(fā)了許多工具Pajek,UCINET,NetMiner,MultiNet,X-Rime，等Cuttlefish，一個(gè)簡單易用工具的例子第15頁/共22頁小結(jié)網(wǎng)絡(luò)無處不在，行行色色，對社會(huì)影響巨大網(wǎng)絡(luò)作為一門課程學(xué)習(xí)的兩個(gè)重要角度：結(jié)構(gòu)、行為；它們不同但相互影響。圖論：討論網(wǎng)絡(luò)結(jié)構(gòu)的語言作業(yè)不用交的：閱讀第1章，第2章；基于教材中的插圖2.3，以UCLA為起始節(jié)點(diǎn)（根節(jié)點(diǎn)）畫出該圖的寬度優(yōu)先搜索結(jié)果下次課前交的：上網(wǎng)搜索，找到3個(gè)不同類型的網(wǎng)絡(luò)圖及其簡單說明；第2章練習(xí)2.1第16頁/共22頁練習(xí)2.1

圖論作為有效建模工具的原因之一在于它的靈活性。許多大型系統(tǒng)都可以用圖論語言來概括其性質(zhì)，進(jìn)而系統(tǒng)地研究其影響結(jié)果。在這第一個(gè)練習(xí)中，我們利用關(guān)鍵節(jié)點(diǎn)的概念，通過一個(gè)例子來考察這個(gè)過程。

首先，第2章所講的兩節(jié)點(diǎn)間最短路徑對應(yīng)該節(jié)點(diǎn)間的最短距離。對于節(jié)點(diǎn)Y和Z，若X存在于Y和Z之間所有最短路徑上，則稱X為Y和Z間的關(guān)鍵節(jié)點(diǎn)（假定X是不同于Y或Z的節(jié)點(diǎn)）。

例如，在圖2.13中，節(jié)點(diǎn)B是節(jié)點(diǎn)A和C之間、A和D之間的關(guān)鍵節(jié)點(diǎn)（注意：B并不是節(jié)點(diǎn)D和E之間的關(guān)鍵節(jié)點(diǎn)，因?yàn)镈和E間存在兩條不同的最短路徑，而其中的一條（包含C和F）并不通過B。由此可見，B并不存在于D和E之間的所有最短路徑上）。此外，我們能看到節(jié)點(diǎn)D不是圖中任意兩個(gè)節(jié)點(diǎn)之間的關(guān)鍵節(jié)點(diǎn)。第17頁/共22頁練習(xí)2.1（續(xù)）（1）請舉一個(gè)圖例，使其滿足以下條件：該圖中每個(gè)節(jié)點(diǎn)均為至少一個(gè)節(jié)點(diǎn)對的關(guān)鍵節(jié)點(diǎn)。請就你的答案給出解釋。（2）請舉一個(gè)圖例，使其滿足以下條件：該圖中每個(gè)節(jié)點(diǎn)均為至少兩個(gè)節(jié)點(diǎn)對的關(guān)鍵節(jié)點(diǎn)。請就你的答案給出解釋。（3）請舉一個(gè)圖例，滿足以下條件：該圖中包含至少4個(gè)節(jié)點(diǎn)，并存在一個(gè)節(jié)點(diǎn)X，它是圖中所有節(jié)點(diǎn)對的關(guān)鍵節(jié)點(diǎn)（不包括含X的節(jié)點(diǎn)對）。請就你的答案給出解釋。第18頁/共22頁第19頁/共22頁第20頁/共22頁第21頁/共22頁練習(xí)2.3

當(dāng)我們試圖就一個(gè)圖的節(jié)點(diǎn)間的距離尋找一個(gè)單一的綜合衡量指標(biāo)時(shí)，有兩個(gè)自然的量值得考慮。一個(gè)是直徑，我們定義它為圖中所有兩節(jié)點(diǎn)之間距離的最大值；另一個(gè)是平均距離，我們定義它為圖中所有節(jié)點(diǎn)對距離的平均值。

在許多圖中，上述兩個(gè)量在數(shù)值上的差別不大。但在有些圖中它們則可能