（基礎(chǔ)數(shù)學(xué)專業(yè)論文）fuzzy關(guān)系的分解及其計算復(fù)雜性的研究.pdf

f u z z y 關(guān)系的分解及其計算復(fù)雜性的研究 基礎(chǔ)數(shù)學(xué)專業(yè) 研究生楊雁指導(dǎo)教師王學(xué)平 博士教授 論文摘要 本文在f o 1 1 格上對f u z z y 關(guān)系的一系列分解問題及其計算復(fù)雜性問題作 了深入探討 研究了布爾矩陣可實(shí)現(xiàn)問題與色數(shù)問題的關(guān)系 討論了n 元集上傳 遞關(guān)系個數(shù)的計算問題 首先討論了f u z z y 關(guān)系的q 分解問題 給出了f u z z y 關(guān)系 可o t 分解的兩個充要條件 構(gòu)造了可口分解f u z z y 關(guān)系的q 分解解集 證明了可q 分 解的f u z z y 關(guān)系是收斂的并給出了計算其收斂指數(shù)的算法 然后討論了f u z z y 關(guān)系 的o 廣義分解問題和f u z z y 矩 陣的廣義分解問題 證明了計算f u z z y 關(guān)系的o 廣義容 度及計算f u z z y 矩陣的s c h e i n 秩都是 n p 一完全問題 其次討論了布爾矩陣可實(shí) 現(xiàn)問題與色數(shù)問題的關(guān)系 證明了簡單圖的鄰接矩陣的對偶陣是可實(shí)現(xiàn)的 且其容 度就是簡單圖的色數(shù)的一個上界 最后討論了開問題 計算佗元集合上傳遞關(guān)系 的個數(shù) 構(gòu)造出了一類特殊的傳遞關(guān)系 并由這類特殊的傳遞關(guān)系構(gòu)造出了其它 所有的傳遞關(guān)系 進(jìn)一步證明了 蹙 一c 5 是佗元集合上傳遞關(guān)系個數(shù)的一個上 界 其中i i 佗 n c 童 禮一忌 1 關(guān)鍵i a o 1 格 f u z z y 關(guān)系 a 分解 解集 收斂指數(shù) 算法 q 廣義分解 o 廣義容度 f u z z y 矩陣 s c h e i n 秩 可實(shí)現(xiàn)f u z z y 矩陣 容度 布爾矩陣 色數(shù)問 題 n p 一完全問題 傳遞關(guān)系 第i 頁 共7 4 頁 t h es t u d yo ft h ed e c o m p o t i o np r o b l e m so ff u z z y r e l a t i o n sa n dt h e i rc o m p u t a t i o n a lc o m p l e x i t y m a j o r b a s i cm a t h e m a t i c s w r i t e r y a n g 徹s u p e r v i s o r w a n gx u e p j n g a b s t r a c t i nt h i sp a p e r s o m ed e c o m p o s i t i o np r o b l e m so ff u z z yr e l a t i o n sa n d t h e i rc o m p u t a t i o n a lc o m p l e x i t ya l es t u d i e do nf 0 1 1 a tf i r s t a d e c o m p o s i t i o n p r o b l e mo ff u z z yt e l a t i o n si sd i s c u s s e d t w on e c e s s a x ya n ds u f f i c i e n tc o n d i t i o n s t h a taf u z z yr e l a t i o nri sn d e c o m p o s a b l ea r eg i v e n a n dt h es o l u t i o ns e t o faa n dbw i t ha b ri so b t a i n e d t h e nt h ec o n v e r g e n c eo ft h e a d e c o m p o s a b l ef u z z yr e l a t i o ni si n v e s t i g a t e da n da na l g o r i t h mi ss h o w nt o c a l c l l l a t et h ec o n v e r g e n c ee x p o n e n tf o rag i v e no d e c o m p o s a b l ef l l z z yr e l a t i o n s e c o n d l y t h eg e n e r a la d e c o m p o s i t i o np r o b l e mo ff u z z yr d a t i o n sa n dt h e g e n e r a ld e c o m p o s i t i o np r o b l e mo ff u z z ym a t r i c e sa r ei n v e s t i g a t e d w jp r o v e t h a tc a l c u l a t i n gt h eg e n e r a la c o n t e n to faf u z z yr e l a t i o na n dc a l c u l a t i n gt h e s c h e i nr a n ko faf u z z ym a t r i xa r en p c o m p l e t ep r o b l e m s t h i r d l v t h er e l a t i o n s b e t w e e nr e a l i z a b l eb o o l a n nm a t r i c e sa n dt h ec h r o m a t i cn u m b e ro fg r a p h sa r e l s t u d i e d ep r o v et h a tt h ed u a lm a t r i xo fa d j a c e n c ym a t r i xo fas i m p l eg r a p h i sr e a l i z a b l e a n di t sc o n t e n ti sau p p e rb o u n df o rt h ec h r o m a t i cn u m b e ro f t h es a l t l e g r a p h f i n a l l v t h eo p e np r o b l e m c o u t i n gt r a n s i t i v er e l a t i o n s o naf i n i t en e l e m e n ts e t i si n v e s t i g a t e d as p e c i a lt y p eo ft r a n s i t i v e t e l a t i o n sa r ec o n s t r u c t e d t h e nw eu s et h e s es p e c i a lo n e st oo b t a i nt h eo t h e r s a n dw ep r o v et h a t 譬1i ii sau p p e rb o u n do ft h e i rn u m b e r w h e r e i i n f 2 曉 n k 1 l l v a v 蓽 s u p v i n f a 0 u n o i q i o o f q l o n 厶 a b xxy f x f x y 三n m 君是臺參纛 a t f a i l g l 部分符號說明 格 對每一個 不 屬于 大于 小于 大于或等于 小于或等于 上確界 下確界 空集 集合的并 集合的交 s u p i n f 合成算子 q 為無限集 包括可數(shù)無限集和不可數(shù)無限集 q 為有限集 自然數(shù)集 從1 到n 的所有自然數(shù)構(gòu)成的集合 由屬于集合a 而不屬于集合b 的元所構(gòu)成的集合 x 與y 的笛卡爾集 x 上的f u z z y 集 xxy 上的f u z z y 關(guān)系 格l 上的nxm 階f u z z y 矩陣之集 取值于格l 的n m 階f u z z y 矩陣 矩陣a 的轉(zhuǎn)置 集合g 中元素的個數(shù) 第v 頁 共7 4 頁 引言 關(guān)系方程是以關(guān)系為研究對象的一個數(shù)學(xué)分支 歷史悠久 最早可追溯到 運(yùn)籌學(xué)f 3 4 它在布爾變量的處理 3 8 及數(shù)字線路 2 8 的研究等方面有著廣泛的 應(yīng)用 但是 傳統(tǒng)的關(guān)系方程并不能解決一些實(shí)際問題如醫(yī)療診斷 知識庫系 統(tǒng)等中的模糊現(xiàn)象 因此 為了彌補(bǔ)這一缺陷 1 9 7 6 年 法國學(xué)者s a n c h e z 3 9 首先 提出 s u p i n 恰成f u z z y 關(guān)系方程的概念 從而開始 f u z z y 關(guān)系方程的研究 有 關(guān)s u p i n f 合成f u z z y 關(guān)系方程的研究工作可參見f 3 1 3 1 4 2 0 2 6 3 2 4 2 4 3 4 9 5 2 1 9 8 5 年 d in o l a 等f 1 2 1 發(fā)現(xiàn)用i n f 1 型合成算子去進(jìn)行f u z z y 關(guān)系的計算 或推理規(guī)則的合成效果更好 并提出 j i n f q 合成f u z z y 關(guān)系方程的研究 現(xiàn) 有關(guān)于i n f c y 合成f u z z y 關(guān)系方程的研究工作主要集中在兩種類型的i n f c y 合 成f u z z y 關(guān)系方程上 第一種 已知f u z z y 集a f x 和f u z z y 關(guān)系r f x y 求解f u z z y 集b f y 使a r o l b 第二種 已知f u z z y 集a f x 和b f y 求解f u z z y 關(guān)系ref xx 使b a q 兄 1 9 8 9 年 d in o l a 等 1 3 構(gòu) 造出了這兩類方程的最小解 并證明了方程有解的一個充要條件是方程 有最小解 之后 為了給出方程的整個解集 很多研究者又致力于構(gòu)造方 程的極大解的研究 2 9 1 本文則在 o 1 格上討論了另外兩種類型的i n f c 合 成f u z z y 關(guān)系方程 第一種 已知f u z z y 關(guān)系r f x xy 求解兩個f u z z y 集a f x 和b f y 使r a q b 若此方程有解 我們就稱r 是可o t 分解的 第二 種 已知f u z z y 關(guān)系r f x y 求解兩個f u z z y 關(guān)系a f x z 和b f z xy 使r a q b 若此方程有解 我們就稱r 是可o t 廣義分解的 本文第一 章討論 f u z z y 關(guān)系的a 分解問題 首先給出t f u z z y 關(guān)系可口分解的兩個充要條 件 然后刻畫了可o t 分解f u z z y 關(guān)系的o t 分解解集 即構(gòu)造出了方程的整個解集 最后證明了可q 分解的f u z z y 關(guān)系是收斂的并給出了一種計算其收斂指數(shù)的算 法 本文第二章討論 f u z z y 關(guān)系的q 廣義分解問題 首先證明了任一n z z y 關(guān) 系r 都是可o l 廣義分解的 然后給出了一種算法來構(gòu)造a 和b 使r a o r b 最 后證明了計算o l 廣義容度p r 其中 p r r a i n izi a q b r 是一個 第1 頁 共7 4 頁 引言 n p 一完全問題 眾所周知 從組合問題中提煉出來的布爾矩陣的平方根問題一直懸 而未決f 2 5 1 具體說來既沒有一個一般的標(biāo)準(zhǔn)去判別給定的布爾矩陣是 否有平方根 也沒有一種在有平方根的情況下能很快找到給定布爾矩陣 平方根的方法 1 9 8 5 年 d in o l a 等 1 0 1 1 進(jìn)一步研究j f u z z y 矩陣的平方根 問題 利用構(gòu)造矩陣的方法給出了一種判斷f u z z y 矩陣是否有平方根的算 法 并對有平方根的f u z z y 矩陣的平方根進(jìn)行了完整的刻畫 在此基礎(chǔ)之 上 1 9 9 3 年 v r b a 4 2 1 提出 y f u z z y 關(guān)系的廣義分解問題 對于已知的f u z z y 關(guān) 系r f xxy 問是否存在兩個f u z z y 關(guān)系a f x z 和b f z y 使r aob 記p n m i n z i r aob a f x z b f z y 稱為r 的廣義容度 而批ef x y r 總是可廣義分解的 且p r 就是尉拘s c h e i n 秩f 4 4 因此 對f u z z y 關(guān)系廣義分解的研究主要是求 解j d r 和r 的一個廣義分解 a b 使a 為i x i p r 階f u z z y 矩陣且b 為p r l y i 階矩陣 對此 v r b a 4 2 只是用截矩陣技術(shù)給出了進(jìn)行廣義分解時應(yīng)遵守 的幾條規(guī)則 1 9 8 4 年 王鴻緒和賀仲雄 4 4 提出了一種分層解法 其計算量至少 為 1 2 i l x i i y i 2 2 2 1 剮y i b n 2 k r i x i y f 2 0 0 1 年 王學(xué)平 4 8 1 j 用構(gòu) 造矩陣的方法給出了一種算法 其計算量為曬 r 吲m 總的來說 現(xiàn)有的算法 都不是多項(xiàng)式次的 因此 一個值得關(guān)注的問題就是 計算p r 能否用一個多 項(xiàng)式次的算法來實(shí)現(xiàn) 它是否是一個n p 完全問題 事實(shí)上 f u z z y 關(guān)系的廣 義分解問題和f u z z y 關(guān)系的交分解問題是緊密相關(guān)的 1 9 8 5 年 d in o l a 等 9 在 完備格上討論了f u z z y 關(guān)系的交分解問題 給出 j f u z z y 關(guān)系可交分解的一個 充要條件 并構(gòu)造出了可交分解的f u z z y 關(guān)系的最小交分解 本文第三章首先 在f 0 1 1 格上刻畫了可交分解f u z z y 關(guān)系的交分解解集 然后從f u z z y 關(guān)系的廣義 分解問題和f u z z y 關(guān)系的交分解問題之間的關(guān)系出發(fā) 給出了一個求解f u z z y 關(guān) 系的廣義分解的算法 最后從f u z z y 關(guān)系廣義分解的角度來討論f u z z y 矩陣 的s c h e i n 秩 指出f u z z y 矩陣的s c h e i n 秩等于由它生成的一個簡單圖的色數(shù) 從 而證明了計算f u z z y 矩陣的s c h e i n 秩是一個 n p 一完全問題 1 9 6 8 年 j b k e l l y 2 2 首先在實(shí)數(shù)域上討論了0 1 矩陣的可實(shí)現(xiàn)問題 并 指出0 1 矩陣的可實(shí)現(xiàn)問題在組合問題上有著良好的應(yīng)用前景 而可實(shí)現(xiàn) c h r i s t i n y a n y y h h o t m a i l c o r n 第2 頁 共7 4 頁 畢業(yè)論文 引言 矩陣的容度更是一個重要的數(shù)值特征 1 9 8 2 年 劉旺金 3 0 將這一問題推廣 到 f u z z y 集上 研究 f u z z y 矩陣的可實(shí)現(xiàn)問題 已知4 為取值于 o 1 1 的n n 階f u z z y 矩陣 問是否存在取值于 o 1 的仡 p v 階 f u z z y 矩陣b 使a bob t 記r a m i 禮 p a bob t b 為禮 p 階f u z z y 矩陣 稱r a 為4 的容度 1 9 8 4 年 王銘新 4 6 1 給出了f u z z y 矩陣可實(shí)現(xiàn)的充要條件 眾所周知 研究可實(shí) 現(xiàn)矩陣的核心問題是計算可實(shí)現(xiàn)矩陣的容度及容度的應(yīng)用 為此 研究者們 對可實(shí)現(xiàn)f u z z y 矩陣容度的上 下界作了較為精確的估計 3 1 4 5 4 6 5 4 5 6 1 9 9 9 年 王學(xué)平f 4 7 1 給出了計算可實(shí)現(xiàn)f u z z y 矩陣容度的一種算法 由于布爾矩 陣是f u z z y 矩陣的特殊形式 因此 計算可實(shí)現(xiàn)f u z z y 矩陣的容度的算法同樣適 合計算可實(shí)現(xiàn)布爾矩陣的容度 另一方面 由于布爾矩陣和圖論的密切聯(lián)系 可 實(shí)現(xiàn)布爾矩陣也有著重要的圖論意義 所謂色數(shù)問題是指 給已知簡單圖的所 有頂點(diǎn)著色 要求相鄰的兩個頂點(diǎn)顏色不一樣 問最少需要幾種顏色 這一問 題一經(jīng)提出便受到廣泛關(guān)注 并廣泛應(yīng)用到許多實(shí)際問題的解決中 例如 時 間表問題f 2 6 5 3 和化學(xué)物質(zhì)分類儲藏問題 6 等 研究者們長期致力于從圖 本身結(jié)構(gòu)出發(fā) 對其色數(shù)上 下界進(jìn)行估計 1 9 3 3 4 0 5 3 和給出計算色數(shù)的 精確算法 這些精確算法僅適合較簡單的圖 2 6 并不斷加以改良 2 1 眾所周 知 色數(shù)問題 是一個 n p 一完全問題 故要精確計算色數(shù)或獲得色數(shù)的一 個上界是十分困難的 因此 也有一些研究者們提出了若干探試法 h e u r i s t i c s m e t h o d 去獲得圖的色數(shù)的上界 2 1 1 本文第四章討論了布爾矩陣的可實(shí)現(xiàn)問題 和簡單圖的色數(shù)問題之間的關(guān)系 首先給出了布爾矩陣可實(shí)現(xiàn)的一些充要條件 討論了可實(shí)現(xiàn)布爾矩陣的性質(zhì) 其次證明了簡單圖的鄰接矩陣的對偶陣是可實(shí) 現(xiàn)的 且其容度就是簡單圖的色數(shù)的一個上界 最后指出該上界可用王學(xué)平 4 7 所給出的計算可實(shí)現(xiàn)f u z z y 矩陣的容度的算法來實(shí)現(xiàn) 也即給出了簡單圖色數(shù) 的上界的一個算法 1 9 8 2 年 k i m 在 2 5 1 一書中提出了開問題 計算n 元集合上傳遞關(guān)系的個 數(shù) 之后雖然也有一些學(xué)者對這一問題進(jìn)行了研究 但總的來說 現(xiàn)有的 工作很少單獨(dú)地把傳遞關(guān)系作為研究對象來刻畫它的性質(zhì)和結(jié)構(gòu) 1 9 7 9 年 k i m 和r u s h 2 3 證明了n 元集合上的傳遞關(guān)系的個數(shù)漸近地等于偏序關(guān)系個 數(shù)的2 n 倍 1 9 9 7 年 k l a s k a 2 7 1 證明了偏序關(guān)系和傳遞關(guān)系之間存在著一個 c h r i s t i n y a n y y h h o t m a i l c o r n 第3 y i 共7 4 頁畢業(yè)論文 引言 一一對應(yīng)關(guān)系 并給出了它們個數(shù)之間的遞歸公式 另一方面 也有許多算 法 1 5 7 8 1 8 3 5 3 7 1 被用來枚舉偏序關(guān)系的個數(shù) 顯然 傳遞關(guān)系的個 數(shù)也可以通過這些算法 再結(jié)合 2 7 中的遞歸公式求得 但迄今為止 最好 的結(jié)果也只是計算到禮 1 6 本文第五章首先討論了傳遞關(guān)系對應(yīng)的布爾 矩陣的結(jié)構(gòu)特征 然后構(gòu)造出了一類特殊的傳遞關(guān)系 并通過其構(gòu)造出了所 有的傳遞關(guān)系 最后指出n 元集合上傳遞關(guān)系個數(shù)的上界為 爛 j i 其 中l(wèi) n i n 乏1 磷 他一尼 1 c h r i s t i n y a n y y h h o t m a i l c o r n 第4 頁 共7 4 頁 畢業(yè)論文 第一章 a 分解f u z z y 關(guān)系的a 分解解集及收斂指數(shù) 本章將在 0 1 格上討論f u z z y 關(guān)系的a 分解問題 即對給定的f u z z y 關(guān)系r f x y 討論是否存在兩個f u z z y 集a f x 辛1 1 b f 使兄一a a b 首 先給出f u z z y 關(guān)系可口分解的兩個充要條件 然后對可n 分解的f u z z y 關(guān)系 求解 出其所有的 分解解集 最后證明可恥分解的f 1 1 z z y 關(guān)系收斂并給出一種計算其 收斂指數(shù)的算法 1 1 預(yù)備 首先回憶一些基本概念 3 9 稱映射a x 一 0 1 共j x1 的n z z y 集 記f x a a x 一 0 1 稱映射兄 xx y 一 0 1 為x y 上的f u z z y 關(guān) 系 記f x y 一 r r x y 一 0 1 定義1 1 1 3 9 1 設(shè)n b 0 1 定義二元算子 0 1 x 0 1 一 0 1 滿足 a a b 等 值得注意的是 定義1 1 1 所定義的q 算子 實(shí)際上就是g o d e l 蘊(yùn)含算子 1 6 17 定義1 1 2 3 9 1 稱f i l z z y 集a f x 包含f i l z z y 集b f y 記作a b 當(dāng) 且僅當(dāng) x a z b z 進(jìn)一步 稱以與b 相等 記作a b 當(dāng)且僅 當(dāng)a b 且b a 即v z x a x 日 z 定義1 1 3f 3 9 設(shè)q f x z t f z y 定義q 和t 的s 叩一i n 合 成關(guān)系r q0 t f x y 滿足 v z y x y r x q o t x 可 v q z z a t z z e z 第5 頁 共7 4 頁 第一章可q 分解f u z z y 關(guān)系的q 分解解集及收斂指數(shù) 定義1 1 4 設(shè)r f x y 如果存在兩個f u z z y 集a f x 和b f y 使r a a b 即滿足 v x y x y r x y a a b x y a x a b y 則稱r 是可q 分解的 并稱 a b 是r 的一個q 分解 本章所討論的f u z z y 集和f u z z y 關(guān)系均定義在 o 1 格上 眾所周知 f u z z y 關(guān) 系可用f u z z y 矩陣來表示 故對于給定的r f x y 既表示x y 上的一 個f u z z y 關(guān)系 也表示x y 上的一個f u z z y 矩陣 1 2 f u z z y 關(guān)系可q 分解的兩個充要條件 本節(jié)將給出f u z z y 關(guān)系可q 分解的兩個充要條件 設(shè)r f x y r x 可 表示r 的第可列 x y 為有限或無限集 定理1 2 1 若兄是可q 分解的 則v y y n x 可 的元素取值或?yàn)? 或?yàn)樾?于1 的常數(shù) 證明若r 是可口分解的 則存在a f x b f y 使r a a b v y y 考慮n x y 的元素取值 則由定義1 1 1 有v x x 腳 裂 鄔 顯然 若兄 y 1 則兄 y b y 1 m 記歷 r f x y v y n x 秒 的元素取值或?yàn)? 或?yàn)樾?于1 的常數(shù) 玩 咒 f x y r 是可q 分解的 由定理1 2 1 易知 玩 勿 設(shè)r 劈 v x x v y y 令a y z x r x y 1 h x 可 y n x y 1 設(shè)r 紡 v y y 若a y d 則比 g r x y 1 且由定 理1 2 1 有r x y a 掣 因此 可定義b f y 如下 v y y 刪 傺裂 舢 c h r i s t i n y a n y y h h o t m a i l c o r n 第6 頁 共7 4 頁畢業(yè)論文 第一章可q 分解f i l z z y 關(guān)系的a 分解解集及收斂指數(shù) 進(jìn)一步 定義a f x 如下 v z x z 八 兄 z y o r b 可 定理1 2 2 若r 留 則比 x a a 可 日扛 b 弋秒l 蕓鬻 眈 證明v 疊 x 若y 日 z 則r z y 1 否則 r x y b 可 1 從 而 a z 陋 z y o c b 秒 人 e l l z r z y o r b 可 八掣隹日 z r z y o r b y e l l z 1 a b 秒 入 c h z i s y a b 可 八掣 日 b y 八 八可隹日 霉 1 因此 若日 z 仍 則有 z 1 否則 a z a 日 b 可 定理1 2 3r 是可0 1 分解的充要條件是r a o l b 進(jìn)一步 a b 是r 的 最大0 1 分解 證明充分性 若冗是可口分解的 則存在a f b f y 使r a q b 即v z y x y r x y a q b 可 下面首先證明b b 且as a i v y y 若c y 仍 則存在z g y 使r x y 1 且r z y b y 故由b 的構(gòu)造有b 白 a r z y b 白 若a y 0 則由b 的構(gòu)造 有b 1 b 秒 因此 v y y b b i i 比 x 若y 日 則兄 z y l j a x b 白 由定理1 2 2 易 知 若h x d 則a z 1 a z 否則 a z a y e h z b 白 a y h z b 秒 a y e h 功4 a z 因此 比 x a a 接下來 證明v 黝 y o xxy r z o y o a x o a b 珈 下面分兩種情 況討論 c h r i s t i n y a n y y h h o t m a i l c o m 第7 頁 共7 4 頁畢業(yè)論文 第一章可q 分解f i l z z y 關(guān)系的a 分解解集及收斂指數(shù) 1 若h x o 仍 則a 黝 1 且冗 銣 y o 1 故r x o y o b v o 另一 方面 由b 的構(gòu)造有b v o r x o y o 1 因此 r x o y o a x o o r b y o b y o b y o l o l b v o a x o a b 珈 2 若h x o 仍 貝u 以 z o a v e r t b 可 故a z o q b v o a v e r t z b 4 qb 珈 若y o 日 z o 貝 u r z o y o 1 目 a v e h b 白 b 珈 故a 跏 q b v o 1 r x o 珈 若y o 譬h x o 貝q r z o y o 1 由定 義1 1 1 有b v o a x o 故r x o y o b y o b 珈 另一面 v y 日 z o 有r x o y 1 a x o b 秒 b y 且j e i v o b y o a x o b 從而b v o a y e 日 b 秒 a z o 故a z o a b v o b y o b y o r x o v o 因此 r x o y o a z o o e b 珈 綜合 1 和 2 知 v x o y o x y r x o y o a z o o b 珈 即冗 a 4 0 e b 必要性 由定義1 1 4 顯然成立j 例1 2 1 設(shè)x x l x 2 x 3 y v i y 2 珧 a f x b f y 其中 a 0 0 0 2 o 4 b 0 1 0 3 1 o 則有 1 01 0 1n r a q 日2 i j n u1 u jm ui 顯然 r 歷且a o 1 0 3 1 0 b 0 1 0 3 1 0 易驗(yàn)證 r a a b 且a a b b 定理1 2 4 冗是可q 分解的充要條件是冗滿足 i r 勿 i i v x o y o xxy 若r x o y o l j h x o 仍 貝j j r x o y o a z o 證明充分性 i 由定理1 2 王有 r 紡 i i v x o y o x y 若r x o y o l j h x 0 函 則由b 的構(gòu)造有b 珈 兄 鉑 珈 因?yàn)閞 是 可o l 分解的 故由定理1 2 2 和定理1 2 3 有 r x o y o a z o o e b v o c h r i s t i n y a n y y h h o t m a i l c o r n第8 頁 共7 4 頁畢業(yè)論文 第一章可q 分解f u z z y 關(guān)系的q 分解解集及收斂指數(shù) a y e h x 曰4 y q b y o a y e h b 可 q r z o y o 1 因此 r x o y o a y e h b 可 a 跏 必要性 因?yàn)閞 砑 故可構(gòu)造a b v x o y o x y 下面分兩種情況 討論 1 若h x o 仍 則由定理1 2 2 有a 1 進(jìn)一步 由b 4 的構(gòu)造可 得b y o r x o y o 1 因此 a z o a b l a b y o b y o r x o y o 2 若h x o 仍 則由定理1 2 2 有a 跏 a y e h 知 b 可 若y o h x o 貝j j r x o y o l j f l b y o a y e h j e 7 可 a z o 故a 4 x o a b y o 1 r x o 珈 若y o 碧日 鉑 則兄 z o y o b y o 1 此時 由條件 i i b y o n x o y o a z o 因此 a x o a b y o b y o r x o 珈 綜合 1 和 2 可得 v x o y o xxy r x o y o a x o a b 珈 因此 r 是可0 1 分解的 注1 2 1 設(shè)r 刀 由定理1 2 4 易知 v x x 若g x d 或h y 則冗是可q 分解的 r 1 0 0 2 1 0 但r x l y 2 0 2 a y e h 正 b 可 o 1 因此 r 不是可q 分解的 推論1 2 1 設(shè)冗是可口分解的 璣 y 2 y 且z x 若b y 1 b 沈 則r z y 2 1 蘊(yùn)含r z y 1 1 進(jìn)一步 若b y 1 b 沈 則冗 x y i n x 耽 c h r i s t i n y a n y y h h o t m a i l c o i l l 第9 頁 共7 4 頁 畢業(yè)論文 第一章可n 分解f i i l z z y 關(guān)系的q 分解解集及收斂指數(shù) 證明比 x 若兄 z y 2 1 即沈 日 則一定有兄 z y 1 1 否則 假設(shè)r x y 1 1 則由定理1 2 4 有b y 1 r x y 1 a o h z b 可 b 耽 即b y 1 b 4 耽 矛盾 1 3 可q 分解f u z z y 關(guān)系的a 分解解集 本節(jié)將給出可o t 分解f u z z y 關(guān)系r 的q 分解解集 令夕 b oa a b r 設(shè)r f x x y x y 為有限或無限集 若r 是可q 分解的 則令k 可 y b 可 1 j 王x 1 z x r z y 1 定理1 3 1 若存在a f x b f y 使r a q b 則v y m b y b 可 證明v y y 1 由b 的構(gòu)造知 b 可 l j t g y 仍 因此 存在z g 秒 使兄 z y b y b u 則a o x v 掣隹日 z b 可 a z 否則 a o x v 可岳日 z j e 7 耖 a z 證明充分性 若存在b f y 使r a a b 則由定理1 3 2 可得r a a b i 若z x 1 則由定理1 2 3 有 y r x y a x a b 可 c h r i s t i n y a n y y h h o t m a i l c o m 第1 0 頁 共7 4 頁畢業(yè)論文 第一章可q 分解f u z z y 系的q 分解解集及收斂指數(shù) a z q b 秒 1 故a x a z sb 秒 因此 a x f 0 a z i i 若z 芒x 1 則由日 z 的定義有 h x y 且v y 譬日 z r x y 1 因 此 v y 譬日 z b 可 b u 則顯然有a x f v c h z b 白 a z 若存在y o 隹日 z 使v c h z b 可 b 珈 則一定有a x v 掣c h z b 可 否 則 a x v c h z j e 7 b 珈 則r y o l 即珈 日 矛盾 因此 a x v c h z b 可 a z 綜合 i 和 i i 可得 a m 必要性 v a m 比 x i 若z x i 則由定理1 2 3 v y y r x y a z 乜b 1 故a b 可 又因?yàn)閍 x 0 a 所 以a x b 可 因此 a x a b y 1 r x 可 i i 若z 岳x 1 貝l j v 如 y r x y o 1 或n x y o 1 若r x y o 1 則珈 日 z 且由定理1 2 2 有 a 0 八可 日 b 可 b 珈 此時 由 2 知v 壁日扛 b y a z a b 珈 故a x a b y o 1 r x 珈 若r x y o b 跏 故b y o r z y o b 4 u 則由 2 得a z a x v 晦日 z b 可 b 珈 即 有a x a b y o r x 珈 否則 存在u 隹日 使v 掣c h b 秒 b 4 讓 此時 由 2 得4 0 a x v c h b b 珈 故有a x o r b y o n x 珈 由 i 和 i i 可得 b f y j 王 v a m r a o l b 注1 3 1 在定理1 3 3 中 由m 的構(gòu)造可知 若x 是一個有限集 則比岳x 1 a x v y c h z b 可 a 比隹x 1 a x v y c h z b 可 a z 的必要條 件是x 是無限集 定理1 3 4 若a f x 且r a a b 定義b f y 滿足 v y y i 若y y 1 則b 可 b 可 i i 若y 隹h 貝0 b 秒 v z x a x 1 則有r a a b 證明若y y 1 貝j j b y b y 故v z x r x y a x a b 4 y a x a b y 若秒譬m 則由b 可 v z x a z 1 有a z q b 可 1 又因?yàn)?譬 c h r i s t i n y a n y y h h o t m a i l c o r n 第1 1 頁 共7 4 頁畢業(yè)論文 第一章可口分解n l z z y 關(guān)系的a 分解解集及收斂指數(shù) m 故b 可 1 即v 童 x r x y 1 從而 a z q b y l r x 因 此 r a a b j 對于給定的4 m 由定理1 3 4 總可以得到一系列b f y 使r a a b 記這些b f 廣 組成的集合為m a 此時 由定理1 3 2 1 3 4 易得下面的定理 成立 定理1 3 5 設(shè)r 是可q 分解的 a m 則v b m a r a a b 且必a 中存在 一個最小的元素瘍滿足 v y y 鼬 b 協(xié) 因此 由定理1 3 3 可求得 m a f x a x 2 由定理1 3 4 可求得 v a m 0 主 比 烈 z 2 a 戤 蕓 1 m m a b f y b y 1 v 蠔x a x 1 魄 y y 1 b 璣 b 執(zhí) 因此 夕 a b a m b 心 1 4 可口分解f u z z y 關(guān)系的收斂指數(shù) 討論和求解f u z z y 矩陣在s u p i n f 合成算子下的收斂指數(shù)和周期一直是許 多研究者非常關(guān)注的問題 4 本節(jié)將證明可q 分解的f u z z y 矩陣收斂 并給出一 個求解其收斂指數(shù)的算法 設(shè)r f x x a x 是有限集 定義1 4 1 4 4 1 設(shè)r f xxx v k n 定義r 1 r r 七 1 r 七or 定義1 4 2 4 4 1 f u z z y 關(guān)系r f xxx 收斂當(dāng)且僅當(dāng)存在正整 數(shù)k 使兄七 1 r 鳧 其中 使r 七 1 r 七成立的最小正整數(shù)k 稱為冗的收斂指 數(shù) 記作r 冗 c h r i s t i n y a n y y h h o t m a i l c o r n 第1 3 頁 共7 4 頁 畢業(yè)論文 第一章可q 分解f u z z y 關(guān)系的a 分解解集及收斂指數(shù) 定義1 4 3 設(shè)r f xxx y y r 的第可列r x 可 收斂當(dāng)且僅當(dāng)存在 正整數(shù)k 使肼 1 x y r 詹 x 可 其中 使r 1 x y r 七 x 可 成立的最小 正整數(shù)k 稱為r x y e j 收斂指數(shù) 記作7 可 設(shè)r 玩 i f x 令i y z x r z y 1 x g 秒 定理1 4 1 設(shè)尼是可q 分解的且可1 y 2 x 若b y i b 沈 貝 l j i y 1 j 耽 證明比 j 耽 r x y 2 1 因?yàn)閎 y i b 4 耽 故由推 論1 2 1 知r x y 1 l 即z 可1 因此 i y 1 2i y 2 j 推論1 4 1 設(shè)尼是可q 分解的且y 1 y 2 x 若b v 1 b 渤 則i y 1 垅 注1 4 1 推論1 4 1 的逆命題不一定成立 兄 羞 b 珈 b k 秒 則b 可 b k 可 b k n y j t i y 2j k 秒 2 2z k n 可 2d 定理1 4 3 設(shè)r 是可q 分解的且可 y 則一定存在正整蜘使b 艫 y b 觶1 矽 證明因?yàn)閤 是有限集 由注1 4 4 易得 定理1 4 4 設(shè)r 是可q 分解的且珈 y 若i y o 仍 則比 x v 石 r z z n x k 踟 c h r i s t i n y a n y y h h o t m a i l c o r n 第1 5 頁 共7 4 頁畢業(yè)論文 第一章可q 分解f u z z y 關(guān)系的a 分解解集及收斂指數(shù) 證明 因?yàn)閎 k 珈 m a x b z z 珈 故由定理1 4 1 知 v z 珈 z z k 珈 v x x 若v z x v o r x z 1 則r z z b z b k 加 n x k 珈 故v z 可 冗 z z r x k 珈 否則 若 存在z o z y o 使r x z o 1 則有z x z o 此時 一定有r x k y o 1 否則 若r x k y o 1 則有z 隹i k y o j i z o 垡j k 珈 矛盾 因此 v z 地o 兄 z z 一1 n x k 珈 定理1 4 5 設(shè)r 是可q 分解的且珈 y 若x y o 0 或b y o b k 則冗2 x y o r x v o 證明 i 若i y o 0 貝 u v x x r x y o b 珈 b k 珈 此時 一定有y o 隹x y o 否則 y o i y o 又因?yàn)閎 4 k 珈 m a x b z z j 珈 故b k 可o b 珈 矛盾 若z j k 珈 貝j j r x k y o 1 故由 1 2 有r 2 x y o 1 若z 譬j k 珈 則咒 z k y o b k 珈 由 1 2 可得 r 2 z y o b y o v v g b 珈 b 珈 又因?yàn)閥 o 隹z y o 故r 2 z y o r x y o ab 珈 b 珈 因此 r 2 z y o b y o m a x b 珈 b 4 k 珈 由 i 和 i i 可得 當(dāng)m 2 時 命題成立 i i 假設(shè)當(dāng)m p 時 命題成立 貝j j v x x r p x y o 三觚 b 珈 b k 珈 b 艫一 珈 x 否e 則i 艫 珈 下面證明當(dāng)m p 1 時 命題b 樣成立 c h r i s t i n y a n y y h h o t m a i l c o m 第1 7 頁 共7 4 頁畢業(yè)論文 第一章可口分解f u z z y 關(guān)系的a 分解解集及收斂指數(shù) 事實(shí)上 若z 隹i k p q 跏 則一定存在g 且1 v v 茌j k 一 陋 z ar p z 珈 j v z i k p 一 陋 z a1 v v c z k 一 珈 陋 z ab k 9 蜘 v z i k p 一 可 r z z v v 馨j 艫一 陋 z z ab k 口 珈 r x 艫 珈 v v 垡j 腳一z 珈 陋 z z ab k 9 m 1 4 1 若z 艫 珈 則r 艫 珈 1 故由 1 4 有屆時1 珈 1 2 若z 岳i k p y o 則由b 的定義有咒 z 艫 珈 b 艫 蜘 下面分為兩種 情況討論 a b 4 艫 蜘 b k g 珈 此時 m 1 3 和 1 4 易得 r 葉1 y o b 釅 珈 m a x b 珈 b k 珈 b 艫 珈 b b 艫 珈 b k 可 若對于某個正整 數(shù)m b k m 1 y 存在j i i k m 1 可 仍 則胛 1 x y 艫 x 秒 證明由定理1 4 6 和注1 4 4 知 v y y 艫 z y b 可 故比 x r m 1 可 v r z z ar z 可 v 兄 z z ab 可 b 可 z e x z e x 而另一面 v z x 陋 z z ab 可 r x y ab 可 b 可 因此 v x x 妒 1 z y r m z 可 即胛 1 x y 胛 x 秒 定理1 4 7 若尼黽可q 分解的 則 廠 r x 可 收斂 證明v y x 可分為兩種情況 i z y d 此時 由定理1 4 5 和定義1 4 3 知 n x 可 收斂k r y 1 i i i v o 此時 由注1 4 2 知 b k 可 存在 下面分三種情況來討論 i b b k y 由定理1 4 5 和定義1 4 3 知 r x 3 收斂a r y 1 i i b 可 b k 秒 因?yàn)閤 是有限集 由注1 4 2 和注1 4 4 可連續(xù) 得到x 的一個有限點(diǎn)列k o 秒 k 可 k 2 矽 k n 可 直i u b k 計1 可 b k b 1 此時 b b k b 艫 進(jìn)一步 由定理1 4 6 不難得至u n x y 尼件1 x y 艫 2 x 秒 因此 根 據(jù)定義1 4 3 n x 可 收斂j t r y n 1 其中 1 b k 可 因?yàn)閤 是有限集 由注1 4 2 和注1 4 4 可 連續(xù)得到x 的一個有限點(diǎn)列艫 可 k 可 k 2 可 k m k m 矽 直 至 j j k m 1 y 0 z k m 2 y 或i k 秒 i k m 1 y i k m 2 y 此時 b 秒 b k 可 b k m 可 進(jìn)一步 由推論1 4 2 和定理1 4 6 不難得到 1 x y r m x y 艫 1 x 可 因此 由定義1 4 3 r x 可 收 斂且7 可 m 其中 1 r y i x l 因此 由 i 和 i i 知 v y y n x 收斂j 事實(shí)上 設(shè)冗 f x x 若r 收斂于指數(shù)七 則r 的每一列也將收斂于指 數(shù)忌 反之 若r 的每一列都收斂 則r 亦收斂 因此 由定理 4 7 下面的結(jié)論成 立 c h r i s t i n y a n y y h h o t m a i l c o r n 第1 9 頁 共7 4 頁畢業(yè)論文 第一章可q 分解f u z z y 關(guān)系的a 分解解集及收斂指數(shù) 定理1 4 8 若r 是可q 分解的 則r 收斂且r r m a x r y y x 設(shè)兄是可o t 分解的 1 y 2 x 由推論1 2 1 有 ob y 1 b 4 渤 當(dāng) 且僅當(dāng)r x y 1 r x y 2 因此 我們可以作集合x 的一個劃分 q 1 q 2 q m 滿足下列條件 1 4 1 i 設(shè)秒1 y 2 x y 1 垅屬于同一個集合q i k 當(dāng)且僅當(dāng)b y 1 b 耽 i i q 1uq 2u uq x i i i v i j k 若i j 則qnq 0 這樣一來 我們有下面的結(jié)論成立 定理1 4 9 若兄是可q 分解的且q 1 q 2 q m 是x 的一個滿足上述條 件 1 4 1 的劃分 則v y l y 2 q i k 對于任 正整數(shù)佗 都有形 x y 1 形 x 拋 因此 對于給定的可a 分解的f u z z y 關(guān)系咒 結(jié)合定理1 4 7 的證明 以及定 理1 4 8 和1 4 9 我們可給出一個計算刷拘收斂指數(shù)r 兄 的算法如下 算法1 4 1 設(shè)q 1 q 2 q m 是x 的一個滿足條件 1 4 1 的劃分 v i k 選定q 中的元素q i 作為其代表元 s t e p1 v k 計算r 吼 s t e p2 計算r r m a x 7 吼 o i k s t e p3 停止 由定理1 4 7 的證明 以及定理1 4 8 和1 4 9 我們可給出算法1 4 1 的流程圖 見圖1 4 1 例1 4 2 設(shè)x x l x 2 x 3 x 4 x 5 x 6 r c h r i s t i n y a n y y h