หลักทางคณิตศาสตร์ > ทฤษฎีกราฟ

บทนิยามของกราฟ

                กราฟ  เป็นเรื่องที่สำคัญเรื่องหนึ่งในสาขาวิชาวิยุตคณิต  (Discrete mathematics)  กราฟในที่นี้จะกล่าวถึงความสัมพันธ์ของจุด  และเส้นที่เชื่อมระหว่างจุด  เช่น  แผนที่ถนนเชื่อมระหว่างเมืองต่าง ๆ  แผนที่แสดงเส้นทางการบิน  และจากตัวอย่างการแก้ปัญหาโดยใช้จุดและเส้นเป็นแบบจำลองที่กล่าวมาข้างต้น  เป็นต้น  ซึ่งจะให้ความหมายดังนิยามต่อไปนี้

 

 

บทนิยาม  1          กราฟจำกัด  G  คือคู่อันดับ  (V(G))  ประกอบไปด้วยเซตจำกัด  2  เซต

                1.  V(G) เป็นเซตของจุดที่ไม่เป็นเซตว่าง ถ้าu เป็นสมาชิกใน V(G)  เรียก  u  ว่าจุด  (vertex)

                2.  E(G) เป็นเซตของเส้น ซึ่งเส้นแต่ละเส้น คือ  คู่ที่ไม่เป็นอันดับ  (unordered pair)  ของจุด             ที่เขียนอยู่ในรูป uv  เรียก  uv  ว่า เส้น  (edge)

 

บทนิยาม  2

                1.  เส้นที่มีจุดปลายทั้งสองเป็นจุดเดียวกัน เราเรียกว่า  วงวน  (loop)

                2.  เส้นตั้งแต่สองเส้นขึ้นไปที่เชื่อมจุดคู่เดียวกัน เราเรียกว่า  เส้นหลายชั้น (multiple edges)

                3.  กราฟที่ไม่มีเส้นหลายชั้นและไม่มีวงวน เราเรียกว่า  กราฟเชิงเดียว  (Simple graph)

 

บทนิยาม  3          กำหนดกราฟ G  =  (V(G), D(G))  และ  v Î V(G)  ระดับขั้น (degree)  ของ       v                              คือจำนวนเส้นใน E(G) ที่ตกกระทบกับจุด v  เราเขียน  deg(v) แทนระดับขั้นของ v

                                (จำนวนเส้น ใน  E(G)  ที่ตกกระทบกับจุด  v  คือ จำนวนเส้นใน  E(G)  ที่ออกจาก                              จุด  v  นั่นเอง)

                                ถ้า  deg(v)  เป็นจำนวนคู่       เราเรียก  v  ว่าจุดคู่  (even vertex)

                                ถ้า  deg(v)  เป็นจำนวนคี่       เราเรียก  v  ว่าจุดคี่  (odd vertex)

 

ทฤษฎีบท  1          ให้  G  =  (V(G), E(G))  แทนกราฟ  โดย  | V(G)|  =  p  และ  | E(G) |  =  q

                                ซึ่ง  V(G)  =  {v1, v2, ..., vp }  และ  E(G)  =  { e1, e2, ...., eq }  จะได้ว่า

                                                                                 P

                                                                                å  deg  (v i )        =   2| E(G) |

                                                                                i=1

บทแทรก  1           กราฟทุกกราฟจะมีจุดคี่เป็นจำนวนคู่

 

บทนิยาม  4          ให้  H  =  (V(H)), E(H))  และ  G  =  (V(G)), E(G))  เป็นกราฟใด ๆ

                                1.  ถ้า  V(H)  Ì  V(G)  และ  E(H)  Ì  E(G)

                                เรากล่าวว่า  H  เป็นสับกราฟ  (subgraph)  ของ  G

                                2.  ถ้า  H  เป็นสับกราฟของ  G  และ  V(H)  =  V(G)

                                เรากล่าวว่า  H  เป็นสับกราฟแผ่ทั่วถึง  (spanning subgraph)  ของ  G

                                3.  ถ้า  V(H)  =  V(G)  และ  E(H)  =  E(G)

เรากล่าวว่า  กราฟ  H  และกราฟ  G  เป็นกราฟเหมือนกัน  (identical)  เขียนแทน  H  =  G

 

บทนิยาม  5          ให้  G  =  (V(G), E(G))  เป็นกราฟใด ๆ                                                         (หน้า  19)

                1.  ถ้า  U  เป็นเซตของจุดที่ไม่เป็นเซตว่าง และเป็นสับเซตแท้ของ  V(G)  แล้ว  G – U  เป็นสับกราฟของ  G  ที่ได้จากการกำจัดจุดใน  U  และเส้นทุกเส้นที่ตกกระทบกับจุดแต่ละจุดใน  U

                2.  ถ้า  F  เป็นเซตของเส้นที่ไม่เป็นเซตว่าง  และเป็นสับเซตของ  E(G)  แล้ว  G – F  คือสับกราฟของ  G  ที่ได้จากการกำจัดเส้นใน  F  โดยที่ไม่มีผลต่อจุด

 

