ใน สาขา คณิตศาสตร์ทฤษฎีกราฟ โฮโมมอร์ฟิซึมของกราฟคือฟังก์ชันที่เชื่อมโยงระหว่าง กราฟสองกราฟโดยเคารพโครงสร้างของ กราฟ ทั้งสอง กล่าวโดยละเอียดแล้ว มันคือฟังก์ชันระหว่างเซตของจุดยอดของกราฟสองกราฟที่เชื่อมโยง จุดยอดที่อยู่ติดกันไปยังจุดยอดที่อยู่ติดกัน

โฮโมมอร์ฟิซึมเป็นการขยายแนวคิดต่างๆ ของการระบายสีกราฟและอนุญาตให้แสดงปัญหาความพึงพอใจข้อจำกัด ที่สำคัญ เช่นปัญหาการจัดตารางเวลาหรือการจัดสรรความถี่ บางอย่าง ^{[ 1 ]} ข้อเท็จจริงที่ว่าโฮโมมอร์ฟิซึมสามารถประกอบกันได้นำไปสู่โครงสร้างพีชคณิตที่หลากหลาย: ลำดับก่อนหน้าบนกราฟ แลตทิซแบบกระจายและหมวดหมู่ (หนึ่งสำหรับกราฟแบบไม่มีทิศทางและหนึ่งสำหรับกราฟแบบมีทิศทาง) ^{[ 2 ]} ความซับซ้อนในการคำนวณของการค้นหาโฮโมมอร์ฟิซึมระหว่างกราฟที่กำหนดนั้นโดยทั่วไปแล้วเป็นไปไม่ได้ แต่มีความรู้มากมายเกี่ยวกับกรณีพิเศษที่สามารถแก้ไขได้ในเวลาพหุนามขอบเขตระหว่างกรณีที่จัดการได้และกรณีที่จัดการไม่ได้นั้นเป็นพื้นที่วิจัยที่คึกคัก^{[ 3 ]}

ในบทความนี้ เว้นแต่จะระบุไว้เป็นอย่างอื่นกราฟ จะเป็น กราฟจำกัด ที่ไม่มีทิศทางและอนุญาต ให้มีวงวนได้ แต่ ไม่อนุญาตให้มี ขอบหลายเส้น (ขอบขนาน) โฮโมมอร์ฟิซึมของกราฟ^{[ 4 ]} f   จากกราฟหนึ่งไปยังอีกกราฟหนึ่งเขียนว่าf  : G → Hคือฟังก์ชันจากไปยังที่รักษาขอบไว้ ในทางรูปธรรม ${\displaystyle G=(V(G),E(G))}$${\displaystyle H=(V(H),E(H))}$${\displaystyle V(G)}$${\displaystyle V(H)}$

${\displaystyle (u,v)\in E(G)}$หมายความว่า สำหรับทุกคู่ของจุดยอดใน${\displaystyle (f(u),f(v))\in E(H)}$${\displaystyle u,v}$${\displaystyle V(G)}$

ถ้ามีฟังก์ชันโฮโมมอร์ฟิซึมใดๆ จากGไปยังHแล้วGจะถูกเรียกว่าเป็นโฮโมมอร์ฟิกของHหรือH -colorableซึ่งมักจะใช้สัญลักษณ์ แทนด้วย

G → H .

นิยามข้างต้นขยายไปถึงกราฟแบบมีทิศทาง จากนั้น สำหรับโฮโมมอร์ฟิซึม f  : G → Hนั้น ( f ( u ), f ( v )) เป็นส่วนโค้ง (ขอบแบบมีทิศทาง) ของH เมื่อใดก็ตาม ที่ ( u , v ) เป็นส่วนโค้งของG

มี โฮโมมอร์ฟิซึม แบบฉีดจากGไปยังH (กล่าวคือ โฮโมมอร์ฟิซึมที่แมปจุดยอดที่แตกต่างกันในGไปยังจุดยอดที่แตกต่างกันในH ) ก็ต่อเมื่อGเป็นไอโซมอร์ฟิกกับกราฟย่อยของH เท่านั้น ถ้าโฮโมมอร์ฟิซึมf  : G → Hเป็นไบเจกชันและฟังก์ชันผกผันf ⁻¹ ของมัน เป็นโฮโมมอร์ฟิซึมของกราฟด้วยแล้วfจะเป็นไอโซมอร์ฟิซึมของกราฟ^{[ 5 ]}

แผนที่ครอบคลุมเป็นโฮโมมอร์ฟิซึมชนิดพิเศษที่สะท้อนคำจำกัดความและคุณสมบัติหลายอย่างของแผนที่ครอบคลุมในโทโพโลยี [ ^{6 ] พวก} มันถูกกำหนดให้เป็น โฮโมมอร์ฟิซึม แบบทั่วถึง (กล่าวคือ สิ่งที่แมปไปยังแต่ละจุดยอด) ที่เป็นแบบหนึ่งต่อหนึ่งในระดับท้องถิ่นด้วย นั่นคือ เป็นการส่งแบบหนึ่งต่อหนึ่งในบริเวณใกล้เคียงของแต่ละจุดยอด ตัวอย่างเช่นการครอบคลุมสองชั้นแบบทวิภาคซึ่งสร้างขึ้นจากกราฟโดยการแบ่งแต่ละจุดยอดvออกเป็นv ₀และv ₁และแทนที่ขอบแต่ละขอบu , vด้วยขอบu ₀ , v ₁และv ₀ , u ₁ฟังก์ชันที่แมปv ₀และv ₁ในการครอบคลุมไปยังvในกราฟดั้งเดิมเป็นโฮโมมอร์ฟิซึมและแผนที่ครอบคลุม

