柯特斯圖

柯特斯圖(Coates graph)是一種特殊的圖，它是弧帶權的有向圖，如流圖，對於n階方陣A=(a_ij)，如下構造的n階帶權有向圖G(A)稱為與A關聯的柯特斯圖，圖G(A)的頂點分別標記為1，2，…，n，若a_ij≠0，則連一條從i到j權為a_ij的弧，方陣與柯特斯圖之間一一對應，可以用柯特斯圖G(A)解線性方程組AX=B。

基本介紹

• 中文名：柯特斯圖
• 外文名：Coates graph
• 所屬學科：數學
• 所屬問題：組合學(圖與超圖)
• 簡介：是弧帶權的有向圖

基本介紹

矩陣

可用一個n頂點的圖表示，即對於非零元素 可以從 引一有向邊到 點，令它的權為，如圖1所示。

圖1

這樣一n階矩陣對應一n個頂點的帶權的有向圖，叫做柯特斯(Coates)圖。例如

對應一有向圖2。

圖2

相關分析

由上所述，有些線性代數的問題便化為圖論的問題了，比如一非強連通的圖G，它的鄰接矩陣為 ，則適當地編排頂點的次序使得頂點 形成一強連通部分，則存在一置換矩陣P使得

對於矩陣 ，若存在n×n的置換矩陣P使得

則稱矩陣A是可化約的；否則是不可化約的。

若 是可化約的，則方程組 可分解為

即

其中

不難證明：矩陣 為不可化約矩陣的充要條件是它所對應的圖是強連通的，只要證明對於任意兩個不同的i、j， 。