บทนิยาม  6          แนวเดิน (Walk)  W ในกราฟ G  คือ ลำดับสลับของจุดและเส้นของกราฟ  G  ดังนี้

                                            W    :     v0 , e1 , v1 , e2 , v2 , ....., vn-1 , en , vn

                ซึ่งเส้น  ei   มีจุดปลาย  คือ  vi-1   และ  vi    สำหรับ  1  £  i  £  n

 

บทนิยาม  7          ให้  v  เป็นจุดใด ๆ  ในกราฟ  G  และ  W  เป็นแนวเดินใน  G  โดยที่

                                            W   :   v    (ซึ่งมีความยาว  =  0)

                                เราเรียกแนวเดิน  W  ที่ไม่มีเส้น  (n = 0)  ว่าแนวเดินชัด  (trival walk)

 

บทนิยาม  8          ให้  u  และ  v  เป็นจุดใด ๆ  ในกราฟ  G

                เรากล่าวว่าแนวเดิน  u – v  เป็น แนวเดินปิด  (closed walk)  เมื่อ  u  =  v

                และ             แนวเดิน  u – v  เป็นแนวเดินเปิด  (open walk)   เมื่อ  u  ¹  v

 

บทนิยาม  9

                1.   ถ้าเส้นในแนวเดิน  u – v  ไม่ซ้ำกัน  เรากล่าวว่าแนวเดิน  u – v  เป็นรอยเดิน  (trail)

                2.   ถ้าจุดในแนวเดิน  u – v   ไม่ซ้ำกัน  เรากล่าวว่าแนวเดิน  u – v  เป็นวิถี  (path)

 

ทฤษฎีบท  2          ให้  u  และ  v  เป็นจุดในกราฟ  G  ทุก ๆ  แนวเดิน  u – v  จะมีวิถี  u – v

 

บทนิยาม  10

                1.   เราเรียกรอยเดินปิดที่ไม่ใช่แนวเดินชัดว่า  วง  (circuit)

                2.   เราเรียก  วงที่มีจุดเริ่มต้น  และจุดภายในไม่ซ้ำกันว่า  วัฏจักร  (cycle)

 

 

 

 

บทนิยาม  11        เมทริกซ์ประชิด  (adjacency  matrix)

                ให้  V(G)  =  { v1 , v2 , ...., vn}  เป็นเซตของจุดในกราฟ  เมื่อ  n  =  | V(G)|  เมทริกซ์ประชิดของ  G  เขียนแทนด้วย  A(G)  จะเป็นเมทริกซ์มีมิติ  n x n  และ  A(G)  =  [aij ]  โดยที่  aij  เป็นจำนวนของเส้นที่เชื่อมจุด  vi  และ  vj

                                                                                                                                                                (หน้า  20)

ทฤษฎีบท  3          ให้  V(G)  =  { v1 , v2 , ... , vn}   เป็นเซตของจุดในกราฟ  G  และ  A  =  A(G)  เป็นเมทริกซ์ประชิดของ  G  แล้วสมาชิก  aij  ของ  Ak ,  k  ³  1  จะเป็นจำนวนของแนวเดิน  vi – vj   ที่มีความยาว  k  ที่แตกต่างกันใน  G

 

บทนิยาม  12        เมทริกซ์ตกกระทบ  (incidence  matrix)

                ให้  V(G)  =  { v1 , v2 , ... , vn}  และ  E(G)  =  { e1 , e2 , ... , em}   เป็นเซตของจุดและเซตของเส้นในกราฟ  G  เมื่อ  n  =  V(G)| และ  m  =  | E(G)|

                เมทริกซ์ตกกระทบ  (incidence  matrix)  ของกราฟ  G  เขียนแทนด้วย  I(G)  จะเป็นเมทริกซ์มีมิติ  n  x  m  และ  I(G)  =  [ xij ]  โดยที่  xij  เป็นจำนวนครั้งที่จุด  vi  ตกกระทบกับเส้น  ej  ซึ่ง  xij  มีค่าดังนี้

                                                         0   ถ้า  vi   ไม่เป็นจุดปลายของเส้น  ej

                                    xij     =          1   ถ้า  vi    เป็นจุดปลายของเส้น  ei  ที่ไม่เป็นวงวน

                                                         2   ถ้า  vi    เป็นจุดปลายของเส้น  ei  ที่เป็นวงวน

 

 

บทนิยาม  13        ให้  u  และ  v  เป็นจุดใด ๆ  ในกราฟ  G  เรากล่าวว่า  u  และ v  เชื่อมโยงกันได้  (connect)  เมื่อมีวิถี  u – v

