כאשר מדברים על מטריצת קבוצת חיתוך בגרף, בדרך כלל מדברים על מטריצת קבוצת חיתוך בסיסית. קבוצת חיתוך היא קבוצה מינימלית של ענפים של גרף מחובר כך שכאשר מסירים את הענפים הללו מהגרף, הגרף מתפצל לשני חלקים נפרדים שנקראים תת-גרפים והמטריצה של קבוצת החיתוך היא המטריצה המתקבלת על ידי לקיחת קבוצת חיתוך אחת בכל פעם בשורה. מטריצת קבוצת החיתוך מיוצגת בסימן [Qf].

שני תת-גרפים מתקבלים מהגרף על ידי בחירת קבוצות חיתוך המורכבות מהענפים [1, 2, 5, 6].
לכן, במילים אחרות ניתן לומר שהקבוצה הבסיסית של חיתוך של גרף נתון בהתייחס לעץ היא קבוצת חיתוך המורכבת מאחד הענפים של העץ והקישורים השאריים. הענפים הם הענפים של העץ והקישורים הם הענפים של הקואטוס.
לכן, מספר קבוצות החיתוך שווה למספר הענפים של העץ.
[מספר הענפים = N – 1]
כאשר, N הוא מספר הצמתים של הגרף או העץ הנ drown.
הכוונה של קבוצת החיתוך היא כזו כמו של ענף והיא נלקחת כחיובית.
ישנם כמה צעדים שצריך לעקוב אחריהם בעת רישום מטריצת קבוצת החיתוך. הצעדים הם כדלקמן-
צייר את הגרף של הרשת או המעגל הנתונים (אם ניתנים).
ואז צייר את העץ שלו. הענפים של העץ יהיו הענפים.
ואז צייר את הענפים השאריים של הגרף באמצעות קו נקודות. הענפים הללו יהיו קישורים.
כל ענף או ענף של העץ יוצרים קבוצת חיתוך עצמאית.
כתוב את המטריצה עם השורות jako קבוצות חיתוך והעמודות כענפים.
| ענפים ⇒ | 1 | 2 | 3 | . | . | b | |
| קבוצות חיתוך | |||||||
| C1 | |||||||
| C2 | |||||||
| C3 | |||||||
| . | |||||||
| . | |||||||
| Cn | |||||||
n = מספר קבוצות החיתוך.
b = מספר הענפים.
Qij = 1; אם הענף J נמצא בקבוצת החיתוך עם כוונה זהה לזו של ענף העץ.
Qij = -1; אם הענף J נמצא בקבוצת החיתוך עם כוונה הפוכה לזו של ענף העץ.
Qij = 0; אם הענף J אינו נמצא בקבוצת החיתוך.
דוגמה 1
צייר את מטריצת קבוצת החיתוך עבור הגרף הבא.
תשובה:
שלב 1: צייר את העץ עבור הגרף הבא.
שלב 2: עכשיו 식별 את קבוצת החיתוך. קבוצת החיתוך תהיה הצומת שמכילה רק ענף אחד ומספר כלשהו של קישורים.
כאן C2, C3 ו- C4 הן קבוצות חיתוך.
שלב 3: עכשיו צייר את המטריצה.