Yazan : Şadi Evren ŞEKER
Graf teorisinde (graph theory) bir ağacın içerisinden bir kısmınkesilmesine dayalı işlemdir. Bir ağaç (tree) yada bir graf( graph) kesildiğinde tek bir kesilme ile iki parçaya ayrıldığı kabul edilir.
Bir kesitin boyutu kestiği kenar (edge) sayısı kadardır. Örneğin aşağıdaki kesitin boyutu 3’dür.
grafın ağırlıklı olması durumunda (weighted graph), kesitin boyutu, kestiği kenarların ağırlıkları topalmıdır.
Kesilme şekline göre bu ayrım iki grupta incelenebilir:
Asgari Kesit (Minimum Cut)
Bir grafı, iki parçaya bölen kesitin, en az kenarı kesmesi durumudur. Örneğin aşağıdaki grafta en az kesilebilen kenardan kesilmiştir. Bu kesilme dışındaki bütün kesitler bu kesitten daha yüksek veya aynı boyuttadır:
Yukarıdaki kesitin boyutu 2’dir ve yukarıdaki graf için boyutu 1 olan başka bir kesit bulunamaz.
Azami Kesit (Maximum Cut)
Kesitin, kesebildiği en fazla kenarı kesmesi durumudur. Aşağıdaki grafta bu durum gösterilmektedir:
Yukarıdaki kesitin boyutu 6’dır ve daha büyük boyutta bir kesit elde edilmesi mümkün değildir.