ในทฤษฎีกราฟการตัด (cut)คือการแบ่งจุดยอดของกราฟออกเป็นสองเซตย่อยที่ไม่ซ้ำกัน [ ^{1 ] การ}ตัดใดๆ จะกำหนดเซตของการตัด (cut-set)ซึ่งเป็นเซตของขอบที่มีจุดปลายหนึ่งจุดในแต่ละเซตย่อยของการแบ่ง ขอบเหล่านี้เรียกว่า ตัดผ่านการตัด (cross the cut) ในกราฟที่เชื่อมต่อกันเซตของการตัดแต่ละเซตจะกำหนดการตัดที่ไม่ซ้ำกัน และในบางกรณี การตัดจะถูกระบุด้วยเซตของการตัดมากกว่าการแบ่งจุดยอด

ในเครือข่ายการไหล การตัด แบบs–tคือการตัดที่กำหนดให้แหล่งกำเนิดและปลายทางอยู่ในเซตย่อยที่แตกต่างกัน และเซตของการตัด นั้น ประกอบด้วยขอบที่เชื่อมจากฝั่งแหล่งกำเนิดไปยังฝั่งปลายทางเท่านั้นความจุของการตัดแบบ s–t ถูกกำหนดให้เป็นผลรวมของความจุของแต่ละขอบในเซตของการตัด

คัทC = ( S , T )คือการแบ่งส่วนVของกราฟG = ( V , E )ออกเป็นสองเซตย่อยSและTเซตคัทของคัทC = ( S , T )คือเซต{( u , v ) ∈ E | u ∈ S , v ∈ T }ของขอบที่มีจุดปลายด้านหนึ่งอยู่ในSและจุดปลายอีกด้านหนึ่งอยู่ในTถ้าsและtเป็นจุดยอดที่กำหนดไว้ของกราฟGแล้วคัทs – tคือคัทที่s อยู่ในเซตSและtอยู่ในเซตT

ในกราฟแบบไม่มีทิศทางและไม่มีน้ำหนักขนาดหรือน้ำหนักของการตัดคือจำนวนขอบที่ตัดผ่านการตัดนั้น ในกราฟแบบมีน้ำหนักค่าหรือน้ำหนักจะถูกกำหนดโดยผลรวมของน้ำหนักของขอบที่ตัดผ่านการตัดนั้น

พันธะคือเซตตัดที่ไม่มีเซตตัดอื่นใดเป็นเซตย่อยที่ แท้จริง

การตัดจะถือว่าน้อยที่สุดหากขนาดหรือน้ำหนักของการตัดนั้นไม่มากกว่าขนาดของการตัดอื่นๆ ภาพประกอบทางด้านขวาแสดงการตัดที่น้อยที่สุด: ขนาดของการตัดนี้คือ 2 และไม่มีการตัดขนาด 1 เนื่องจากกราฟไม่มีสะพานเชื่อม

ทฤษฎีบทการไหลสูงสุด-การตัดขั้นต่ำพิสูจน์ว่าการไหลสูงสุดของเครือข่ายและผลรวมของน้ำหนักขอบตัดของการตัดขั้นต่ำใดๆ ที่แยกแหล่งกำเนิดและปลายทางนั้นเท่ากัน มี วิธีการ ใช้เวลาพหุนามในการแก้ปัญหาการตัดขั้นต่ำ โดยเฉพาะอย่างยิ่งอัลกอริทึม Edmonds– Karp ^{[ 2 ]}

การตัดจะมีขนาดใหญ่ที่สุดก็ต่อเมื่อขนาดของการตัดนั้นไม่น้อยกว่าขนาดของการตัดอื่นๆ ภาพประกอบทางด้านขวาแสดงการตัดที่มีขนาดใหญ่ที่สุด: ขนาดของการตัดเท่ากับ 5 และไม่มีการตัดที่มีขนาด 6 หรือ | E | (จำนวนขอบ) เนื่องจากกราฟไม่ใช่กราฟสองส่วน (มีวัฏจักรคี่ )

