รงคเลขของเส้นเชื่อมของกราฟเชื่อมต่อในทฤษฎีกราฟ

Abstract

บทคัดย่อ
การวิจัยครั้งนี้มีจุดมุ่งหมาย คือ 1) เพื่อหาค่าขอบเขตที่เหมาะสมของรงคเลขของเส้นของกราฟเชื่อมต่อในพจน์ของรงคเลขของเส้นของกราฟต้นฉบับ 2) เพื่อหาค่ารงคเลขของเส้นเชื่อมของกราฟเชื่อมต่อสำหรับการเชื่อมด้วยลักษณะเฉพาะ 3) เพื่อจัดกำหนดการเชื่อมโยงในระบบเครือข่ายโดยใช้ทฤษฎีบทเกี่ยวกับการระบายสีเส้นเชื่อมในทฤษฎีกราฟที่ได้จากข้อ 1) และ 2) ผลการวิจัยพบว่าขอบเขตบนของรงคเลขของเส้นเชื่อมของกราฟเชื่อมต่อคือผลรวมของรงคเลขของกราฟต้นฉบับ และขอบเขตล่างของรงคเลขของเส้นเชื่อมของกราฟเชื่อมต่อคือ ค่ามากสุดของรงคเลขของกราฟต้นฉบับ และพบว่าเงื่อนไขสำหรับรอยเชื่อมกราฟต้นฉบับที่เป็นกราฟบริบูรณ์ที่เป็นเลขคู่และเลขคี่ค่ารงคเลขของเส้นเชื่อมเท่ากับผลรวมของรงคเลขของเส้นเชื่อมของกราฟต้นฉบับลดลง 1 หรือเพิ่มขึ้น 1 ตามลำดับนอกจากนั้น พบว่าการจัดกำหนดการเชื่อมโยงในระบบเครือข่าย โดยใช้ทฤษฎีบทเกี่ยวกับการระบายสีเส้นเชื่อมในทฤษฎีกราฟ ได้กราฟแทนระบบเครือข่ายโดยที่ จุดแทนช่วงเวลาที่ต้องการในการทำงาน ซึ่งจุดสองจุดใดๆ จะมีเส้นเชื่อมกันก็ต่อเมื่อ ช่วงเวลาที่ต้องการทำงานสิ่งเดียวกันคาบเกี่ยวกัน และการเชื่อมต่อกราฟมีการประยุกต์ให้กราฟที่ 1 แทนระบบเครือข่ายที่ 1 และกราฟที่ 2 แทนระบบเครือข่ายที่ 2 เส้นสองเส้นใดๆ จะให้สีต่างกันด้วยจำนวนสีเส้นเชื่อมที่น้อยที่สุด ก็ต่อเมื่อมีการทำงานสิ่งเดียวกันในช่วงเวลาที่คาบเกี่ยวกัน และจำนวนสีเส้นเชื่อมแทนจำนวนชิ้นงานที่เพียงพอต่อความต้องการ และประหยัดทรัพยากรภายในช่วงเวลาที่กำหนดตามช่วงของขอบเขตที่ได้จากทฤษฎีบทหลักเกี่ยวกับการระบายสีเส้นเชื่อม

คำสำคัญ: กราฟเชื่อมต่อรอยเชื่อม การระบายสีเส้นเชื่อม

Abstract

The purposes of this research are 1) to find bounds of the edge-chromatic numbers of welded graphs in terms of the edge-chromatic numbers of their original graphs, 2) to find values for the edge-chromatic numbers of welded graphs for specific welding, and 3) to find link scheduling in networks by using edge coloring in graph theory as of 1) and 2). The research results obtained are as follows: the upper bound for the edge-chromatic numbers of welded graphs is the sum of the edge-chromatic numbers of their original graphs, and the lower bound for which is the maximum of the edge-chromatic numbers of their original graphs. The conditions for complete patch of the edge-chromatic numbers for odd or even complete original graphs are the sums of their original graph edge-chromatic numbers plus or minus 1 respectively. Moreover, the applications of link scheduling in networks by using edge coloring in graph theory are: any two connected graphs represent a connection of two networks in which a vertex means a period of working time for a task. Any two vertices can be connected if and only if the periods of the task working time overlap each other; and, any two edges can be colored differently if and only if there is a task is effectively performed in the overlap bounded period, taking into account edge-chromatic numbers of welded graphs based on the principal theorem.

Keywords: Welded Graph, Patch, Edge Coloring