กราฟโฮมีโอเมอร์ฟิซึมเป็นแนวคิดที่แตกต่างออกไป ไม่เกี่ยวข้องโดยตรงกับโฮโมมอร์ฟิซึม โดยคร่าวๆ แล้ว มันต้องการคุณสมบัติการฉีด (injectivity) แต่ก็อนุญาตให้แมปขอบไปยังเส้นทาง (ไม่ใช่แค่ขอบ) ได้ส่วนกราฟไมเนอร์นั้นเป็นแนวคิดที่ยืดหยุ่นกว่ามาก

กราฟสองกราฟGและHจะสมมูลกันในเชิงโฮโมมอร์ฟิก^{ถ้า G → H และ H → G [ 4 ]}แผนที่ ไม่จำเป็นต้องเป็นแบบทั่วถึงหรือ^{แบบหนึ่ง}ต่อหนึ่งเสมอไป ตัวอย่างเช่นกราฟสองส่วนสมบูรณ์K _2,2และK _3,3จะสมมูลกันในเชิงโฮโมมอร์ฟิก: แผนที่แต่ละอันสามารถกำหนดได้โดยการนำครึ่งซ้าย (หรือครึ่งขวา) ของกราฟโดเมนและแมปไปยังจุดยอดเพียงจุดเดียวในครึ่งซ้าย (หรือครึ่งขวา) ของกราฟรูปภาพ

การหดตัวคือโฮโมมอร์ฟิซึมrจากกราฟGไปยังกราฟย่อยHของGโดยที่r ( v ) = vสำหรับแต่ละจุดยอดvของH ใน ^กรณีนี้กราฟย่อยHเรียกว่ารีแทรกต์ของG [ ^{7 ]}

แกนหลักคือกราฟที่ไม่มีโฮโมมอร์ฟิซึมไปยังซับกราฟแท้ใดๆ หรือกล่าวอีกนัยหนึ่ง แกนหลักสามารถนิยามได้ว่าเป็นกราฟที่ไม่สามารถหดตัวไปยังซับกราฟแท้ใดๆ ได้^{[ 8 ]} กราฟG ทุกกราฟ จะเทียบเท่ากับแกนหลักที่ไม่ซ้ำกัน (จนถึงไอโซมอร์ฟิซึม) ซึ่งเรียกว่าแกนหลักของG [ ^{9 ] ที่}น่าสังเกตคือ โดยทั่วไปแล้วสิ่งนี้จะไม่เป็นจริงสำหรับกราฟอนันต์^{[ 10 ]} อย่างไรก็ตาม นิยามเดียวกันนี้ใช้ได้กับกราฟแบบมีทิศทาง และกราฟแบบมีทิศทางก็เทียบเท่ากับแกนหลักที่ไม่ซ้ำกันเช่นกัน กราฟทุกกราฟและกราฟแบบมีทิศทางทุกกราฟจะมีแกนหลักเป็นรีแทร็กต์และเป็น ซับ กราฟเหนี่ยวนำ^{[ 7 ]}

ตัวอย่างเช่นกราฟสมบูรณ์K _n ทั้งหมด และวัฏจักรคี่ทั้งหมด ( กราฟวัฏจักรที่มีความยาวคี่) เป็นแกนหลักกราฟG ที่ระบายสีได้ 3 สี ทุกกราฟ ที่มีรูปสามเหลี่ยม (นั่นคือมีกราฟสมบูรณ์K ₃เป็นกราฟย่อย) จะเทียบเท่ากับK ₃ ในเชิงโฮโมมอร์ฟิก เนื่องจากในอีกด้านหนึ่ง การระบายสี 3 สีของGเหมือนกับโฮโมมอร์ฟิซึมG → K ₃ดังที่อธิบายไว้ด้านล่าง ในอีกด้านหนึ่ง กราฟย่อยทุกกราฟของGยอมรับโฮโมมอร์ฟิซึมไปยังG อย่างชัดเจน ซึ่งหมายความว่าK ₃ → Gนอกจากนี้ยังหมายความว่าK ₃เป็นแกนหลักของกราฟG ดังกล่าวทุก ^กราฟ ในทำนองเดียวกัน กราฟสองส่วน ทุกกราฟที่มีขอบอย่างน้อยหนึ่งขอบจะเทียบเท่ากับK ₂ ^{[ 11} ]

การระบายสีk สี สำหรับจำนวนเต็มk บางตัว คือการกำหนดสีหนึ่งในkสีให้กับแต่ละจุดยอดของกราฟGโดยที่ปลายของแต่ละขอบจะได้รับสีที่แตกต่างกัน การระบายสี kสีของGสอดคล้องกับโฮโมมอร์ฟิซึมจากGไปยังกราฟสมบูรณ์K _{k อย่างแม่นยำ} ^{[ 12 ]}อันที่จริง จุดยอดของK _kสอดคล้องกับ สี kสี และสองสีจะอยู่ติดกันในฐานะจุดยอดของK _kก็ต่อเมื่อสีทั้งสองแตกต่างกัน ดังนั้น ฟังก์ชันจะกำหนดโฮโมมอร์ฟิซึมไปยังK _kก็ต่อเมื่อมันแมปจุดยอดที่อยู่ติดกันของGไปยังสีที่แตกต่างกัน (กล่าวคือ เป็นการ ระบายสี kสี) โดยเฉพาะอย่างยิ่งGสามารถ ระบายสี kสีได้ก็ต่อเมื่อสามารถระบายสีK _{k สีได้} ^{[ 12 ]}

