Graph homomorphisms form a natural

Graph homomorphisms form a natural generalization of graph colorings: there is a homomorphism from a graph G to
the complete graph on k vertices if and only if G is k-colorable. A homomorphism from a graph G = (VG, EG) to a graph
R = (V R , ER ) is a mapping r : VG → V R that maps adjacent vertices of G to adjacent vertices of R, i.e., r(u)r(v) ∈ ER
whenever uv ∈ EG . A homomorphism r from G to R is locally surjective if the following is true for every vertex u of G: for
every neighbor y of r(u) in R, there is at least one neighbor v of u in G with r(v) = y. We also call such an r an R-role
assignment. See Fig. 1 for an example.
Role assignments originate in the theory of social behavior [9,24]. A role graph R models roles and their relationships,
and for a given society we can ask if its individuals can be assigned roles such that relationships are preserved: each
person playing a particular role has among its neighbors exactly the roles prescribed by the model. In this way, a large
network of individuals can be compressed into a smaller network that still gives some description of the large network.
Role assignments are also useful in the area of distributed computing, in which one of the fundamental problems is to
arrive at a final configuration where all processors have been assigned unique identities. Chalopin et al. [4] show that,
under a particular communication model, this problem can be solved on a graph G representing the distributed system
if and only if G has no R-role assignment for any graph R with fewer vertices than G. Role assignments are useful in
topological graph theory as well, where a main question is which graphs G allow role assignments to planar graphs R [

ผลลัพธ์ (ไทย) 1:

Homomorphisms กราฟแบบ generalization ธรรมชาติของกราฟ colorings: homomorphism จากกราฟ G จะมีการทำกราฟบนจุดยอด k ถ้าและเฉพาะถ้า G k colorable Homomorphism จากกราฟ G = (VG, EG) กับกราฟR = (V R, ER) เป็นแมป: VG → V R ที่แผนที่ข้าง ๆ ของข้าง ๆ ของ R เช่น r(u)r(v) ∈ ERเมื่อ uv ∈ EG R homomorphism จาก G เพื่อ R เป็นเครื่อง surjective ถ้าต่อไปนี้เป็นจริงสำหรับ u ทุกจุดของ G: ในy ทุกบ้านของ r(u) ใน R มีน้อยบ้าน v ของคุณใน G กับ r(v) = y เรายังเรียก r เป็น R มีบทบาทกำหนด ดู Fig. 1 สำหรับตัวอย่างมากำหนดบทบาทในทฤษฎีพฤติกรรมทางสังคม [9,24] รุ่น R กราฟบทบาทหน้าที่และความสัมพันธ์และเราสามารถถามได้ถ้า บุคคลนั้นสามารถกำหนดบทบาทให้มีเก็บความสัมพันธ์สังคมกำหนด: แต่ละมีคนเล่นบทบาทเฉพาะในหมู่บ้านว่าบทบาทตามแบบจำลอง ด้วยวิธีนี้ ขนาดใหญ่เครือข่ายของบุคคลสามารถถูกบีบอัดเป็นเครือข่ายขนาดเล็กที่ยัง ให้คำอธิบายบางอย่างของเครือข่ายขนาดใหญ่นอกจากนี้ยังกำหนดบทบาทมีประโยชน์ในพื้นที่วางจำหน่ายคอมพิวเตอร์ ปัญหาพื้นฐานอย่างใดอย่างหนึ่งคือการมาที่การกำหนดค่าสุดท้ายที่ตัวประมวลผลทั้งหมดได้ถูกกำหนดรหัสประจำตัวเฉพาะ Chalopin et al. [4] แสดงว่าภายใต้รูปแบบการติดต่อสื่อสาร ปัญหานี้สามารถแก้ไขได้ในกราฟ G แทนระบบกระจายถ้าและเฉพาะถ้า G มี การมอบบทบาท R ไม่มีกราฟ R กับจุดยอดที่น้อยลงกว่ากำหนดบทบาทกรัมมีประโยชน์ในtopological ทฤษฎีกราฟเช่น คำถามหลักว่ากราฟ G ให้กำหนดบทบาท[ระนาบกราฟ R

ผลลัพธ์ (ไทย) 2:

กราฟ homomorphisms รูปแบบทั่วไปตามธรรมชาติของสีกราฟ: มี homomorphism จากกราฟ G
ไปยังรูปแบบของกราฟที่สมบูรณ์เกี่ยวกับจุดk ถ้าหาก G เป็น k-colorable homomorphism จากกราฟ G = (VG, EG) เพื่อกราฟ
R = (VR, ER) เป็นอาร์การทำแผนที่: VG → VR ที่แผนที่จุดที่อยู่ติดกันของ G เพื่อจุดที่อยู่ติดกันของ R คืออาร์ (มึง) อาร์ ( V) ∈ ER
เมื่อใดก็ตามที่ยูวี∈ EG งาน R homomorphism จาก G เพื่อ R คือในประเทศ surjective
ถ้าต่อไปนี้เป็นจริงสำหรับจุดสุดยอดยูจีทุกเพราะว่าทุกปีเพื่อนบ้านของอาร์(U) ในการวิจัยมีอย่างน้อยหนึ่งเพื่อนบ้านโวลต์ของท่านในจีอาร์ (V) y = นอกจากนี้เรายังเรียกเช่น R เป็น
R-บทบาทที่ได้รับมอบหมาย ดูรูป 1 สำหรับตัวอย่าง.
ได้รับมอบหมายบทบาทมาในทฤษฎีของพฤติกรรมทางสังคม [9,24] บทบาทรุ่น R กราฟบทบาทและความสัมพันธ์ของพวกเขาและสังคมได้รับเราสามารถถามว่าบุคคลที่สามารถกำหนดบทบาทดังกล่าวว่ามีความสัมพันธ์จะถูกเก็บไว้แต่ละคนมีบทบาทโดยเฉพาะอย่างยิ่งในหมู่ผู้มีเพื่อนบ้านว่าบทบาทที่กำหนดไว้ในรูปแบบ ด้วยวิธีนี้มีขนาดใหญ่เครือข่ายของบุคคลที่จะสามารถบีบอัดเป็นเครือข่ายขนาดเล็กที่ยังคงให้รายละเอียดบางส่วนของเครือข่ายขนาดใหญ่. ได้รับมอบหมายบทบาทยังมีประโยชน์ในพื้นที่ของคอมพิวเตอร์กระจายในที่หนึ่งของปัญหาพื้นฐานคือการมาถึงที่การกำหนดค่าการประมวลผลขั้นสุดท้ายที่ทุกคนได้รับมอบหมายอัตลักษณ์ที่ไม่ซ้ำกัน Chalopin et al, [4] แสดงให้เห็นว่าภายใต้รูปแบบการสื่อสารโดยเฉพาะอย่างยิ่งปัญหานี้สามารถแก้ไขได้บนกราฟG เป็นตัวแทนของระบบการกระจายและถ้าหากG ไม่เคยมีใครได้รับมอบหมาย R-บทบาท R กราฟใด ๆ ที่มีจุดน้อยกว่ากรัมการกำหนดบทบาทที่มีประโยชน์ ในทฤษฎีกราฟทอพอโลยีเช่นกันที่คำถามหลักคือกราฟG ซึ่งช่วยให้การกำหนดบทบาทกราฟระนาบ R [