13.1   ถ้ามีวิถีระหว่างจุดสองจุดใดๆ แล้วกราฟ G  เป็นกราฟเชื่อมโยง  (connected graph)

13.2   ถ้าไม่มีวิถีระหว่างจุดสองจุดใดๆ แล้วกราฟ G เป็นกราฟไม่เชื่อมโยง (disconnected graph)

 

บทนิยาม  14        ให้กราฟ G  เป็นกราฟเชื่อมโยง  และ  v  เป็นจุดในกราฟ  G  เรียก  จุด v  ว่า จุดตัด  (cut vertex)  ถ้ากราฟ  G – v  กลายเป็นกราฟไม่เชื่อมโยง

 

บทนิยาม  15        ให้กราฟ  G  เป็นกราฟเชื่อมโยง  และ  e  เป็นเส้นในกราฟ  G  เรียก  เส้น  e  ว่า เส้นตัด  (cut edge)  ถ้ากราฟ  G – e  กลายเป็นกราฟไม่เชื่อมโยง

 

บทนิยาม  16        เรากล่าวว่ากราฟ  G  เป็น  กราฟที่มีน้ำหนัก  เมื่อเส้นแต่ละเส้น  e  ใน  G  ถูกกำหนดด้วยจำนวนจริงที่ไม่เป็นลบ  และเราเรียกจำนวนจริงดังกล่าวนี้ว่า  น้ำหนักของเส้น  e  เขียนแทนด้วย  w(e)

 

บทนิยาม  17        ความยาวของวิถีในกราฟที่มีน้ำหนัก  G  คือ  ผลรวมของน้ำหนักของเส้นในวิถีนั้น

 

บทนิยาม  18        ให้  G  เป็นกราฟเชื่อมโยงที่มีน้ำหนัก  u  และ  v  เป็นจุดยอดใน  G  ระยะทาง  d(u, v)  คือ  ค่าความยาวของวิถี  u – v  ที่น้อยที่สุด

 

ทฤษฎีบท  1                                                                                                                                          (หน้า  21)

1.1   ถ้ากราฟ  G  มีวงวน  แล้วกราฟ  G  ไม่เป็นต้นไม้

1.2   ถ้ากราฟ  G  เป็นต้นไม้  แล้วจุด  2  จุดใด ๆ  ใน  G  เชื่อมโยงกันได้ด้วย  วิถีเพียงวิถีเดียว

1.3   ถ้ากราฟ  G  เป็นต้นไม้  ที่มีจุด  n  จุด  แล้ว กราฟ  G  จะมีจำนวนเส้น  n – 1  เส้น

1.4   ถ้ากราฟ  G  เป็นต้นไม้  ที่มีจุด  n  >  1  กราฟ  G  จะมีจุดที่มีดีกรี  1  อย่างน้อย  2  จุด

 

บทนิยาม  1          ให้  G  เป็นกราฟเชื่อมโยง

เรากล่าวว่า  G  เป็นกราฟออยเลอร์  (Eulerian graph)  เมื่อ  G  มีรอยเดินปิดซึ่งผ่านเส้นทุกเส้นใน  G  และเรียกรอยเดินปิดดังกล่าวนี้ว่า  รอยเดินออยเลอร์หรือ  วงออยเลอร์  (Eulerian circuit)

 

 

ทฤษฎีบท  1          ให้  G  เป็นกราฟเชื่อมโยง  และ  | E(G) |  ³  1

จะได้ว่า  G  เป็นกราฟออยเลอร์  ก็ต่อเมื่อ  จุดทุกจุดใน  G  เป็นจุดคู่

 

บทนิยาม  2          ให้  G  เป็นกราฟเชื่อมโยง  เราเรียกรอยเดินเปิดใน  G  ว่า รอยเดินเปิดออยเลอร์  (Eulerian trail)  เมื่อรอยเดินดังกล่าวนี้ผ่านเส้นทุกเส้นใน  G

 

ทฤษฎีบท  2          ให้  G  เป็นกราฟเชื่อมโยง  G  มีรอยเดินเปิดออยเลอร์  ก็ต่อเมื่อ G  มีจุดที่เป็นจุดคี่ไม่เกิน  2  จุด  ยิ่งไปกว่านั้นจุดคี่เหล่านี้จะเป็นจุดเริ่มต้นและจุดปลายของรอยเดินเปิดออยเลอร์






หลักทางคณิตศาสตร์:    สัจพจน์ความบริบูรณ์ (Axiom of Completeness) | ค่าเชิงอนุพันธ์ |
ฟังก์ชันเอกซ์โพเนนเชียลและฟังก์ชันลอการิทึม | ความสัมพันธ์และฟังก์ชัน | กราฟของความสัมพันธ์ |
ลำดับ (Sequence) | ทฤษฎีกราฟ | Matrices