王 濤

（長(zhǎng)沙民政職業(yè)技術(shù)學(xué)院通識(shí)教育中心，湖南長(zhǎng)沙410004）

一、問(wèn)題的提出

1、用鄰接矩陣表示有向圖

如有向圖D(圖1所示)。

其A（D）（即圖1的鄰接矩陣）如下

此圖的行從左往右表示v1,v2,v3,v4,此圖的列從上往下表示v1,v2,v3,v4，矩陣中的元素aij

表示vi,鄰接到vj長(zhǎng)度是1的路徑的條數(shù)（非負(fù)整數(shù)）

如v11（第一行，第一列）表示v1到v1長(zhǎng)度為1的路徑的條數(shù)是1（一個(gè)環(huán)）

2、利用矩陣的乘法求D中長(zhǎng)度為2的路徑數(shù)

如A2=A×A矩陣中元素aij表示vi鄰接到vj長(zhǎng)度是2的路徑的條數(shù)（非負(fù)整數(shù)）

在結(jié)果矩陣中如v14=2（第一行，第四列）表示到v4長(zhǎng)度為2的路徑的條數(shù)是2。

這個(gè)2是第一個(gè)矩陣的第一行與第二個(gè)矩陣的第四列對(duì)應(yīng)元素相乘，然后相加所得

2=1 ×1 +1×0+1×1+1×0

從圖中可以觀察到這兩條路徑分別是

以此類推，因此我們可以得到定理；

矩陣AL中元素aij表示vi鄰接到vj長(zhǎng)度是L的路徑的條數(shù)（非負(fù)整數(shù)）

接下來(lái)利用初等數(shù)學(xué)中的加法原理和乘法原理證明上述定理

二、定理的證明

如上的例子中v1到v4長(zhǎng)度為2的路徑的條數(shù)可以理解為

這件事情可以分成四類方式，每類方式可以分成兩個(gè)步驟，分別是

第一類方式是v1→ v1→ v4，其中第一個(gè)步驟v1→ v1有1條路徑，第二個(gè)步驟v1→ v4有1條路徑，因此利用乘法原理可以得到第一類方式中共有路徑的條數(shù)是1×1。

第二類方式是v1→ v2→ v4，其中第一個(gè)步驟v1→ v2有1條路徑，第二個(gè)步驟v2→ v4有0條路徑，因此利用乘法原理可以得到第二類方式中共有路徑的條數(shù)是1×0。

第三類方式是v1→ v3→ v4，其中第一個(gè)步驟v1→ v3有1條路徑，第二個(gè)步驟v4→ v4有1條路徑，因此利用乘法原理可以得到第二類方式中共有路徑的條數(shù)是1×1。

第四類方式是v1→ v4→ v4，其中第一個(gè)步驟v1→ v4有1條路徑，第二個(gè)步驟v4→ v4有0條路徑，因此利用乘法原理可以得到第二類方式中共有路徑的條數(shù)是1×0。

所有最后用加法原理可得

1×1 +1 ×0+1×1+1×0=2

以此類推，可以證明

AL=AL-1A

矩陣AL中的元素aij表示vi鄰接vj到長(zhǎng)度是L的路徑的條數(shù)（非負(fù)整數(shù)）。

三、結(jié)束語(yǔ)

本文利用了初等數(shù)學(xué)中的加法原理和乘法原理證明了離散數(shù)學(xué)中的一個(gè)很重要的定理，學(xué)生很容易理解。教材中有些重要定理的證明學(xué)生理解起來(lái)比較困難，教師要善于用簡(jiǎn)單的、學(xué)生容易接受的方法去重新證明，從而達(dá)到最好效果。