กราฟและเครือข่าย
Introduced| English | ไทย |
|---|---|
| graph/ɡræf/ | กราฟ |
| vertices/ˈvɜːtɪsiːz/ | จุดยอด |
| edges/ˈedʒɪz/ | edges |
| degree/dɪˈɡriː/ | ดีกรี |
| path/pæθ/ | Path |
| cycle/ˈsaɪkl/ | วัฏจักร |
| connected/kəˈnektɪd/ | เชื่อมต่อกัน |
| tree/triː/ | ต้นไม้ |
| weighted graph/ˈweɪtɪd ɡræf/ | กราฟที่มีน้ำหนัก |
| shortest path/ˈʃɔːtɪst pæθ/ | เส้นทางสั้นที่สุด |
โมเดลการเชื่อมต่อต้องมีสมมติฐาน
- กราฟ (graph) มี จุดยอด (vertices) และ เส้นเชื่อม (edges). ตัดสินใจว่าแทนอะไร และการเชื่อมต่อเป็นแบบมีทิศทาง น้ำหนัก หรือไม่มีทิศทาง
- ใบงานใช้กราฟ simple undirected ที่มีจำนวนจำกัดโดยไม่มี self-loops หรือเส้นเชื่อมซ้ำ ตำแหน่งการวาดไม่เปลี่ยนการเชื่อมต่อของมัน แต่ลูกศรหรือน้ำหนักของเส้นเชื่อมสามารถเปลี่ยนโมเดลทางคณิตศาสตร์ได้
นับการเชื่อมต่ออย่างสม่ำเสมอ
- Degree นับเส้นเชื่อมที่ติดกับจุดยอดในกราฟ simple undirected. Degree รวมเป็นสองเท่าของจำนวนเส้นเชื่อม ดังนั้นจึงต้องเป็นเลขคู่
- Path ตามการเชื่อมต่อ; Cycle กลับไปยังจุดเริ่มต้นโดยไม่ทำซ้ำจุดยอดอื่น กราฟเป็น connected เมื่อแต่ละจุดยอดเข้าถึงได้จากทุกจุดยอดอื่น
ใน simple undirected graph中没有 loops, สี่ edges เชื่อมต่อกับ vertex หนึ่ง What is its degree?
Degree ของมันคือ 4 จำนวน incident edges ภายใต้ nomenclature กราฟที่กำหนด
ต้นไม้ต้องมีสองคุณสมบัติ
- Tree เป็น connected และไม่มี cycle. Tree ที่มีจำนวนจำกัด n จุดยอดจะมี n ลบด้วย 1 เส้นเชื่อม
- การมี n ลบด้วย 1 เส้นเชื่อมเพียงอย่างเดียวไม่พิสูจน์ว่าเป็น tree: สามเหลี่ยมบวกองค์ประกอบสองจุดยอดที่แยกกันจะมีห้าจุดยอดและสี่เส้นเชื่อมแต่ disconnected และมี cycle
ต้นไม้มี vertices 4 ตัว它有几条edges?
Finite tree ที่มีสี่ vertices มี n − 1 = 3 edges การนับนี้ขึ้นอยู่กับกราฟว่าเป็น connected และ acyclic จริงๆ
ในเครือข่ายไม่Directedที่เชื่อมต่อกันและมีการต้นทุนของเส้นเชื่อมเป็นบวกอย่างเคร่งครัด ทำไมจึงไม่มีวงวนอยู่ในสับกราฟที่มีต้นทุนต่ำที่สุดซึ่งครอบคลุมทุกจุดยอด?
การลบเส้นเชื่อมใด ๆ จากวงวนจะรักษาการเชื่อมต่อไว้ได้และลดต้นทุนรวมลง เนื่องจากน้ำหนักของเส้นเชื่อมนั้นเป็นบวกอย่างเคร่งคร故此 cyclic subgraph ไม่อาจเป็นค่าต่ำสุดภายใต้สมมติฐานเหล่านี้
ถนนที่มีต้นทุนเป็นบวก. สำหรับเครือข่ายที่ connected ด้วยต้นทุนถนนที่เป็นบวก()(strictly positive), การลบเส้นเชื่อมจาก cycle ทิ้งไว้จะคงความ connected และลดต้นทุนลง ดังนั้น subgraph ที่ connects ทั้งหมดที่มีต้นทุนต่ำสุดคือ tree. เพื่อหาค่า minimum spanning tree, เลือกเส้นเชื่อมที่ connect ทุกจุดยอดโดยไม่เกิด cycle; การเลือกเส้นเชื่อมที่ราคาถูกที่สุด n ลบด้วย 1 แบบ Blindly อาจทิ้งองค์ประกอบที่แยกออกมาได้
เส้นทางสั้นที่สุดไม่ใช่ spanning tree
- Weighted graph ติดตั้งค่าที่กำหนดไว้ให้กับแต่ละเส้นเชื่อม Shortest path ลดทอนน้ำหนักเส้นทางระหว่างจุดปลายที่กำหนดให้
- Minimum spanning tree เชื่อมต่อทุกจุดยอดที่น้ำหนักรวมที่รวมเข้ามามีค่าต่ำสุดที่สุด เส้นทางสั้นที่สุดอาจมีเส้นเชื่อมมากกว่าเส้นทางตรงที่มีราคาแพง; ให้บวกน้ำหนักเข้าด้วยกันแทนที่จะนับจำนวนเส้นเชื่อม
จับคู่สถานการณ์แต่ละอย่างกับสิ่งที่ vertices และ edges ควรจะเป็น
การตัดสินใจว่า vertices แทนอะไรคือการสร้างโมเดล และนั่นคือจุดที่ได้คะแนน
การปิดขอบเปลี่ยนแปลงความเป็นไปได้ ในแผ่นงาน 4.5 พบเส้นทางที่มีน้ำหนัก 7 จากนั้นปิดขอบหนึ่งและตรวจสอบทางเลือกที่มีน้ำหนัก 9 อย่าใช้ผลรวมเดิมสำหรับเส้นทางที่หายไปแล้ว
สองภาพวาดที่ดูต่างกันต้องเป็นกราฟที่แตกต่างกัน
การจัดวางแบบต่าง ๆ อาจมี adjacency matrix ที่มีฉลากเหมือนกัน เมื่อตรวจสอบให้แน่ใจว่าต้องพิจารณาทั้งทิศทางและน้ำหนักด้วยหากสิ่งเหล่านั้นเป็นส่วนที่กำหนดของกราฟ
เปรียบเทียบโครงสร้างทั้งหมดที่เกี่ยวข้องกับคำถาม: ความสัมพันธ์ของจุดยอด, การเชื่อมต่อ, ทิศทาง และน้ำหนักเมื่อระบุไว้ ภาพที่ดูเหมือนกันอาจไม่ได้แทนกราฟเดียวกัน; การจัดวางที่แตกต่างกันสามารถแทนการเชื่อมต่อกันที่ติดป้ายได้เหมือนกัน