ถ้ากราฟสองกราฟเป็นไอโซมอร์ฟิกแล้วดีเทอร์มิแนนต์ของมันจะเท่ากันหรือไม่?

Aug 18 2020

กราฟจุดยอด 10 จุด G1 และ G2

ฉันกำลังแก้แบบฝึกหัดในบทที่ 2 จาก Graph Theory with Algorithms และ Applications จนถึงตอนนี้สำหรับ isomorphism ฉันแค่เขียนขอบทั้งหมดแล้วลองหารูปแบบซึ่งสำหรับกราฟขนาดเล็กก็เพียงพอแล้ว สำหรับกราฟ 30 ขอบ 10 จุด 2 จุดนี้ฉันคิดว่าฉันต้องการอะไรที่ปรับขนาดได้มากกว่านี้ ฉันพยายาม 'แปล' กราฟทั้งสองเป็นโครงสร้างที่เป็นหนึ่งเดียว แต่ไม่แน่นอนหากจุดยอดหนึ่งเปลี่ยนชื่อกราฟก็จะดูแตกต่างกันด้วย ฉันเขียนเมทริกซ์ adjacency โดยพยายามหารูปแบบและมีคอลัมน์ที่ทำให้ฉันสงสัยว่าทั้งสองนี้อาจไม่ใช่ไอโซมอร์ฟิก อย่างไรก็ตามฉันสามารถเปลี่ยนชื่อของจุดยอดเพื่อให้คอลัมน์ดูคล้ายกันมากขึ้น อย่างไรก็ตามฉันพบว่ากราฟสองกราฟ (A, B) เป็นไอโซมอร์ฟิกถ้า A = PBP (t) โดยที่ P เป็นเมทริกซ์การเปลี่ยนแปลงและ P (t) คือทรานสโพส

เนื่องจาก det (P) = 1 หรือ -1 = det (P (t)) และ det (AB) = det (A) * det (B) ถ้า A และ B เป็น isomorphic:

det (A) = 1 | -1 * det (B) * 1 | -1 det (A) = det (B)

เมทริกซ์ adjacency สองตัวสามารถมีดีเทอร์มิแนนต์เดียวกันและไม่เป็นไอโซมอร์ฟิกได้หรือไม่ หรือความเท่าเทียมกันในดีเทอร์มีแนนต์เป็นเงื่อนไขที่เพียงพอ (และสามารถปรับขนาดได้มากขึ้น) สำหรับไอโซมอร์ฟิซึม?

ดีที่สุด

เซอร์จิโอ

คำตอบ

9 BenGrossmann Aug 17 2020 at 22:47

มันเป็นความจริงที่เมทริกซ์ความใกล้เคียงของกราฟไอโซมอร์ฟิกจะมีดีเทอร์มิแนนต์เดียวกัน อันที่จริงถ้า$A = PBP^T$ สำหรับเมทริกซ์การเปลี่ยนแปลง $P$แล้ว $$ \det(A) = \det(P) \det(B) \det(P^T) = \det(P)^2 \det(B) = \det(B). $$ ในความเป็นจริงเราสามารถพูดได้มากกว่านี้: เพราะว่า $A$ และ $B$เป็นเมทริกซ์ที่คล้ายกันโดยจะมีค่าลักษณะเฉพาะเหมือนกัน โปรดทราบว่าหากเมทริกซ์สองเมทริกซ์มีค่าลักษณะเฉพาะเหมือนกันก็จะมีดีเทอร์มีแนนต์เดียวกันโดยอัตโนมัติ

การสนทนาไม่ถือ: if $A,B$ คือเมทริกซ์ adjacency ของกราฟสองกราฟและเรามี $\det(A) = \det(B)$ไม่จำเป็นต้องถือว่ากราฟเป็นไอโซมอร์ฟิก ในความเป็นจริงแม้ว่า$A$ และ $B$มีค่าลักษณะเฉพาะเหมือนกันไม่จำเป็นต้องถือว่ากราฟเป็นไอโซมอร์ฟิก ตัวอย่างของปรากฏการณ์นี้เรียกว่ากราฟคู่isospectral (หรือ cospectral)

1 JCAA Aug 17 2020 at 23:04

ไม่ใช่เส้นทางของความยาว 2 (2 ขอบ 3 จุดยอด) มี det 0 และกราฟที่มีจุดยอด 3 จุดและไม่มีขอบก็มี det 0