Please enable JavaScript.

Coggle requires JavaScript to display documents.

UNIT 5 (Module05 กราฟแบบระนาบ (Planar Graph) (นิยามที่ 5.21 **…

- - - - กราฟคืออะไร?
        
        โครงสร้างที่แยกส่วนอย่างชัดเจน(Discrete structure) ซึ่งประกอบจุดด้วย (vertices) และเส้นเชื่อม (edges) ที่ต่อจุดต่างๆเข้าด้วยกัน
        
        ชนิดของกราฟ
        
        Simple graph
        
        Multigraph
        
        Peseudograph
        
        Directed Graph
        
        Directed Multigraph
- - - - นิยามที่ 5.12
        ให้ n เป็นจำนวนเต็มบวกและ G เป็นกราฟแบบไม่มีทิศทาง ทางเดินที่มีความยาว
        n จากจุด u ไปยัง v ในกราฟ G คือ
        
        ลำดับของเส้นเชื่อมจำนวน n เส้น คือ e1, e2 , . . ., en ของ G
        
        ซึ่ง f(e1) = {x0, x1}, f(e2) = {x1, x2}, . . .,f(en) = {xn-1, xn} โดยที่ x0 = u และ xn =v
      - นิยามที่ 5.13
        
        ทางเดินที่เริ่มต้นและจบที่จุดเดียวกันเรียกว่า “วงจร (Circuit)”
      - นิยามที่ 5.14
        
        ทางเดินหรือวงจรจะเรียกว่าเป็น “ทางเดินแบบง่าย (Simple path) หรือวงจรแบบง่าย (Simple circuit)” เมื่อผ่านเส้นเชื่อมเดียวกันแค่ 1 ครั้งเท่านั้น
    - - นิยามที่ 5.15
        
        กราฟแบบไม่มีทิศทางจะกล่าวว่า “ถูกเชื่อมต่อกัน (connected)” ถ้ามีทางเดินระหว่างทุกๆ คู่ของจุดในกราฟ
      - กราฟที่ไม่เชื่อมต่อกัน
        
        ประกอบด้วย connected subgraphs ตั้งแต่ 2 subgraphs ขึ้นไป
        
        แต่ละ connected subgraphs จะเรียกว่า "Connected components" ของกราฟ
    - - นิยามที่ 5.16
        กราฟแบบมีทิศทางจะเป็น strongly connected ถ้ามีทางเดินจาก a ไป b และ
        จาก b ไป a เมื่อใดก็ตามที่ a และ b เป็นจุดในกราฟ
      - นิยามที่ 5.17
        กราฟแบบมีทิศทางจะเป็น weakly connected ถ้ามีทางเดินระหว่างทุกๆ คู่
        ของจุดในกราฟ โดยไม่สนใจทิศทาง
- - - - u adjacent to v และ v adjacent from u
        เรียกจุด u ว่า จุดเริ่มต้น (initial vertex) ของ (u, v)
      - เรียก v ว่าเป็น จุดปลาย (terminal or end vertex) ของ (u, v)
      - ซึ่งในกรณีของ loop ทั้งจุดเริ่มต้นและจุดปลายจะเป็นจุดเดียวกัน
    - - :<3: จุด 2 จุด คือ u และ v ในกราฟแบบไม่มีทิศทาง G จะเรียกว่า adjacent (หรือ
        neighbors) ถ้า {u, v} เป็นเส้นเชื่อมของ G และถ้า e = {u, v}
        เส้นเชื่อม e ว่า incident กับจุด u และ v อาจกล่าวว่าเส้นเชื่อม e connect u และ v
        โดยจุด u และ v จะเรียกว่าเป็น endpoints ของเส้นเชื่อม {u, v}
    - - :<3:Degree ของจุดๆ หนึ่งในกราฟแบบไม่มีทิศทาง คือ จำนวนของเส้นเชื่อมที่ต่อกับ
        จุดนั้นๆ กรณี loop ที่จุดนั้นจะนับ degree เป็น 2 โดย degree ของจุด v เขียน
        แทนด้วย deg (v)
        จุดที่มี degree = 0 เรียกว่า "Isolated".
        จุดที่มี degree = 1 เรียกว่า "Pendant".