Кіріспе
Графтың түйіндерін екі бөлек жиынға бөлу
Графтар теориясында, кесік – графтың төбелерін екі бөлек жиынға бөлу. Кез келген кесік кесік жиынын анықтайды, ол бөлудің әр жиынында бір ұшы бар жиектердің жиыны болып табылады. Бұл жиектер кесіктен өтеді деп айтылады. Байланысқан графта әр кесік жиыны бірегей кесікті анықтайды, ал кейбір жағдайларда кесіктер олардың төбелік бөліністерімен емес, кесік жиындарымен анықталады. Ағын желісінде, s–t кесігі – бұл бастапқы нүкте мен аяқтау нүктесін әртүрлі жиынға орналастыруды талап ететін кесік, ал оның кесік жиыны бастапқы нүктенің жағынан аяқтау нүктесінің жағына бағытталған жиектерден ғана тұрады. s–t кесігінің сыйымдылығы – кесік жиынындағы әр жиектің сыйымдылығының қосындысы ретінде анықталады.
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut set determines a unique cut, and in some cases cuts are identified with their cut sets rather than with their vertex partitions. In a flow network, an s–t cut is a cut that requires the source and the sink to be in different subsets, and its cut set only consists of edges going from the source's side to the sink's side. The capacity of an s–t cut is defined as the sum of the capacity of each edge in the cut set.
Анықтама
1=C = (S,T) кесіндісі – 1=G = (V,E) графигінің V жиынын S және T екі қосалқы жиынға бөлу. 1=C = (S,T) кесіндісінің кесінді жиыны – бір ұшы S жиынында, екінші ұшы T жиынында болатын жиектердің жиыны. Егер s және t графигі G-нің белгіленген төбелері болса, онда s–t кесіндісі – s жиыны S-қа, t жиыны T-ға кіретін кесінді.
The cut set of a cut 1=C = (S,T) is the set of edges that have one endpoint in S and the other endpoint in T.
If s and t are specified vertices of the graph G, then an s–t cut is a cut in which s belongs to the set S and t belongs to the set T.
Салмағы жоқ бағытталмаған графтарда кесіндінің өлшемі немесе салмағы – кесінді арқылы өтетін жиектердің саны. Салмақты графтарда мән немесе салмақ – кесінді арқылы өтетін жиектердің салмақтарының қосындысымен анықталады. Байланыс – өзінен кіші жиынтығы жоқ кесінді жиыны.
Ең аз кесу
Егер кесудің мөлшері немесе салмағы кез келген басқа кесудің мөлшерінен артық болмаса, онда кесу минималды деп есептеледі. Оң жақтағы суретте минималды кесу көрсетілген: осы кесудің мөлшері 2-ге тең, ал 1 мөлшерінде кесу жоқ, себебі графта көпірлер жоқ. Максималды ағым-минималды кесу теоремасы, желідегі максималды ағым мен бастапқы нүкте мен аяқтаушы нүктені бөлетін кез келген минималды кесудің кесу жиектері салмағының қосындысы тең екенін дәлелдейді. Минималды кесу мәселесін шешу үшін полиномиалдық уақытта жұмыс істейтін әдістер бар, олардың ішінде Эдмондс-Карп алгоритмі ең танымалдарының бірі.
Ең жоғарғы кесу
Егер кесудің мөлшері кез келген басқа кесудің мөлшерінен кем болмаса, онда кесу максималды болып саналады. Оң жақтағы сурет максималды кесуді көрсетеді: кесудің мөлшері 5-ке тең, ал 6 мөлшерінде немесе |E| (қабырғалар саны) кесу жоқ, себебі граф екі бөлікті емес (жұп емес цикл бар). Жалпы, максималды кесуді табу есептеу тұрғысынан қиын. Максималды кесу мәселесі – Карптың 21 NP-толық мәселесінің бірі. Максималды кесу мәселесі сонымен қатар APX-қиын, яғни P=NP болмаса, оған полиномиалдық уақытта жуықтау схемасы жоқ. Дегенмен, оны жартылай анықталған бағдарламалауды қолдана отырып, тұрақты жуықтау қатынасымен жуықтауға болады. Min cut және max cut сызықтық бағдарламалау мағынасында екілік проблемалар емес екенін ескеріңіз, тіпті мақсаттық функцияны өзгерту арқылы бір проблемадан екіншісіне көшуге болады (min-ді max-қа ауыстыру арқылы). Максималды ағын мәселесі – минималды кесу мәселесінің дуалы болып табылады.
Ең аз кесу
Ең сирек кесу мәселесі – төбелерді екіге бөлу, осылайша кесу арқылы өтетін жиектер санының, бөліністің кіші жартысының төбелер санына қатынасын азайту. Бұл мақсаттық функция сирек (кесу арқылы аз жиектер өтетін) және теңгерілген (екідік бөлуге жақын) шешімдерді жақсы көреді. Мәселе NP-қиын екені белгілі, ал ең жақсы танымал жуықтау алгоритмі – ғалымның жуықтауы.
Бос орынды кесу
Бағытталмаған графтың барлық кесу жиындарының жиыны графтың кесу кеңістігі деп аталады. Ол екі элементті шекті өріс үстінде векторлық кеңістік құрайды, мұнда арифметикалық амалдар екі модульдік есептеу бойынша орындалады, ал векторлық қосу операциясы – екі кесу жиынының симметриялық айырмасы. Бұл кеңістік циклдық кеңістіктің ортогональді толықтырғышы болып табылады. Егер графтың қабырғаларына оң салмақтар берілсе, кесу кеңістігінің ең төмен салмақты негізін сол графтың түйіндер жиынындағы ағаш арқылы сипаттауға болады, бұл Гомори-Ху ағашы деп аталады. Осы ағаштың әр қабырғасы бастапқы графтың байланысына сәйкес келеді, ал екі түйін s және t арасындағы ең төмен кесу – ағаштағы s-тен t-ге дейінгі жолға сәйкес келетін байланыстардың ең төмен салмақтысы болып табылады.