1樓:老蝦米
兩個圖的頂點集合之間能夠建立一一對應的對映,對應的頂點之間保持邊的一一對應關係。
也可以通過圖的鄰接矩陣來**。一個圖的鄰接矩陣經過有限次的互換行或列的變換變成另一個圖的鄰接矩陣,則兩個圖同構。
2樓:匿名使用者
判斷子圖同構有許多比較成熟的演算法,比如agm演算法、gspan演算法、fsg演算法、esu演算法等。這些可以在網上查內到容具體的解釋。
歸根到底是要理解子圖同構的定義:
對於給定的兩個圖g = ( v, e ),g』 = ( v』, e』 ),若存在雙射f:v -> v』使對任意a, b∈v,(a, b)∈e當且僅當( f(a),f(b) )∈e』,並且(a, b)與( f(a), f(b) )有相同重數,則稱g與g』同構,記為g ≌ g』。
用通俗的話說,則是隻兩幅子圖上的節點能夠一一對應,並且節點與節點之間所連線的邊的情況也是完全一致的。
如何判斷兩個圖是否同構
3樓:小蘋果
1、兩個圖的頂點
集合之間能夠建立一一對應
的對映,對應的頂點之間保持版
邊的一一對應關係。
2、也可權以通過圖的鄰接矩陣來**.一個圖的鄰接矩陣經過有限次的互換行或列的變換變成另一個圖的鄰接矩陣,則兩個圖同構。
同構是在數學物件之間定義的一類對映,它能揭示出在這些物件的屬性或者操作之間存在的關係。若兩個數學結構之間存在同構對映,那麼這兩個結構叫做「是同構的」。
一般來說,如果忽略同構物件的屬性或操作的具體定義,單從結構上講,同構的物件是完全等價的。
4樓:數學一專家
兩個無向圖的關聯矩陣經過行或者列交換以後完全相同,那麼這兩個圖同構。
嘿嘿,給你兩個矩陣,你還看不出兩個矩陣經過行,列交換以後是不是相同嗎?
我知道的只有這麼多了,讓高人回答吧。
5樓:匿名使用者
判斷是不是同構目前沒有什麼好的辦法。。我們都是根據已知的條件判斷這兩幅圖不同夠,用排除
離散數學 如何證明兩個圖同構? 40
6樓:匿名使用者
若g與g』同構,其充要條件是:
兩個圖的結點和邊分別存在一一對應,且保持關聯關係,
特別是對有向圖還要保持邊的方向一致。
離散圖論:如何快速判斷兩個圖同構?
7樓:匿名使用者
姐姐 同構不考啊!
8樓:匿名使用者
這是個np問題,但還不清楚是否是npc問題。換句話說,就目前來看,除了一個對映一個對映地驗證,沒有其他效率更好的方法。
至於到底有沒有更快的演算法,即不能肯定也不能否定。
判斷是否是同一函式,如何判斷兩個函式是否表示同一個函式
f x 的定義域為全體非0實數 x的平方非負 而g x 的定義域為正實數 變形是可以,但變形必須是表示式有意義,是吧 如何判斷兩個函式是否表示同一個函式 給出相同的變數,分別求兩個函式的函式值。同時對兩個函式求一階導數和二階導數,看斜率和拐點是否相同。如果上述值都相同,則可認為是同一函式的兩種不同表...
什麼是語素，如何判斷語素和兩個語素
語法單bai位有大有小，最大du 的語法單位是句子，比zhi句子小的語法dao單位，依次是短內語 詞容 語素。人類的語言是有聲音 有意義的，是語音和語義的結合體，這便是語法單位基本的特點。語素是最小的語法單位，也就是最小的語音 語義結合體。語素有兩個特點 一是最小 不能再分割了 一是有意義。怎樣判斷...
如何判斷哪些社交是無用的，如何區分有效社交與無效社交？
這題我們先說，哪些社交是有意義的 1.發小 從小一起長大，這種關係不摻雜利益而開始，並且伴隨彼此上學結婚生娃，是值得珍惜的。2.同學中的好友 畢業之後見到同學都會分外親切，不管在學校中關係如何，何況在校時就是好友。有人說同學是影響成年後價值觀的很大因素，能成為好友，必然見證過彼此的成長，值得珍惜。3...