ผลต่างระหว่างรุ่นของ "Biconnectedness (ค่ายวันที่ 11 มีนาคม 2551)"
ไปยังการนำทาง
ไปยังการค้นหา
Cardcaptor (คุย | มีส่วนร่วม) |
Cardcaptor (คุย | มีส่วนร่วม) |
||
| แถว 3: | แถว 3: | ||
* เราเรียก edge <math>e\,</math> ว่าเป็น '''bridge''' ถ้าเราตัด <math>e\,</math> ออกจากกราฟแล้วจะทำให้กราฟเป็นกราฟไม่ต่อเนื่อง | * เราเรียก edge <math>e\,</math> ว่าเป็น '''bridge''' ถ้าเราตัด <math>e\,</math> ออกจากกราฟแล้วจะทำให้กราฟเป็นกราฟไม่ต่อเนื่อง | ||
* เรากล่าวว่า edge สอง edge ใดๆ อยู่ใน '''biconnected component''' เดียวกันก็ต่อเมื่อมี simple cycle ที่มี edge ทั้งสองนั้นอยู่ภายใน | * เรากล่าวว่า edge สอง edge ใดๆ อยู่ใน '''biconnected component''' เดียวกันก็ต่อเมื่อมี simple cycle ที่มี edge ทั้งสองนั้นอยู่ภายใน | ||
| + | |||
| + | จะเห็นได้ว่าความสัมพันธ์ "อยู่ใน biconnected component เดียวกัน" จะแบ่ง edge ออกเป็นกลุ่มๆ ซึ่งเราเรียกกลุ่มเหล่านั้นว่า biconnected component (นั่นแหละ) | ||
รุ่นแก้ไขเมื่อ 08:18, 12 มีนาคม 2551
กำหนด undirected graph ซึ่งเป็นกราฟต่อเนื่อง ใดๆ
- เราเรียก vertex ว่าเป็น articulation point ถ้่าเราตัด และ edge ที่ต่อกับมันทั้งหมดออกไปออกจากกราฟแล้วจะทำให้กราฟเป็นกราฟไม่ต่อเนื่อง
- เราเรียก edge ว่าเป็น bridge ถ้าเราตัด ออกจากกราฟแล้วจะทำให้กราฟเป็นกราฟไม่ต่อเนื่อง
- เรากล่าวว่า edge สอง edge ใดๆ อยู่ใน biconnected component เดียวกันก็ต่อเมื่อมี simple cycle ที่มี edge ทั้งสองนั้นอยู่ภายใน
จะเห็นได้ว่าความสัมพันธ์ "อยู่ใน biconnected component เดียวกัน" จะแบ่ง edge ออกเป็นกลุ่มๆ ซึ่งเราเรียกกลุ่มเหล่านั้นว่า biconnected component (นั่นแหละ)