โดยทั่วไป การหาค่าตัดสูงสุดนั้นยากในเชิงการคำนวณ^{[ 3 ]} ปัญหาค่าตัดสูงสุดเป็นหนึ่งใน21 ปัญหา NP-complete ของ Karp [ ^{4 ] ปัญหา} ค่าตัดสูงสุดยังเป็นปัญหาAPX-hardซึ่งหมายความว่าไม่มีแผนการประมาณค่าในเวลาพหุนามสำหรับปัญหานี้ เว้นแต่ว่าP = NP [ ^{5 ] อย่างไรก็ตาม} สามารถประมาณค่าได้ภายในอัตราส่วนการประมาณค่า คงที่ โดยใช้ การ เขียนโปรแกรมแบบกึ่งกำหนด^{[ 6 ]}

โปรดทราบว่า min-cut และ max-cut ไม่ใช่ ปัญหาคู่กัน ในแง่ของ การเขียนโปรแกรมเชิงเส้นแม้ว่าการเปลี่ยน min เป็น max ในฟังก์ชันวัตถุประสงค์ จะทำให้ได้ปัญหาหนึ่งไปอีกปัญหาหนึ่งก็ตาม ปัญหาmax-flowเป็นปัญหาคู่กันของปัญหาmin-cut ^{[ 7 ]}

ปัญหาการตัดที่เบาบางที่สุดคือการแบ่งจุดยอดออกเป็นสองส่วนเพื่อลดอัตราส่วนของจำนวนขอบที่ตัดผ่านจุดยอดหารด้วยจำนวนจุดยอดในครึ่งส่วนที่เล็กกว่าของการแบ่งส่วน ฟังก์ชันวัตถุประสงค์นี้สนับสนุนโซลูชันที่ทั้งเบาบาง (มีขอบที่ตัดผ่านจุดยอดน้อย) และสมดุล (ใกล้เคียงกับการแบ่งครึ่ง) ปัญหานี้เป็นที่ทราบกันว่าเป็นปัญหา NP-hard และอัลกอริทึมการประมาณที่ดีที่สุดที่ทราบคือการประมาณจากArora, Rao & Vazirani (2009 ) ^{[ 8 ]}${\displaystyle O({\sqrt {\log n}})}$

ตระกูลของเซตตัดทั้งหมดของกราฟแบบไม่มีทิศทางเรียกว่าปริภูมิตัดของกราฟ ปริภูมิตัดนี้ก่อตัวเป็นปริภูมิเวกเตอร์ เหนือ ฟิลด์จำกัดสององค์ประกอบของเลขคณิตโมดูลสอง โดยมีผลต่างสมมาตรของเซตตัดสองเซตเป็นการดำเนินการบวกเวกเตอร์ และเป็นส่วนเติมเต็มเชิงตั้งฉากของปริภูมิวัฏจักร^{[ 9 ] [ 10 ]}หากขอบของกราฟมีน้ำหนักเป็นบวกฐาน น้ำหนักต่ำสุด ของปริภูมิตัดสามารถอธิบายได้ด้วยต้นไม้บนเซตจุดยอดเดียวกันกับกราฟ เรียกว่าต้นไม้โกโมรี-ฮู^{[ 11 ]}ขอบแต่ละขอบของต้นไม้นี้เกี่ยวข้องกับพันธะในกราฟดั้งเดิม และการตัดขั้นต่ำระหว่างโหนดsและt สองโหนด คือพันธะน้ำหนักต่ำสุดในบรรดาพันธะที่เกี่ยวข้องกับเส้นทางจากsไปยังtในต้นไม้

• การเชื่อมต่อ (ทฤษฎีกราฟ)
• การตัดกราฟในคอมพิวเตอร์วิชั่น
• แยก (ทฤษฎีกราฟ)
• ตัวคั่นจุดยอด
• สะพาน (ทฤษฎีกราฟ)
• ความกว้างในการตัด
• ไดคัท