Proceeding2562

1490 การประชุมวิชาการระดับชาติมหาวิทยาลัยทักษิณ ครั้งที่ 29 ประจ�ำปี 2562 วิจัยและนวัตกรรมเพื่อการพัฒนาที่ยั่งยืน บทนา กราฟ ( ( ), ( )) G V G E G  ประกอบด้วยเซตของจุดยอดคือ   V G และ เซตของเส้นเชื่อมคือ   E G กาหนดให้ จุดยอด u และ v เป็นจุดในกราฟ G และส้นเชื่อม e uv  เป็นเส้นเชื่อมในกราฟ G จะกล่าวว่า จุดยอด u ประชิดกับจุด ยอด v เส้นเชื่อม e กระทบกับจุด u และเส้นเชื่อม e กระทบกับจุด v เส้นเชื่อม e เชื่อมจุดยอด u และจุดยอด v ดีกรี ของจุดยอด v ในกราฟ G คือจานวนเส้นที่กระทบกับจุดยอด v ในกราฟ G ซึ่งเขียนแทนด้วย G deg v เรียกจุด v ว่าจุด เพนเด็นท์ ถ้าดีกรีของจุดยอด v เท่ากับ 1 ย่านใกล้เคียงของจุดยอด v ในกราฟ G ซึ่งเขียนแทนด้วย   N v คือเซตของจุด ยอดทั้งหมดที่ประชิดกับจุดยอด v ในกราฟ G นั่นคือ       { | } N v u V G uv E G    เส้นเชื่อมที่เชื่อมจุดยอดเพียงจุดเดียว เรียกว่า วงวน (loop) เส้นเชื่อมตั้งแต่ 2 เส้นที่เชื่อมระหว่างจุดยอดคู่เดียวกัน เรียกว่า เส้นเชื่อมขนาน กราฟที่ไม่มีเส้นเชื่อมขนานและไม่มีวงวนปรากฏอยู่ เรียกว่ากราฟเชิงเดียว วิถี u v  ในกราฟ G คือ ลาดับ ของจุดยอดและเส้นเชื่อมในกราฟ G เริ่มต้นด้วยจุดยอด u สิ้นสุดด้วยจุดยอด v และจุดยอดต้องไม่ซ้ากัน ถ้าทุกๆ สองจุด ยอดในกราฟ G มีวิถีถึงกัน แล้วจะเรียกกราฟ G ว่ากราฟเชื่อมโยง ถ้ากราฟ G มีเส้นเชื่อม q เส้น ถ้า f เป็นฟังก์ชันหนึ่งต่อหนึ่งจากเซต   V G ไปยังเซต   1,2,3,  แล้ว เราจะ กล่าวว่า f เป็นการกากับของกราฟ G และเรียก   1,2,3,  ว่าเซตกากับของจุดยอดใน G กราฟที่กากับจุดยอดไว้ เรียกว่า กราฟกากับ จะเรียกฟังก์ชัน f ว่า การกากับแบบเกรซฟูล ของกราฟ G ถ้า     : 0,1,2, , f V G q   เป็น ฟังก์ชันหนึ่งต่อหนึ่ง และ     * : 1,2, , f E G q   เป็นฟังก์ชันหนึ่งต่อหนึ่งและทั่วถึงสาหรับทุกเส้นเชื่อม   e uv E G   กาหนดโดย       * f uv f u f v   เมื่อ     f u f v  คือ ค่าสัมบูรณ์ของ   f u ลบ   f v กราฟ G พร้อมด้วยการกากับแบบเกรซฟูล f จะเรียกว่า กราฟเกรซฟูล การกากับแบบเกรซฟุลนาเสนอโดย Rosa (1966) และขยายแนวคิดโดย Golomb (1972) กราฟวิถี n P คือกราฟเชื่อมโยงที่มี จานวนจุดยอด n จุด โดยที่ดีกรีของจุดยอดแต่ละจุดไม่เกิน 2 ดังนั้นกราฟวิถี n P จะมีจานวนเส้นเชื่อม 1 n  เส้น ตัวอย่างของกราฟวิถี n P เช่น งานวิจัยของ Rohan Cattell (2015) ได้ศึกษาพบว่ากราฟวิถี n P เป็นกราฟเกรซฟูล และจาการศึกษางานวิจัยของ Vaidya & Barasara (2012) ในงานวิจัยได้ศึกษาการสร้างกราฟใหม่ และหาการกากับหรับกราฟใหม่ จากการศึกษางานวิจัยของ Kaneria & Chudasama (2017) ในงานวิจัยได้สร้างกราฟใหม่โดยวิธีการทาซ้าจุดยอดบนกราฟเดิมด้วยเส้นเชื่อมใหม่ และหา การกากับแบบเกรซฟุลสาหรับกราฟใหม่ที่ได้ ดังนั้นจากการศึกษาข้างต้น ในงานวิจัยนี้ จึงมีแนวคิดในการสร้างกราฟใหม่ โดยวิธีการ 1) ทาซ้าจุดเพนเด็นท์บนก ราฟวิถี n P ด้วยเส้นเชื่อมใหม่ 2) ทาซ้าจุดกึ่งกลางบนกราฟวิถี n P ด้วยเส้นเชื่อมใหม่ และหาการกากับแบบเกรซฟูลสาหรับ กราฟใหม่ เพื่อแสดงว่ากราฟใหม่ที่ได้เป็นกราฟเกรซฟูล