談談傳遞閉包以及自己雜想

關於傳遞閉包，我想談一下自己的想法，因為覺得這是個有用的東西，前幾天上離散課中學到了傳遞閉包的概念，覺得在圖論中還是有點用處的，就仔細想了一下，沒想到還是很有收穫的，最起碼對於我對矩陣相乘有了更深的理解。之前學矩陣相乘的時候還是在線性代數中學到的，當時覺得不怎麼具體，但是知道怎麼用，直到聽說矩陣相乘和圖聯繫很大的時候也沒多想，但是通過學傳遞閉包理解了他與圖有啥聯繫。

不賣關子了，直接到正題。先說一下矩陣乘法吧，兩個矩陣相乘，得到新的矩陣的某一個元素這樣形如：<x,y>代表第 x行和第y列的元素。那麼這個元素是怎麼得到的呢，就是第一個矩陣的第x行和第二個矩陣的第y列相乘得到的！那麼為了不搞的那麼複雜我們就定義如果得到的數不為零記為1.否則就是0了。那麼這有什麼含義呢？其實都是人給的，好，我們就令<x,y>如果是1，就是代表x和y這兩個點可以到達，並且是從x到y。那麼矩陣相乘的時候就有意思了，可以看出相乘的時候第一個矩陣的元素<x1,y1>,x1是不是變的，同理第二個矩陣的元素的y2是不變的。那麼我們就可以得到，最後如果得到的結果為1，即<x1,y2>為1。那麼<x1,y2>就是可到達的，並且是從x1到y2。

到這裡我想對於傳遞背包的理解就有一大半了。那麼傳遞閉包是什麼東西呢？就是形如一個集合，如果元素<x,y>、<y,z>在集合里，那麼元素<x,z>也在集合里。放到圖裡就是說如果點x到y可到達，那麼x和y就有一條邊相連。放到矩陣里就是<x,y>是1。那麼這個集合本身就是一個傳遞閉包。如果這個集合不滿足這個性質呢？那麼我們就要求他的傳遞閉包，讓他變成一個「完整」的圖。怎麼求，一種方法就是用集合的複合來做，這是在離散課本上學到的，比較麻煩，但是考試會用到，呵呵。另一種方法用於編程，叫做warshall演算法，可以用來解題，對於一個搞圖論的人來說可以看看。在這裡不多說。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！