ریاضیات

این دو گراف یکریخت نیستند در گراف با رئوس 1234567 دو دور مثلثی وجود دارد اما در گرافABCDEFG یک دور مثلثی است بعلاوه در این گراف دور مربعی نیز دارد که در اولی نیست. 
1

1

من فکر می کنم من یک روش برای حل مشکل دارم. من می دانم که NP آن کامل است و حل آن بسیار وسوسه انگیز است. من می دانم که می توانم 99.99٪ اشتباه کنم اما می خواستم به آن ضربه بزنم. میخوام تستش کنم

2 نمودار داده شده: A، B (بدون حلقه های خودکار / بدون چند لبه)

ایده ایجاد امضای منحصر به فرد برای هر راس یا گره بر اساس لبه ها است.

1) گره ها را بر اساس درجه هر گره مرتب کنید. 2) گره را با بالاترین درجه بگیرید. در اینجا ما [A ، D ، E ، F] با درجه 3 داریم. بیایید A بگیریم و درجه آن 3 است ، بنابراین اجازه دهید شروع به ساختن یک امضا کنیم. ما آن را به عنوان "C" نشان می دهیم و اکنون گره های adj را با حداکثر درجه D و درجه 3 می گیریم. اکنون امضا "CC" است. بعد گره بالاترین درجه بعدی را می گیریم که B یا C باشد و هر کدام دارای درجه 2 هستند. بنابراین اکنون امضا "CCBB" است.

3) مجموعه های بالا را برای گره بعدی که D است تکرار کنید و یک علامت "CCCC" بدست می آوریم.

4) بعدی برای E - "CCCB". 5) بعدی برای G - "CCCB". 6) بعدی برای B - "BCC" 7) بعدی برای C - "BCB" 8) بعدی برای F - "BCB"

همین کار را برای نمودار 2 که دریافت می کنیم انجام دهید:

• گره 1: "CCCB"
• گره 5: "CCCB"
• گره 6: "CCCC"
• گره 7: "CCBB"
• گره 2: "BCB"
• گره 3: "BCB"
• گره 4: "BCC"

بنابراین این ثابت می کند که هر دو نمودار یکسان هستند. گره (1 ، 5) = گره (E ، G). گره (A) = گره (7). گره (D) = گره (6). گره (B) = گره (4). گره (C ، F) = گره (2،3).

https://math.stackexchange.com/questions/2041534/are-two-graph-isomorphic