Please enable JavaScript.

Coggle requires JavaScript to display documents.

กราฟ(Graph) (การเชื่อมต่อ (ทางเดิน (Paths) การเชื่อมต่อกันในกราฟแบบไม่มีทิ…

- - - - ให้ทุกๆจุดเป็น อินฟินิตี้
        L(a) = 0
        L(a,b) = 4
        :check:L(a,c) = 2
        :check:L(a,c,b) = 3
        L(a,c,d) = 10
        L(a,c,e) = 12
        L(a,c,b,d) = 8
        :check:L(a,c,b,d,e) = 14
        L(a,c,b,d,z) = 10
        :red_flag:L(a,c,b,d,e,z) = 13
- - - - จุด (Vertices)
      - เส้นเชื่อม(edges)
    - - Simple Graph
        ประกอบด้วย
        
        V เป็นเซตของจุด ที่ไม่ใช้เซ็ตว่าง
        
        E เป็นเซ็ตของ Undordered pairs ของสามชิกแต่ละสมาชิกของ V เรียกมันว่าเส้นเชื่อม
      - Multigraph
        ประกอบด้วย
        
        V ซึ่งเป็นเซตของจุด และ
        
        E ซึ่งเป็นเซตของเส้นเชื่อม และ
        
        ฟังก์ชัน f จาก E ไปยัง {{u, v} | u, v ∈ V, u ≠ v} แล้ว
        
        เส้นเชื่อม e1 และ e2 จะเรียกว่า multiple หรือ parallel edges ถ้า f(e1) = f(e2)
      - Pseudograph
        ประกอบด้วย
        
        V ซึ่งเป็นเซตของจุด และ
        
        E ซึ่งเป็นเซตของเส้นเชื่อม และ
        
        ฟังก์ชัน f จาก E ไปยัง {{u, v} | u, v ∈ V}
        
        โดยเส้นเชื่อมจะเป็น loop ถ้า f(e)={u,u}={u} สําหรับบางค่าของ u ∈ V
      - Directed Graph
        ประกอบด้วย
        
        V ซึ่งเป็นเซตของจุด และ
        
        E ซึ่งเป็นคู่ลําดับของสมาชิกของ V
      - Directed Multigraph
        ประกอบด้วย
        
        V ซึ่งเป็นเซตของจุด และ
        
        E ซึ่งเป็นเซตของเส้นเชื่อม และ
        
        ฟังก์ชัน f จาก E ไปยัง {(u, v) | u, v ∈ V} แล้ว
        
        เส้นเชื่อม e1 และ e2 จะเรียกว่า multiple edges ถ้า f(e1) = f(e2)
    - - Complete graph
        Complete graph ที่มีจํานวน n จุด แทนด้วย Kn คือ
      - Cycle
        Cycle แทนด้วย Cn โดย n ≥ 3
        ประกอบด้วยจุดจํานวน n จุด คือ v1, v2, v3, ..., vn และมี
        edges {v1, v2}, {v2, v3}, . . .,{vn-1, vn}, และ {vn, v1}
      - Wheel
        Wheel แทนด้วย Wn จะได้มาจาก
        การเพิ่มจุดเข้าไปใน Cn (n ≥ 3) และเชื่อมต่อจุดใหม่นี้ไปยังแต่ละจุดเดิมใน Cn
      - n-Cube
        n-Cube หรือลูกบาศก์ n มิติแทนด้วย Qn คือ
        กราฟที่มีจุดต่างๆ ซึ่งใช้แสดง bit string จํานวน 2n
        bit strings โดยที่ n คือ
        จํานวนบิต ซึ่ง 2 จุดใดๆ จะต่อกันก็ต่อเมื่อ bit string ที่ใช้แสดงจุดนั้นต่างกัน 1
        บิต
- - - - จะคล้ายกันก็ต่อเมื่อกราฟรูปหนึ่งสามารถเปลี่ยนเป็นกราฟอีกรูปหนึ่งได้โดย
        
        การแทนเส้นเชื่อมที่มีอยู่ด้วยเส้นเชื่อมหลายๆ เส้นต่ออนุกรมกัน (คือ การเติมจุดซึ่งมีดีดรีเท่ากับสองในเส้นเชื่อมเดิม) หรือ
        
        การรวมเส้นเชื่อมหลายๆ เส้นที่ต่ออนุกรมกันเป็นเส้นเชื่อมเดียวกัน (คือการลบจุดเดิมที่มีดีกรีเป็น 2 ออก)
    - - ลบเส้นเขื่อมแบบลูปออก
        
        รวมเส้นเชื่อมที่ต่อแบบอนุกรมกันเป็นเส้นเชื่อมเดียว
        
        ลบเส้นเชื่อมที่ขนานกันระหว่างคู่ของจุดออกให้เหลือเพียง 1 เส้น
        
        ค้นหาและวาดวงจรแบบง่ายซึ่งใช้เส้นเชื่อมมากที่สุด
        
        วาดเส้นเชื่อมและจุดที่เหลือซึ่งไม่ไ้อยู่ในวงจรแบบง่ายโดยพยายามหลีกเลี่ยงการตัดกัน
        
        หากไม่สามารถหลีกเลี่ยงได้ ก็ให้หากราฟย่อยที่คล้ายกับรูป K5 หรือ K3,3 เพื่อยืนยันว่ากราฟดังกล่าวเป็นกราฟแบบไม่ระนาบ
        
        ตัวอย่างกราฟ
    - - นิยามที่ 5.21
        
        การให้สีกราฟ คือ การกำหนดสีให้แต่ละจุดของกราฟโดย 2 จุดที่เชื่อมติดกัน (adjacent) ต้องไม่มีสีเดียวกัน
        
        การให้สีกราฟนั้นจะพยายามใช้สีห้น้อยที่สุด จำนวนสีอย่างน้อยที่ต้องใช้ในการให้สีกราฟใดๆ เรียกว่า "Chromatic number of a graph"
        
        การประยุกต์ใช้งาน แก้ปัญหาที่เกี่ยวข้องกับการจัดตารางและกำหนดต่าง
        
        ตัวอย่างที่ 22 Chromatic Number ของกราฟ G และ H
        
        ตัวอย่างที่ 23 chromatic number
      - การประยุกต์ใช้
        
        ในการจัดตารางสอนของภาควิชาครุศาสตร์วิศวกรรมซึ่งมี
        จํานวนวิชาที่จะจัดทั้งหมด 6 วิชา คือ a, b, c, d, e และ f
        มีบางคู่วิชาที่ไม่สามารถสอนพร้อมกันได้เนื่องจากมีนักศึกษาลงทะเบียนเรียนทั้ง
        2 วิชานั้น ได้แก่ วิชา a กับ b, b กับ c, c กับ a, a กับ d, b กับ d, d กับ c,
        และ e กับ f
        ภาควิชาจะจัดตารางสอนเฉพาะช่วงบ่ายเท่านั้น
        จงหาจํานวนวันที่น้อยที่สุดในการสอน 6 วิชานี้
        
        ตอบ