กลับไปหน้าบทความ

อ่าน 2 นาที

ไม่มีชื่อบทความ

ใน ทางคณิตศาสตร์ กราฟ k- อัลตรา โฮโมจีนัส คือ กราฟ ที่ ไอโซมอร์ฟิซึม ทุกตัว ระหว่าง กราฟย่อยเหนี่ยวนำ สองตัว ที่มีจุดยอดไม่เกิน k จุด สามารถขยายเป็น ออโตมอร์ฟิซึม...

กราฟเอกพันธุ์

กราฟด้านซ้ายเป็นกราฟ3-ultrahomogeneous : สำหรับ กราฟย่อยสองกราฟใดๆที่สมมาตรกันและมีจุดยอดไม่เกิน 3 จุด (ตัวอย่างชุดกราฟย่อยที่ติดป้ายสีแดงและสีน้ำเงิน) คุณสามารถเลือกการแมปป้ายกำกับใดๆ จากกราฟหนึ่งไปยังอีกกราฟหนึ่งได้โดยที่การเชื่อมต่อระหว่างกราฟทั้งสองยังคงเหมือนเดิม (เช่น จุดยอด 2 ไปยัง 3, 1 ไปยัง 4, 0 ไปยัง 5 โดยที่ 2 ยังคงเชื่อมต่อกับ 1 และ 1 ยังคงเชื่อมต่อกับ 0) จากนั้นคุณสามารถแทนที่กราฟหนึ่งด้วยกราฟอีกกราฟหนึ่ง (เปลี่ยนจุดยอดสีน้ำเงินเป็นป้ายกำกับ 2, 1 และ 0) แล้วติดป้ายกำกับส่วนที่เหลือของกราฟใหม่ในลักษณะที่ยังคงการเชื่อมต่อของกราฟเดิมไว้ กราฟตรงกลางเป็นกราฟเอกพันธุ์ 3แต่ไม่ใช่กราฟเอกพันธุ์ 3 ขั้นสุด: มีอย่างน้อยหนึ่งวิธีในการแมปและแทนที่จุดยอดของกราฟย่อยหนึ่งด้วยจุดยอดของกราฟย่อยอื่นๆ แล้วเปลี่ยนชื่อใหม่เพื่อให้ได้กราฟที่สมมาตรกัน (1 เป็น 4, 2 เป็น 3, 5 เป็น 0) แต่ไม่ใช่ การแมปที่รักษากราฟย่อย ทั้งหมด (1 เป็น 0, 2 เป็น 3, 5 เป็น 4) ที่จะทำให้กราฟสามารถเปลี่ยนชื่อเป็นออโตมอร์ฟิซึมของกราฟเดิมได้ กราฟด้านขวาเป็นกราฟเอกพันธุ์ : เป็นกราฟเอกพันธุ์ k สำหรับขนาดกราฟย่อย k ใดๆ ซึ่งทำให้กราฟเป็นกราฟเอกพันธุ์ k ขั้นสุด ...

ในทางคณิตศาสตร์กราฟk-อัลตราโฮโมจีนัสคือกราฟที่ไอโซมอร์ฟิซึม ทุกตัว ระหว่างกราฟย่อยเหนี่ยวนำ สองตัว ที่มีจุดยอดไม่เกินkจุด สามารถขยายเป็นออโตมอร์ฟิซึมของกราฟทั้งหมดได้ กราฟ k- โฮ โมจีนัสเป็นไปตามคุณสมบัติเดียวกันในรูปแบบที่อ่อนกว่า ซึ่งไอโซมอร์ฟิซึมทุกตัวระหว่างกราฟย่อยเหนี่ยวนำสองตัวบ่งบอกถึงการมีอยู่ของออโตมอร์ฟิซึมของกราฟทั้งหมดที่แมปกราฟย่อยหนึ่งไปยังอีกกราฟย่อยหนึ่ง (แต่ไม่จำเป็นต้องขยายไอโซมอร์ฟิซึมที่กำหนด) [ 1 ]

กราฟเอกพันธุ์คือกราฟที่เป็นk-เอกพันธุ์สำหรับทุกkหรือเทียบเท่ากับk-เอกพันธุ์พิเศษสำหรับทุกkและด้วยเหตุนี้ กราฟเอกพันธุ์ทุกกราฟจึงเป็นเอกพันธุ์พิเศษด้วย[ 1 ]เป็นกรณีพิเศษของแบบจำลองเอกพันธุ์