ถ้ามีโฮโมมอร์ฟิซึมสองตัวคือG → HและH → K _kแล้วการประกอบกันของพวก มัน G → K _kก็เป็นโฮโมมอร์ฟิซึมเช่นกัน^{[ 13 ]}กล่าวอีกนัยหนึ่งคือ ถ้ากราฟHสามารถระบายสีด้วย สี kสีได้ และมีโฮโมมอร์ฟิซึมจากGไปยังHแล้วGก็สามารถ ระบายสีด้วยสี kสีได้เช่นกัน ดังนั้นG → Hหมายความว่า χ( G ) ≤ χ( H ) โดยที่χแทนจำนวนสีของกราฟ ( ค่า k ที่น้อยที่สุด ที่ สามารถระบายสีด้วยสี kสีได้) ^{[ 14 ]}

โฮโมมอร์ฟิซึมทั่วไปยังสามารถคิดได้ว่าเป็นรูปแบบหนึ่งของการระบายสี: ถ้าจุดยอดของกราฟH ที่กำหนดไว้ คือสี ที่มีอยู่ และขอบของHอธิบายว่าสีใดเข้ากันได้การ ระบายสี HของGคือการกำหนดสีให้กับจุดยอดของGโดยที่จุดยอดที่อยู่ติดกันจะได้รับสีที่เข้ากันได้ แนวคิดมากมายเกี่ยวกับการระบายสีกราฟเข้ากับรูปแบบนี้และสามารถแสดงเป็นโฮโมมอร์ฟิซึมของกราฟไปยังตระกูลกราฟต่างๆ ได้ การระบายสีแบบวงกลมสามารถกำหนดได้โดยใช้โฮโมมอร์ฟิซึมไปยังกราฟสมบูรณ์แบบวงกลมซึ่งเป็นการปรับปรุงแนวคิดปกติของการระบายสี^{[ 15 ]}การระบายสีแบบเศษส่วนและ แบบ b เท่า สามารถกำหนดได้โดยใช้โฮโมมอร์ฟิซึมไปยังกราฟKneser ^{[ 16 ]}การระบายสีแบบ Tสอดคล้องกับโฮโมมอร์ฟิซึมไปยังกราฟอนันต์บางประเภท^{[ 17 ]} การระบายสีแบบมีทิศทาง ของกราฟแบบมีทิศทางคือโฮโมมอ ร์ฟิซึมไปยังกราฟแบบมีทิศทาง ใดๆ ^{[ 18 ]} การระบายสี L (2,1)เป็นโฮโมมอร์ฟิซึมไปยังส่วนเติมเต็มของกราฟเส้นทางซึ่งเป็นแบบฉีดเฉพาะที่ หมายความว่าจำเป็นต้องมีการฉีดในบริเวณใกล้เคียงของทุกจุดยอด^{[ 19 ]}

