เมื่อเราพูดถึง เมทริกซ์เซตตัดในทฤษฎีกราฟ เราโดยทั่วไปจะพูดถึง เมทริกซ์เซตตัดหลัก เซตตัดคือเซตย่อยของกิ่งของ กราฟเชื่อมโยง ที่เมื่อลบกิ่งเหล่านี้ออกจากกราฟ กราฟจะถูกแบ่งออกเป็น 2 ส่วนย่อยที่เรียกว่า sub-graphs และเมทริกซ์เซตตัดคือเมทริกซ์ที่ได้จากการนำเซตตัดมาเรียงตามแถว เมทริกซ์เซตตัดแทนด้วยสัญลักษณ์ [Qf]

สอง sub-graphs ได้จากกราฟโดยเลือกเซตตัดประกอบด้วยกิ่ง [1, 2, 5, 6] ดังนั้น ในคำอื่น ๆ เราสามารถกล่าวได้ว่าเซตตัดหลักของกราฟที่กำหนดโดยอ้างอิงต้นไม้คือเซตตัดที่สร้างขึ้นด้วยหนึ่ง twig และลิงค์ที่เหลือ twigs คือกิ่งของต้นไม้และลิงค์คือกิ่งของ co-tree ดังนั้น จำนวนเซตตัดเท่ากับจำนวน twigs [จำนวน twigs = N – 1] โดยที่ N คือจำนวนโหนดของกราฟหรือต้นไม้ที่วาด การจัดเรียงของเซตตัดมีความเหมือนกับ twig และถูกมองว่าเป็นบวก
มีขั้นตอนบางอย่างที่ควรทำขณะวาดรูป เมทริกซ์เซตตัด ขั้นตอนดังนี้-
วาดกราฟของวงจรหรือวงจรที่กำหนด (ถ้ามี)
จากนั้นวาดต้นไม้ของมัน กิ่งของต้นไม้จะเป็น twig
จากนั้นวาดกิ่งที่เหลือของกราฟด้วยเส้นประ กิ่งเหล่านี้จะเป็นลิงค์
แต่ละกิ่งหรือ twig ของต้นไม้จะสร้างเซตตัดอิสระ
เขียนเมทริกซ์ด้วยแถวเป็นเซตตัดและคอลัมน์เป็นกิ่ง
| กิ่ง ⇒ | 1 | 2 | 3 | . | . | b | |
| เซตตัด | |||||||
| C1 | |||||||
| C2 | |||||||
| C3 | |||||||
| . | |||||||
| . | |||||||
| Cn | |||||||
n = จำนวนเซตตัด
b = จำนวนกิ่ง
Qij = 1; ถ้ากิ่ง J อยู่ในเซตตัดด้วยการจัดเรียงเดียวกับกิ่งของต้นไม้
Qij = -1; ถ้ากิ่ง J อยู่ในเซตตัดด้วยการจัดเรียงตรงข้ามกับกิ่งของต้นไม้
Qij = 0; ถ้ากิ่ง J ไม่อยู่ในเซตตัด
ตัวอย่าง 1
วาดเมทริกซ์เซตตัดสำหรับกราฟต่อไปนี้
คำตอบ:
ขั้นตอนที่ 1: วาดต้นไม้สำหรับกราฟต่อไปนี้
ขั้นตอนที่ 2: ระบุเซตตัด เซตตัดจะเป็นโหนดที่มีเพียง twig หนึ่งและลิงค์ใด ๆ จำนวนมาก
ที่นี่ C2, C3 และ C4 เป็นเซตตัด
ขั้นตอนที่ 3: วาดเมทริกซ์