การจำแนกประเภท

กราฟเอกพันธุ์จำกัดเพียงอย่างเดียวคือกราฟคลัสเตอร์mK ที่สร้างขึ้นจากการรวมแบบไม่ทับซ้อนของกราฟสมบูรณ์ ที่สมมาตรกัน กราฟTuránที่สร้างขึ้นเป็นกราฟส่วนเติมเต็มของmK กราฟเรือ 3 × 3 และวัฏจักร 5 [ 2 ]

กราฟเอกพันธุ์อนันต์ ที่นับได้เพียงอย่างเดียวคือการรวมกันแบบไม่ทับซ้อนของกราฟสมบูรณ์ที่สมมาตรกัน (โดยที่ขนาดของกราฟสมบูรณ์แต่ละกราฟ จำนวนกราฟสมบูรณ์ หรือทั้งสองจำนวนเป็นอนันต์ที่นับได้) กราฟส่วนเติมเต็ม กราฟเฮนสันพร้อมกับกราฟส่วนเติมเต็ม และกราฟราโด[ 3 ]

ถ้ากราฟเป็น 5-อัลตราโฮโมจีนัส แสดงว่ากราฟนั้นเป็นอัลตราโฮโมจีนัสสำหรับทุกkมีเพียง กราฟ เชื่อมต่อ สอง กราฟเท่านั้นที่เป็น 4-อัลตราโฮโมจีนัสแต่ไม่ใช่ 5-อัลตราโฮโมจีนัส ได้แก่กราฟ Schläfliและส่วนเติมเต็มของมัน การพิสูจน์อาศัย การจำแนกกลุ่ม ง่ายจำกัด[ 4 ]

การเปลี่ยนแปลง

กราฟจะเรียกว่าเชื่อมต่อแบบเอกพันธุ์ได้ก็ต่อเมื่อไอโซมอร์ฟิซึมทุกตัวระหว่างกราฟย่อยที่เชื่อมต่อกันสองตัวสามารถขยายไปเป็นออโตมอร์ฟิซึมของกราฟทั้งหมดได้ นอกจากกราฟเอกพันธุ์แล้ว กราฟเชื่อมต่อแบบเอกพันธุ์ที่เชื่อมต่อกันแบบจำกัดยังรวมถึงกราฟวงจร ทั้งหมด กราฟรูคสี่เหลี่ยมทั้งหมดกราฟปีเตอร์เซน และ กราฟเคล็บช์แบบ5-ปกติ[ 5 ]

หมายเหตุ

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ไม่มีชื่อบทความ

ใน ทางคณิตศาสตร์ กราฟ k- อัลตรา โฮโมจีนัส คือ กราฟ ที่ ไอโซมอร์ฟิซึม ทุกตัว ระหว่าง กราฟย่อยเหนี่ยวนำ สองตัว ที่มีจุดยอดไม่เกิน k จุด สามารถขยายเป็น ออโตมอร์ฟิซึม...

การจำแนกประเภท

กราฟเอกพันธุ์จำกัดเพียงอย่างเดียวคือ กราฟคลัสเตอร์ mK ที่สร้างขึ้นจาก การรวมแบบไม่ทับซ้อน ของ กราฟสมบูรณ์ ที่สมมาตรกัน กราฟ Turán ที่สร้างขึ้นเป็น กราฟส่วนเติมเต็ม ของ mK กราฟเรือ 3 × 3 และ วัฏจักร 5 [ 2 ]

การเปลี่ยนแปลง

กราฟจะเรียกว่า เชื่อมต่อแบบเอกพันธุ์ได้ก็ต่อ เมื่อไอโซมอร์ฟิซึมทุกตัวระหว่างกราฟย่อยที่เชื่อมต่อกันสองตัวสามารถขยายไปเป็นออโตมอร์ฟิซึมของกราฟทั้งหมดได้ นอกจากกราฟเอกพันธุ์แล้ว กราฟเชื่อมต่อแบบเอกพันธุ์ที่เชื่อมต่อกันแบบจำกัดยังรวมถึง กราฟวงจร ทั้งหมด กราฟรูค...

หมายเหตุ

1 2 รอนเซ่ (1978 ) ↑ การ์ดิเนอร์ (1976 ) ↑ Lachlan & Woodrow (1980) . ↑ Buczak (1980) ; Cameron (1980) ; Devillers (2002) . ↑ การ์ดิเนอร์ (1978) ; เกรย์ และ แมคเฟอร์สัน (2010)