โจทย์ทฤษฎีกราฟครับ

[Suwiwat B]

นายกราฟเเละภรรยาไปงานเลี้ยงเเห่งหนึ่ง ซึ่งที่นั่นมีคู่สามีภรรยา 4 คู่ เเต่ละคนที่ไปงานเลี้ยงนี้จะทักทายสวัสดีกันโดยยกมือไหว้ ไม่มีใครยกมือไหว้คู่ของตนเอง เเละไม่ยกมือไหว้บุคคลเดียวกันเกินกว่า 1 ครั้ง ก่อนงานจะเลิก นายกราฟถามทุกคนรวมทั้งภรรยาของตนว่ายกมือไหว้กี่ครั้ง คำตอบที่ได้รับคือ จำนวนครั้งที่ยกมือไหว้ ของเเต่ละคนเเตกต่างกันหมด ถามว่าภรรยาของนายกราฟยกมือไหว้กีครั้ง

[Thgx0312555]

มีคน 8 คนยกมือ ไหว้ตัวเองกับภรรยาไม่ได้ ดังนั้นไหว้ได้มากสุด 6 ครั้ง
นั่นคือไหว้ได้ 0,1,2,3,4,5 หรือ 6 ครั้ง

แต่ทุกคนไหว้ไม่เท่ากันหมดเลย นั่นคือต้องมีคนนึงไหว้ 0 ครั้ง คนนึงไหว้ 1 ครั้ง...

พิจารณาคนไหว้ 0 กับ 6 ครั้ง
เนื่องจากคนไหว้ 6 ไหว้ทุกคนยกเว้นคู่ของตน แต่ 0 ไม่ได้ไหว้สักคนนั่นคือ 0 ไม่ได้ไหว้ 6 ด้วย
0 เป็นคู่กับ 6

พิจารณา 1 กับ 5
จะได้ว่า 5 ไม่ได้ไหว้ 0 กับคู่ของตน แต่ 1 ไหว้ 6 ไปแล้ว จึงไม่ได้ไหว้ 5 ด้วย
1 เป็นคู่กับ 5

ทำแบบเดียวกันได้ 2 คู่กับ 4
เหลือ 3

จึงได้ว่าภรรยาไหว้ 3 ครั้ง

[art_clex]

ถ้าไม่มีใครเป็นบุคคลระดับเดียวกับ ภรรยานายกราฟ อาจไหว้กี่ครั้งก็ได้ไม่ใช่เหรอครับ ??

[yellow]

คนอื่นๆ 7 คนยกเว้นนายกราฟ ยกมือไหว้จำนวนไม่ซ้ำกันตั้งแต่ 0, 1, 2, 3, 4, 5, 6 ครั้ง

จุดยอดมี 8 จุด เป็นจุดยอดคี่ 3 จุด นายกราฟจึงต้องยกมือไหว้เป็นจำนวนคี่ เพื่อทำให้จุดยอดคี่เป็นจำนวนคู่

เขียนเป็นกราฟ ดังรูป

1. จุดยอดที่มีดีกรี 3 มี 2 จุด ซึ่งจุดนึงต้องเป็นนายกราฟ

2. จุดยอดที่มีดีกรี 6 เป็นคู่นายกราฟไม่ได้ ต้องเป็นคนอื่น สมมติให้ชื่อ A

3. จุดยอดที่มีดีกรี 0 เป็นคู่ของ A สมมติให้ชื่อ a

4. จุดยอดที่มีดีกรี 5 เป็นคู่นายกราฟไม่ได้ ต้องเป็นคนอื่น สมมติให้ชื่อ B

5. จุดยอดที่มีดีกรี 1 เป็นคู่ของ B สมมติให้ชื่อ b

6. จุดยอดที่มีดีกรี 4 เป็นคู่นายกราฟไม่ได้ ต้องเป็นคนอื่น สมมติให้ชื่อ C

7. จุดยอดที่มีดีกรี 2 เป็นคู่ของ C สมมติให้ชื่อ c

8. จุดยอดที่มีดีกรี 3 เป็นคู่ของนายกราฟ

ภรรยานายกราฟยกมือไหว้ 3 ครั้ง