Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Граф теориясында графтың ең аз қимасы немесе минималды кесу – бұл графтың төбелерін екі ажыратылған жиынға бөлу арқылы жасалатын, белгілі бір метрика бойынша минималды кесу (қима). Минималды кесу мәселесінің түрлері салмақты графтарды, бағытталған графтарды, терминалдарды және төбелерді екіден астам жиынға бөлуді қарастырады. Оң және теріс салмақтарды қабылдайтын салмақты минималды кесу мәселесін барлық салмақтардың таңбаларын өзгерту арқылы салмақты максималды кесу мәселесіне оңай түрлендіруге болады. ТОК
Partition of a graph by removing fewest possible edges
In graph theory, a minimum cut or min cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets) that is minimal in some metric. Variations of the minimum cut problem consider weighted graphs, directed graphs, terminals, and partitioning the vertices into more than two sets. The weighted min cut problem allowing both positive and negative weights can be trivially transformed into a weighted maximum cut problem by flipping the sign in all weights. TOC
Терминал түйіндері жоқ
Бағытталмаған, салмақты графтардағы, теріс емес салмақтармен шектелген ең аз қима (minimum cut) мәселесі Стоер-Вагнер алгоритмі арқылы полиномиалдық уақытта шешіледі. Граф салмақсыз болған жағдайда, Каргер алгоритмі қима табудың тиімді, кездейсоқ әдісін ұсынады. Бұл жағдайда ең аз қима, графтың жиек байланысына тең болады. Терминалдары жоқ ең аз қима мәселесінің жалпылама түрі – ең аз k қима, онда мақсат – мүмкіндігінше аз жиектерді жою арқылы графикті кем дегенде k байланысты компонентке бөлу. k-ның белгілі бір мәні үшін бұл мәселе полиномиалдық уақытта шешіледі, бірақ алгоритм үлкен k мәндері үшін тиімді емес.
The minimum cut problem in undirected, weighted graphs limited to non negative weights can be solved in polynomial time by the Stoer Wagner algorithm. In the special case when the graph is unweighted, Karger's algorithm provides an efficient randomized method for finding the cut. In this case, the minimum cut equals the edge connectivity of the graph. A generalization of the minimum cut problem without terminals is the minimum k cut, in which the goal is to partition the graph into at least k connected components by removing as few edges as possible. For a fixed value of k, this problem can be solved in polynomial time, though the algorithm is not practical for large k.
Терминал тораптарымен
Екі терминалдық түйін берілген кезде, олар көбінесе бастапқы нүкте және аяқтаушы нүкте деп аталады. Ағын желісінде, ең төменгі кесу бастапқы нүкте мен аяқтаушы нүктені бөліп, кесудің бастапқы нүкте жағынан аяқтаушы нүкте жағына бағытталған қабырғаларының сыйымдылықтарының жалпы сомасын азайтады. Максималды ағын – ең төменгі кесу теоремасында көрсетілгендей, осы кесудің салмағы берілген желіде бастапқы нүктеден аяқтаушы нүктеге жіберілетін ағынның ең жоғары мөлшеріне тең. Салмақты, бағытталмаған желіде, нақты бір түйіндер жұбын бір-бірінен бөліп, ең аз салмаққа ие кесуді есептеу мүмкін. Бұл мәселені әр мүмкін түйіндер жұбы үшін шешетін кесулер жүйесі, графиктің Гомори-Ху ағашы деп аталатын құрылымға біріктіріледі. Терминалдармен ең төменгі кесу мәселесінің жалпылама түрі – k терминалды кесу немесе көп терминалды кесу. Бұл мәселе NP-қиын, тіпті .
When two terminal nodes are given, they are typically referred to as the source and the sink. In a flow network, the minimum cut separates the source and sink vertices and minimizes the total sum of the capacities of the edges that are directed from the source side of the cut to the sink side of the cut. As shown in the max flow min cut theorem, the weight of this cut equals the maximum amount of flow that can be sent from the source to the sink in the given network. In a weighted, undirected network, it is possible to calculate the cut that separates a particular pair of vertices from each other and has minimum possible weight. A system of cuts that solves this problem for every possible vertex pair can be collected into a structure known as the Gomory–Hu tree of the graph. A generalization of the minimum cut problem with terminals is the k terminal cut, or multi terminal cut. This problem is NP hard, even for .
Қолданбалар
Графты бөлу проблемалары – комбинаторлық оптимизация проблемаларының бір тобы, онда граф екі немесе одан көп бөлікке бөлінеді, мұнда кесудің екі жағының мөлшерін теңестіру сияқты қосымша шектеулер қойылады. Сегментацияға негізделген объектілерді жіктеуді, сурет сегментациясына қолданылатын нормаланған минимумдық кесілім спектральдық кластерлеудің нақты жағдайы ретінде қарастыруға болады. Оны жалпы кластерлеу әдісі ретінде де пайдалануға болады, онда түйіндер метрикалық кеңістіктен алынған деректердің үлгілері деп есептеледі және қабырғалардың салмағы олардың арақашықтығын көрсетеді. Дегенмен, бұл көбінесе жоғары есептеу күрделілігіне байланысты тиімсіз болады. Максималды ағын-минималды кесілім теоремасына сәйкес, екі түйіннің минималды кесілім мәні олардың максималды ағын мәніне тең. Осы жағдайда, максималды ағын мәселесінде қолданылатын кейбір алгоритмдер осы мәселені шешу үшін де қолданылуы мүмкін.
Graph partition problems are a family of combinatorial optimization problems in which a graph is to be partitioned into two or more parts with additional constraints such as balancing the sizes of the two sides of the cut. Segmentation based object categorization can be viewed as a specific case of normalized min cut spectral clustering applied to image segmentation. It can also be used as a generic clustering method, where the nodes are data samples assumed to be taken from a metric space and edge weights are their distances. This is however often impractical due do the high computational complexity for
Due to max flow min cut theorem, 2 nodes' Minimum cut value is equal to their maxflow value. In this case, some algorithms used in maxflow problem could also be used to solve this question.
Ең аз кесу саны
Графиктердегі төбелер саны n болса, ең көп дегенде n-1 түрлі ең аз қима болуы мүмкін. Бұл шектеу тығыз, яғни n төбесі бар (жа simple) циклде дәл n ең аз қима болады.
A graph with vertices can at the most have distinct minimum cuts. This bound is tight in the sense that a (simple) cycle on vertices has exactly minimum cuts.