圖同態
圖論中,保持圖結構的映射 / 維基百科,自由的 encyclopedia
数学分支圖論中,圖同態(英語:graph homomorphism)是兩幅图之間保結構的映射。具體而言,該映射將某圖的各顶点映至另一圖的頂點,且若兩頂點相鄰,則其像仍然相鄰。
同態是若干種圖着色概念的推廣,適用於表達一類重要的約束滿足問題,如排程、頻段分配(英语:frequency assignment)問題。[1]同態可以複合,為全體圖組成的類賦予豐富的代數結構:其上的预序关系、分配格結構、範疇結構(分為無向圖範疇與有向圖範疇兩種)。[2]欲尋找任意兩圖間的同態,而無額外條件,則現時所知的計算複雜度(英语:computational complexity)高得不切實際,但對於某些特定類別的圖,已知有多項式時間算法。此類問題易解與否,兩者的分野,是活躍的研究方向。[3]