ความเชื่อมโยงที่น่าสนใจอีกประการหนึ่งเกี่ยวข้องกับทิศทางของกราฟ ทิศทางของกราฟแบบไม่มีทิศทางGคือกราฟแบบมีทิศทางใดๆ ที่ได้จากการเลือกทิศทางที่เป็นไปได้หนึ่งในสองทิศทางสำหรับแต่ละขอบ ตัวอย่างของทิศทางของกราฟสมบูรณ์K _kคือทัวร์นาเมนต์แบบทรานซิทีฟT → _kที่มีจุดยอด 1,2,…, kและส่วนโค้งจากiไปยังjเมื่อใดก็ตามที่i < jโฮโมมอร์ฟิซึมระหว่างทิศทางของกราฟGและHจะให้โฮโมมอร์ฟิซึมระหว่างกราฟแบบไม่มีทิศทางGและHโดยไม่ต้องคำนึงถึงทิศทาง ในทางกลับกัน เมื่อกำหนดโฮโมมอร์ฟิซึมG → Hระหว่างกราฟแบบไม่มีทิศทาง ทิศทางใดๆH →ของHสามารถดึงกลับไปยังทิศทางG →ของG ได้ดังนั้นG → จึง มีโฮโมมอร์ฟิซึมไปยังH →ดังนั้น กราฟGสามารถ ระบายสีได้ด้วย kสี (มีโฮโมมอร์ฟิซึมไปยังK _k ⁾ก็ต่อเมื่อทิศทางบางอย่างของGมีโฮโมมอร์ฟิซึมไปยังT → _k ^{[ 20} ]

ทฤษฎีบทพื้นบ้านกล่าวว่า สำหรับทุกkกราฟทิศทางGจะมีโฮโมมอร์ฟิซึมไปยังT → k _ก็ต่อเมื่อไม่มีโฮโมมอร์ฟิซึมจากเส้นทางทิศทางP → _{k +1} ^{[ 21 ]} ในที่นี้P → _nคือกราฟทิศทางที่มีจุดยอด 1, 2, …, nและขอบจากiไปยังi + 1 สำหรับi = 1, 2, …, n − 1 ดังนั้น กราฟจะ สามารถระบายสีได้ ด้วย kสี ก็ต่อเมื่อมีทิศทางที่ไม่มีโฮโมมอร์ฟิซึมจากP → _{k +1}ข้อความนี้สามารถเสริมความแข็งแกร่งได้เล็กน้อยโดยกล่าวว่า กราฟจะ สามารถระบายสีได้ด้วย kสี ก็ต่อเมื่อทิศทางบางอย่างไม่มีเส้นทางทิศทางที่มีความยาวk (ไม่มีP → _{k +1}เป็นกราฟย่อย) นี่คือทฤษฎีบท Gallai–Hasse–Roy– Vitaver

ปัญหาการจัดตารางเวลาบางอย่างสามารถจำลองได้เป็นคำถามเกี่ยวกับการค้นหาโฮโมมอร์ฟิซึมของกราฟ^{[ 22 ] [ 23 ]}ตัวอย่างเช่น อาจต้องการกำหนดหลักสูตรการฝึกอบรมให้กับช่วงเวลาในปฏิทินเพื่อให้หลักสูตรสองหลักสูตรที่นักเรียนคนเดียวกันเข้าร่วมไม่ใกล้กันเกินไปในแง่ของเวลา หลักสูตรต่างๆ ก่อตัวเป็นกราฟGโดยมีขอบระหว่างหลักสูตรสองหลักสูตรใดๆ ที่นักเรียนคนเดียวกันเข้าร่วม ช่วงเวลาต่างๆ ก่อตัวเป็นกราฟHโดยมีขอบระหว่างช่วงเวลาสองช่วงใดๆ ที่ห่างกันมากพอในแง่ของเวลา ตัวอย่างเช่น หากต้องการตารางเรียนแบบวนรอบรายสัปดาห์ โดยที่นักเรียนแต่ละคนได้รับหลักสูตรการฝึกอบรมในวันที่ไม่ต่อเนื่องกันHจะเป็นกราฟส่วนเติมเต็มของC ₇โฮโมมอร์ฟิซึมของกราฟจากGไปยังHคือตารางเรียนที่กำหนดหลักสูตรให้กับช่วงเวลาตามที่ระบุ^{[ 22 ]}หากต้องการเพิ่มข้อกำหนด เช่น ไม่มีนักเรียนคนใดคนหนึ่งมีหลักสูตรทั้งในวันศุกร์และวันจันทร์ ก็เพียงพอที่จะลบขอบที่เกี่ยวข้องออกจาก H

ปัญหา การจัดสรรความถี่อย่างง่ายสามารถระบุได้ดังนี้: เครื่องส่งสัญญาณจำนวนหนึ่งในเครือข่ายไร้สายต้องเลือกช่องความถี่ที่จะใช้ส่งข้อมูล เพื่อหลีกเลี่ยงการรบกวนเครื่องส่งสัญญาณที่อยู่ใกล้กันในเชิงภูมิศาสตร์ควรใช้ช่องที่มีความถี่ห่างกัน หากเงื่อนไขนี้ประมาณด้วยเกณฑ์เดียวในการกำหนด 'ใกล้กันในเชิงภูมิศาสตร์' และ 'ห่างกัน' การเลือกช่องที่ถูกต้องจะสอดคล้องกับโฮโมมอร์ฟิซึมของกราฟอีกครั้ง โดยควรเปลี่ยนจากกราฟของเครื่องส่งสัญญาณGที่มีขอบระหว่างคู่ที่อยู่ใกล้กันในเชิงภูมิศาสตร์ ไปยังกราฟของช่องHที่มีขอบระหว่างช่องที่ห่างกัน แม้ว่าแบบจำลองนี้จะค่อนข้างเรียบง่าย แต่ก็มีความยืดหยุ่นอยู่บ้าง: คู่เครื่องส่งสัญญาณที่ไม่ได้อยู่ใกล้กันแต่สามารถรบกวนกันได้เนื่องจากลักษณะทางภูมิศาสตร์สามารถเพิ่มลงในขอบของGได้ ส่วนคู่ที่ไม่ได้สื่อสารกันในเวลาเดียวกันสามารถลบออกได้ ในทำนองเดียวกัน คู่ช่องที่ห่างกันแต่มี การรบกวน แบบฮาร์มอนิกสามารถลบออกจากชุดขอบของHได้^{[ 24 ]}

ในแต่ละกรณี โมเดลที่เรียบง่ายเหล่านี้แสดงให้เห็นถึงปัญหามากมายที่ต้องจัดการในทางปฏิบัติ^{[ 25 ]}ปัญหาความพึงพอใจของข้อจำกัดซึ่งเป็นการขยายปัญหาโฮโมมอร์ฟิซึมของกราฟ สามารถแสดงเงื่อนไขเพิ่มเติมประเภทต่างๆ ได้ (เช่น ความชอบส่วนบุคคล หรือขอบเขตของจำนวนการกำหนดที่ตรงกัน) ซึ่งทำให้โมเดลมีความสมจริงและใช้งานได้จริงมากขึ้น

กราฟและกราฟแบบมีทิศทางสามารถมองได้ว่าเป็นกรณีพิเศษของแนวคิดทั่วไปที่เรียกว่าโครงสร้าง เชิงสัมพันธ์ (ซึ่งกำหนดเป็นเซตที่มีทูเปิลของความสัมพันธ์อยู่บนนั้น) กราฟแบบมีทิศทางเป็นโครงสร้างที่มีความสัมพันธ์แบบไบนารีเดียว (ความประชิด) บนโดเมน (เซตของจุดยอด) ^{[ 26 ] [ 3 ]}ภายใต้มุมมองนี้โฮโมมอร์ฟิซึมของโครงสร้างดังกล่าวก็คือโฮโมมอร์ฟิซึมของกราฟนั่นเอง โดยทั่วไป คำถามของการค้นหาโฮโมมอร์ฟิซึมจากโครงสร้างเชิงสัมพันธ์หนึ่งไปยังอีกโครงสร้างหนึ่งคือปัญหาความพึงพอใจของข้อจำกัด (CSP) กรณีของกราฟเป็นขั้นตอนแรกที่เป็นรูปธรรมที่ช่วยให้เข้าใจ CSP ที่ซับซ้อนมากขึ้น วิธีการเชิงอัลกอริทึมหลายวิธีสำหรับการค้นหาโฮโมมอร์ฟิซึมของกราฟ เช่นการย้อนกลับการแพร่กระจายข้อจำกัดและการค้นหาแบบโลคอล สามารถ นำไปใช้กับ CSP ทั้งหมดได้^{[ 3 ]}

สำหรับกราฟGและHคำถามที่ว่าGมีโฮโมมอร์ฟิซึมไปยังHหรือไม่นั้น สอดคล้องกับอินสแตนซ์ CSP ที่มีข้อจำกัดเพียงประเภทเดียว^{[ 3 ]}ดังต่อไปนี้ตัวแปรคือจุดยอดของGและโดเมนสำหรับแต่ละตัวแปรคือเซตจุดยอดของHการประเมินค่าคือฟังก์ชันที่กำหนดองค์ประกอบของโดเมนให้กับแต่ละตัวแปร ดังนั้นฟังก์ชันfจากV ( G ) ไปยังV ( H ) แต่ละขอบหรือส่วนโค้ง ( u , v ) ของGจะสอดคล้องกับข้อจำกัด (( u , v ), E( H )) นี่คือข้อจำกัดที่แสดงว่าการประเมินค่าควรแมปส่วนโค้ง ( u , v ) ไปยังคู่ ( f ( u ), f ( v )) ที่อยู่ในความสัมพันธ์E ( H ) นั่นคือไปยังส่วนโค้งของHวิธีแก้ปัญหา CSP คือการประเมินค่าที่เคารพข้อจำกัดทั้งหมด ดังนั้นจึงเป็นโฮโมมอร์ฟิซึมจากGไปยังH อย่าง แท้จริง

องค์ประกอบของโฮโมมอร์ฟิซึมคือโฮโมมอร์ฟิซึม^{[ 13 ]} โดยเฉพาะอย่างยิ่ง ความสัมพันธ์ → บนกราฟเป็นแบบถ่ายทอด (และสะท้อนกลับอย่างเห็นได้ชัด) ดังนั้นจึงเป็นพรีออร์เดอร์บนกราฟ^{[ 27 ]} ให้ชั้นสมมูลของกราฟGภายใต้ความสมมูลแบบโฮโมมอร์ฟิกเป็น [ G ] ชั้นสมมูลยังสามารถแสดงได้ด้วยแกนกลางที่ไม่ซ้ำกันใน [ G ] ความสัมพันธ์ → เป็นลำดับบางส่วนบนชั้นสมมูลเหล่านั้น มันกำหนดโพเซต^{[ 28 ]}

ให้G < Hแทนว่ามีโฮโมมอร์ฟิซึมจากGไปยังHแต่ไม่มีโฮโมมอร์ฟิซึมจากHไปยังGความสัมพันธ์ → เป็นลำดับหนาแน่นหมายความว่าสำหรับกราฟ (แบบไม่มีทิศทาง) G , H ทั้งหมด ที่G < HจะมีกราฟKที่G < K < H (ยกเว้นกรณีที่ไม่สำคัญG = K ₀หรือK ₁ ) ^{[ 29 ] [ 30 ]} ตัวอย่างเช่น ระหว่างกราฟสมบูรณ์ สองกราฟใดๆ (ยกเว้นK ₀ , K ₁ , K ₂ ) จะมีกราฟสมบูรณ์แบบวงกลม จำนวนอนันต์ ซึ่งสอดคล้องกับจำนวนตรรกยะระหว่างจำนวนธรรมชาติ^{[ 31 ]}

โพเซตของคลาสสมมูลของกราฟภายใต้โฮโมมอร์ฟิซึมคือแลตทิซแบบกระจายโดยที่การรวมของ [ G ] และ [ H ] ถูกกำหนดให้เป็น (คลาสสมมูลของ) ยูเนียนที่ไม่ทับซ้อนกัน [ G ∪ H ] และการตัดกันของ [ G ] และ [ H ] ถูกกำหนดให้เป็นผลคูณเทนเซอร์ [ G × H ] (การเลือกกราฟGและHที่แทนคลาสสมมูล [ G ] และ [ H ] ไม่สำคัญ) ^{[ 32 ]} องค์ประกอบที่ไม่สามารถลดทอนได้ของแลตทิซนี้คือ กราฟ ที่เชื่อมต่อกัน อย่างแน่นอน ซึ่งสามารถแสดงได้โดยใช้ข้อเท็จจริงที่ว่าโฮโมมอร์ฟิซึมจะแมปกราฟที่เชื่อมต่อกันไปยังส่วนประกอบที่เชื่อมต่อกันหนึ่งส่วนของกราฟเป้าหมาย^{[ 33 ] [ 34 ]} องค์ประกอบที่ไม่สามารถลดทอนได้ของแลตทิซนี้คือกราฟแบบคูณ อย่างแน่นอน ซึ่งก็คือกราฟKที่ผลคูณG × Hมีโฮโมมอร์ฟิซึมไป ยัง Kก็ต่อเมื่อGหรือH ตัวใดตัวหนึ่งมีโฮโมมอร์ฟิซึมเช่น กัน การระบุกราฟการคูณเป็นหัวใจสำคัญของ สมมติฐาน ของHedetniemi ^{[ 35 ] [ 36 ]}

โฮโมมอร์ฟิซึมของกราฟยังก่อให้เกิดหมวดหมู่โดยมีกราฟเป็นวัตถุและโฮโมมอร์ฟิซึมเป็นลูกศร^{[ 37 ]} วัตถุเริ่มต้นคือกราฟว่าง ในขณะที่วัตถุปลายทางคือกราฟที่มีจุดยอดหนึ่งจุดและวงวน หนึ่งวง ที่จุดยอดนั้นผลคูณเทนเซอร์ของกราฟคือผลคูณเชิงหมวดหมู่และกราฟเอกซ์โพเนนเชียลคือวัตถุเอกซ์โพเนนเชียลสำหรับหมวดหมู่นี้^{[ 36 ] [ 38 ]} เนื่องจากการดำเนินการทั้งสองนี้ได้รับการกำหนดไว้เสมอ หมวดหมู่ของกราฟจึงเป็นหมวดหมู่ปิดแบบคาร์ทีเซียน ด้วยเหตุผลเดียวกันนี้ แลตทิซของชั้นสมมูลของกราฟภายใต้โฮโมมอร์ฟิ ซึมจึงเป็นพีชคณิตเฮย์ติง^{[ 36 ] [ 38 ]}

สำหรับกราฟแบบมีทิศทาง คำจำกัดความเดียวกันนี้ใช้ได้ โดยเฉพาะอย่างยิ่ง → เป็นลำดับบางส่วนบนชั้นสมมูลของกราฟแบบมีทิศทาง มันแตกต่างจากลำดับ → บนชั้นสมมูลของกราฟแบบไม่มีทิศทาง แต่มีลำดับย่อยอยู่ภายใน เนื่องจากกราฟแบบไม่มีทิศทางทุกกราฟสามารถคิดได้ว่าเป็นกราฟแบบมีทิศทาง โดยที่ส่วนโค้งทุกส่วน ( u , v ) ปรากฏพร้อมกับส่วนโค้งผกผัน ( v , u ) และสิ่งนี้ไม่ได้เปลี่ยนแปลงคำจำกัดความของโฮโมมอร์ฟิซึม ลำดับ → สำหรับกราฟแบบมีทิศทางเป็นแลตทิซแบบกระจายและพีชคณิตเฮย์ติงอีกครั้ง โดยมีการดำเนินการรวมและพบที่กำหนดไว้ก่อนหน้านี้ อย่างไรก็ตาม มันไม่หนาแน่น นอกจากนี้ยังมีหมวดหมู่ที่มีกราฟแบบมีทิศทางเป็นวัตถุและโฮโมมอร์ฟิซึมเป็นลูกศร ซึ่งเป็นหมวดหมู่ปิดแบบคาร์ทีเซียนอีก ครั้ง ^{[ 39 ] [ 38 ]}

มีกราฟที่ไม่สามารถเปรียบเทียบกันได้หลายคู่โดยสัมพันธ์กับลำดับก่อนของโฮโมมอร์ฟิซึม นั่นคือคู่ของกราฟที่ไม่มีคู่ใดคู่หนึ่งยอมรับโฮโมมอร์ฟิซึมไปยังอีกคู่หนึ่ง^{[ 40 ]} วิธีหนึ่งในการสร้างกราฟเหล่านี้คือการพิจารณาเส้นรอบวงคี่ของกราฟGซึ่งเป็นความยาวของวัฏจักรที่มีความยาวเป็นเลขคี่ที่สั้นที่สุด เส้นรอบวงคี่เทียบเท่ากับจำนวนคี่g ที่เล็กที่สุด ซึ่งมีโฮโมมอร์ฟิซึมจากกราฟวัฏจักรบนจุดยอดg ไปยัง Gด้วยเหตุนี้ ถ้าG → Hเส้นรอบวงคี่ของGจะมากกว่าหรือเท่ากับเส้นรอบวงคี่ของH ^{[ 41 ]}

ในทางกลับกัน ถ้าG → Hแล้วจำนวนสีของGจะน้อยกว่าหรือเท่ากับจำนวนสีของHดังนั้น ถ้าGมีเส้นรอบวงคี่ที่ใหญ่กว่าH อย่างชัดเจน และมีจำนวนสีที่ใหญ่กว่าH อย่างชัดเจน GและH จะเปรียบเทียบกันไม่ได้^{[ 40 ]} ตัวอย่างเช่นกราฟ Grötzschมีสี 4 สีและไม่มีรูปสามเหลี่ยม (มีเส้นรอบวง 4 และเส้นรอบวงคี่ 5) ^{[ 42 ]}ดังนั้นจึงเปรียบเทียบกับกราฟรูปสามเหลี่ยมK ₃ไม่ ได้

ตัวอย่างของกราฟที่มีค่าเส้นรอบวงคี่และจำนวนสีมากตามอำเภอใจ ได้แก่กราฟ Kneser ^{[ 43 ]}และ กราฟ Mycielskian ทั่วไป^{[ 44 ]} ลำดับของกราฟดังกล่าวที่มีค่าพารามิเตอร์ทั้งสองเพิ่มขึ้นพร้อมกัน จะให้กราฟที่ไม่สามารถเปรียบเทียบกันได้เป็นอนันต์ ( แอนติเชนในลำดับก่อนของโฮโมมอร์ฟิซึม) ^{[ 45 ]} คุณสมบัติอื่นๆ เช่นความหนาแน่นของลำดับก่อนของโฮโมมอร์ฟิซึม สามารถพิสูจน์ได้โดยใช้ตระกูลดังกล่าว^{[ 46 ]} การสร้างกราฟที่มีค่าจำนวนสีและเส้นรอบวงมาก ไม่ใช่แค่เส้นรอบวงคี่ ก็เป็นไปได้เช่นกัน แต่ซับซ้อนกว่า (ดูเส้นรอบวงและการระบายสีกราฟ )

ในบรรดากราฟแบบมีทิศทาง การหาคู่ที่ไม่สามารถเปรียบเทียบกันได้นั้นง่ายกว่ามาก ตัวอย่างเช่น พิจารณากราฟวงจรแบบมีทิศทางC → _nที่มีจุดยอด 1, 2, …, nและขอบจากiไปยังi + 1 (สำหรับi = 1, 2, …, n − 1) และจากnไปยัง 1 จะมีโฮโมมอร์ฟิซึมจากC → _nไปยังC → _k ( n , k ≥ 3) ก็ต่อเมื่อnเป็นพหุคูณของkโดยเฉพาะอย่างยิ่ง กราฟวงจรแบบมี ทิศทาง C → _nที่n เป็นจำนวน เฉพาะนั้นไม่สามารถเปรียบเทียบกันได้ทั้งหมด^{[ 47 ]}

ในปัญหาโฮโมมอร์ฟิซึมของกราฟ ตัวอย่างหนึ่งคือคู่ของกราฟ ( G , H ) และคำตอบคือโฮโมมอร์ฟิซึมจากGไปยังH ปัญหาการตัดสินใจทั่วไปที่ถามว่ามีคำตอบใดหรือไม่นั้นเป็นปัญหาNP-complete [ ^{48 ] อย่างไรก็ตาม}การจำกัดตัวอย่างที่อนุญาตทำให้เกิดปัญหาที่แตกต่างกันหลากหลาย ซึ่งบางปัญหานั้นแก้ไขได้ง่ายกว่ามาก วิธีการที่ใช้เมื่อจำกัดด้านซ้าย Gนั้นแตกต่างจากด้านขวาH มาก แต่ในแต่ละกรณีจะมีการแบ่งแยก (ขอบเขตที่ชัดเจนระหว่างกรณีง่ายและยาก) ที่ทราบหรือคาดเดาได้

ปัญหาโฮโมมอร์ฟิซึมที่มีกราฟH คง ที่ทางด้านขวาของแต่ละอินสแตนซ์เรียกว่า ปัญหาการระบายสี Hเมื่อHเป็นกราฟสมบูรณ์K _kนี่คือปัญหาการระบายสีกราฟkซึ่งสามารถแก้ไขได้ในเวลาพหุนามสำหรับk = 0, 1, 2 และNP-completeในกรณีอื่น ๆ^{[ 49 ]} โดยเฉพาะอย่างยิ่ง ความสามารถในการระบายสี K ₂ของกราฟGเทียบเท่ากับการที่Gเป็นกราฟสองส่วนซึ่งสามารถทดสอบได้ในเวลาเชิงเส้น โดยทั่วไปแล้ว เมื่อใดก็ตามที่Hเป็นกราฟสองส่วน ความสามารถในการระบายสี Hจะเทียบเท่ากับ ความสามารถในการระบายสี K ₂ (หรือ ความสามารถในการระบายสี K ₀ / K ₁เมื่อHว่างเปล่า/ไม่มีขอบ) ดังนั้นจึงตัดสินใจได้ง่ายเท่ากัน^{[ 50 ]} Pavol HellและJaroslav Nešetřilพิสูจน์แล้วว่าสำหรับกราฟที่ไม่มีทิศทาง ไม่มีกรณีอื่นใดที่สามารถแก้ไขได้:

ทฤษฎีบท Hell–Nešetřil (1990): ปัญหาการระบายสี Hอยู่ใน P เมื่อHเป็นแบบทวิภาค และ NP-complete ในกรณีอื่น^{[ 51 ] [ 52 ]}

สิ่งนี้ยังเป็นที่รู้จักในชื่อทฤษฎีบทการแบ่งแยกสำหรับโฮโมมอร์ฟิซึมกราฟ (แบบไม่มีทิศทาง) เนื่องจากมันแบ่ง ปัญหาการระบายสี Hออกเป็นปัญหา NP-complete หรือปัญหา P โดยไม่มี กรณี กลางสำหรับกราฟแบบมีทิศทาง สถานการณ์จะซับซ้อนกว่าและในความเป็นจริงเทียบเท่ากับคำถามทั่วไปมากกว่าเกี่ยวกับการกำหนดลักษณะความซับซ้อนของปัญหาความพึงพอใจข้อจำกัด [ ^{53 ] ปรากฏ} ว่า ปัญหาการระบายสี Hสำหรับกราฟแบบมีทิศทางนั้นมีความทั่วไปและหลากหลายเช่นเดียวกับ CSP ที่มีข้อจำกัดประเภทอื่น ๆ^{[ 54 ] [ 55 ]}ในทางรูปธรรมภาษาข้อจำกัด (หรือแม่แบบ ) Γ (แบบจำกัด) คือโดเมนแบบจำกัดและเซตความสัมพันธ์แบบจำกัดเหนือโดเมนนี้ CSP( Γ ) คือปัญหาความพึงพอใจข้อจำกัดที่อนุญาตให้ใช้ข้อจำกัดในΓเท่านั้น

ทฤษฎีบท (Feder, Vardi 1998): สำหรับภาษาข้อจำกัดΓ ทุก ภาษา ปัญหา CSP( Γ ) จะเทียบเท่ากับการลดเวลาพหุนามกับ ปัญหาการระบายสี H บาง ปัญหา สำหรับกราฟทิศทางH บาง กราฟ^{[ 55 ]}

โดยสัญชาตญาณแล้ว นี่หมายความว่าเทคนิคอัลกอริทึมหรือผลลัพธ์ความซับซ้อนใดๆ ที่ใช้กับ ปัญหาการระบายสี HสำหรับกราฟทิศทางHก็สามารถนำไปใช้กับ CSP ทั่วไปได้เช่นกัน โดยเฉพาะอย่างยิ่ง เราสามารถถามได้ว่าทฤษฎีบท Hell–Nešetřil สามารถขยายไปยังกราฟทิศทางได้หรือไม่ ตามทฤษฎีบทข้างต้น สิ่งนี้เทียบเท่ากับการคาดการณ์ของ Feder–Vardi (หรือที่รู้จักกันในชื่อการคาดการณ์ CSP การคาดการณ์การแบ่งแยก) เกี่ยวกับการแบ่งแยก CSP ซึ่งระบุว่าสำหรับภาษาข้อจำกัดΓ ทุกภาษา CSP( Γ ) เป็น NP-complete หรืออยู่ใน P ^{[ 48 ]}การคาดการณ์นี้ได้รับการพิสูจน์ในปี 2017 โดย Dmitry Zhuk และ Andrei Bulatov อย่างอิสระ ซึ่งนำไปสู่บทสรุปต่อไปนี้:

บทสรุป (Bulatov 2017; Zhuk 2017): ปัญหาการระบายสี Hบนกราฟแบบมีทิศทาง สำหรับH ที่กำหนดไว้ จะอยู่ใน P หรือ NP-complete

ปัญหาโฮโมมอร์ฟิซึมที่มีกราฟG คงที่เพียงกราฟเดียว ทางด้านซ้ายของอินสแตนซ์อินพุตสามารถแก้ไขได้ด้วยกำลังทั้งหมดในเวลา | V ( H )| ^{O(| V ( G )|)}ดังนั้นจึงเป็นพหุนามตามขนาดของกราฟอินพุตH [ ^{56 ]}กล่าวอีกนัยหนึ่ง ปัญหานั้นอยู่ใน P อย่างชัดเจนสำหรับกราฟGที่มีขนาดจำกัด คำถามที่น่าสนใจคือ คุณสมบัติอื่นใดของG นอกเหนือจากขนาด ^ที่ทำให้อัลกอริทึมพหุนามเป็นไปได้

คุณสมบัติที่สำคัญคือtreewidthซึ่งเป็นการวัดว่ากราฟนั้นมีลักษณะคล้ายต้นไม้มากน้อยเพียงใด สำหรับกราฟGที่มี treewidth ไม่เกินkและกราฟHปัญหาโฮโมมอร์ฟิซึมสามารถแก้ไขได้ในเวลา | V ( H )| ^{O( k )}ด้วย วิธี การเขียนโปรแกรมแบบไดนามิก มาตรฐาน อันที่จริง เพียงแค่สมมติว่าแกนกลางของGมี treewidth ไม่เกินk ก็เพียงพอแล้ว ซึ่งเป็นเช่นนั้นแม้ว่าแกนกลางจะไม่เป็นที่รู้จักก็ตาม^{[ 57 ] [ 58 ]}

เลขชี้กำลังในอัลกอริธึมเวลา | V ( H )| ^{O( k )}ไม่สามารถลดลงอย่างมีนัยสำคัญได้: ไม่มีอัลกอริธึมใดที่มีเวลาทำงาน | V ( H )| ^{o(tw( G ) /log tw( G ))}อยู่จริง โดยสมมติว่าสมมติฐานเวลาเลขชี้กำลัง (ETH) แม้ว่าอินพุตจะถูกจำกัดไว้ที่คลาสของกราฟใดๆ ที่มี treewidth ไม่จำกัดก็ตาม^{[ 59 ]} ETH เป็นสมมติฐานที่ยังไม่ได้รับการพิสูจน์คล้ายกับP ≠ NPแต่แข็งแกร่งกว่า ภายใต้สมมติฐานเดียวกันนี้ แทบจะไม่มีคุณสมบัติอื่นๆ ที่สามารถใช้เพื่อให้ได้อัลกอริธึมเวลาพหุนามได้อีกด้วย สิ่งนี้ได้รับการกำหนดเป็นทางการดังนี้:

ทฤษฎีบท ( Grohe ): สำหรับคลาสของกราฟที่คำนวณได้ปัญหาโฮโมมอร์ฟิซึมสำหรับอินสแตนซ์ที่มีอยู่ใน P ก็ต่อเมื่อกราฟในมีแกนที่มีความกว้างต้นไม้จำกัด (โดยสมมติว่า ETH) ^{[ 58 ]}${\displaystyle {\คณิตศาสตร์ {G}}}$${\displaystyle (G,H)}$${\displaystyle G\in {\mathcal {G}}}$${\displaystyle {\คณิตศาสตร์ {G}}}$

อาจมีคนถามว่าปัญหานี้สามารถแก้ไขได้อย่างน้อยในเวลาที่ขึ้นอยู่กับG อย่างมาก หรือไม่ แต่ขึ้นอยู่กับขนาดของH ในรูปแบบพหุนามคง ที่ คำตอบจะเป็นบวกอีกครั้งหากเราจำกัดGไว้ที่คลาสของกราฟที่มีแกนที่มีความกว้างของต้นไม้ที่จำกัด และเป็นลบสำหรับคลาสอื่นๆ^{[ 58 ]} ในภาษาของความซับซ้อนแบบพารามิเตอร์สิ่งนี้ระบุอย่างเป็นทางการว่าปัญหาโฮโมมอร์ฟิซึมที่กำหนดพารามิเตอร์โดยขนาด (จำนวนขอบ) ของGแสดงให้เห็นถึงความแตกต่างสองประการ มันสามารถจัดการได้ด้วยพารามิเตอร์คงที่หากกราฟในมีแกนที่มีความกว้างของต้นไม้ที่จำกัด และW[1] -สมบูรณ์ในกรณีอื่นๆ ${\displaystyle {\คณิตศาสตร์ {G}}}$${\displaystyle {\คณิตศาสตร์ {G}}}$

ข้อความเดียวกันนี้ใช้ได้กับปัญหาความพึงพอใจของข้อจำกัดโดยทั่วไป (หรือโครงสร้างเชิงสัมพันธ์ กล่าวอีกนัยหนึ่ง) ข้อสมมติเพียงอย่างเดียวที่จำเป็นคือข้อจำกัดสามารถเกี่ยวข้องกับตัวแปรจำนวนจำกัดเท่านั้น (ความสัมพันธ์ทั้งหมดมีจำนวนอาร์กิวเมนต์จำกัด 2 ในกรณีของกราฟ) พารามิเตอร์ที่เกี่ยวข้องคือ treewidth ของกราฟข้อจำกัดหลัก^{[ 59 ]}

• คำศัพท์เฉพาะทางทฤษฎีกราฟ
• โฮโมมอร์ฟิซึมหมายถึง แนวคิดเดียวกันที่ใช้กับโครงสร้างพีชคณิตที่แตกต่างกัน
• การเขียนกราฟใหม่
• กราฟมัธยฐานสามารถนิยามได้ว่าเป็นการหดตัวของไฮเปอร์คิวบ์
• ข้อสันนิษฐานของซิโดเรนโก