Графтардағы қабырғалар жиыны, кез келген төбеге кемінде бір қабырға тиеді. Минималды қабырға жабу мәселесі – компьютерлік ғылымдағы оптимизациялық есеп.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Графтың шеттерінің ішкі жиыны, кез келген түйінге кем дегенде бір шет тиісті. Графтар теориясында, графтың шет жабыны – бұл графтың әрбір төбесі жиынның кем дегенде бір шетімен байланысқан шеттер жиыны. Компьютерлік ғылымда, ең кішкентай шет жабу мәселесі – ең аз мөлшердегі шет жабынын табу мәселесі. Бұл жабу класына жататын оптимизациялық мәселе және оны полиномиалдық уақытта шешуге болады.
Subset of a graph's edges, to which every node is incident to at least one
In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an optimization problem that belongs to the class of covering problems and can be solved in polynomial time.
Анықтама
Формальды түрде, граф G-нің жиек жабыны – C жиектерінің жиынтығы, мұнда G-дегі әрбір төбе C-дегі кем дегенде бір жиекпен жанасады. C жиынтығы G төбелерін жабады. Келесі суретте екі графтың жиек жабынының мысалдары көрсетілген (C жиынтығы қызыл түспен белгіленген). Ең кішкентай жиек жабыны – ең аз санды жиек жабыны. Жиек жабу саны ρ(G) – ең кішкентай жиек жабынының мөлшері. Келесі суретте ең кішкентай жиек жабуларының мысалдары көрсетілген (қайтадан, C жиынтығы қызыл түспен белгіленген). Оң жақтағы суретте тек жиек жабыны ғана емес, сонымен қатар сәйкестік екеніне назар аударыңыз. Атап айтқанда, бұл толық сәйкестік: әрбір төбе М сәйкестігінде дәл бір жиекпен сәйкес келеді. Толық сәйкестік (бар болса) әрқашан ең кішкентай жиек жабыны болады.
Formally, an edge cover of a graph G is a set of edges C such that each vertex in G is incident with at least one edge in C. The set C is said to cover the vertices of G. The following figure shows examples of edge coverings in two graphs (the set C is marked with red). A minimum edge covering is an edge covering of smallest possible size. The edge covering number ρ(G) is the size of a minimum edge covering. The following figure shows examples of minimum edge coverings (again, the set C is marked with red). Note that the figure on the right is not only an edge cover but also a matching. In particular, it is a perfect matching: a matching M in which every vertex is incident with exactly one edge in M. A perfect matching (if it exists) is always a minimum edge covering.
Мысалдар
Барлық жиектер жиынтығы, егер 0 дәрежелі төбелер болмаса, жиек жабу болып табылады. Толық екі бөлікті Km,n графының жиек жабу саны max(m, n) тең.
The set of all edges is an edge cover, assuming that there are no degree 0 vertices. The complete bipartite graph Km,n has edge covering number max(m, n).
Алгоритмдер
Ең кіші жиекті жабуды көпмүшелік уақытта ең көп сәйкестікті тауып, оны барлық төбелер жабылып қалуы үшін ашкөздікпен кеңейту арқылы табуға болады. Келесі суретте ең көп сәйкестік қызыл түспен белгіленген; сәйкес келмейтін төбелерді жабу үшін қосылған қосымша жиектер көк түспен белгіленген. (Оң жақтағы суретте ең жоғары сәйкестік – толық сәйкестік болып табылады; сондықтан ол барлық төбелерді қамтиды және қосымша жиектердің қажеті жоқ.) Екінші жағынан, ең кіші төбелік жабуды табуға байланысты мәселе NP-қиын мәселе болып табылады. Суретті қарағанда, берілген ең төменгі жиек жабуы және ең жоғары сәйкестік үшін, және сәйкесінше жиектердің саны болатыны анық көрінеді: Расында, ең жоғары сәйкестік қамтылған, сондықтан жиектерді ең жоғары сәйкестіктің жиектеріне, төбелерді қамтитын және әрқайсысы бір төбеді жабатын басқа жиектерге бөлуге болады. Осылайша, барлық төбелерді қамтитындықтан, теңдік орындалады.
A smallest edge cover can be found in polynomial time by finding a maximum matching and extending it greedily so that all vertices are covered. In the following figure, a maximum matching is marked with red; the extra edges that were added to cover unmatched nodes are marked with blue. (The figure on the right shows a graph in which a maximum matching is a perfect matching; hence it already covers all vertices and no extra edges were needed.) On the other hand, the related problem of finding a smallest vertex cover is an NP hard problem. Looking at the image it already becomes obvious why, for a given minimum edge cover and maximum matching , letting and be the number of edges in and respectively, we have: Indeed, contains a maximum matching, so the edges of can be decomposed between the edges of a maximum matching, covering vertices, and the other edges that each cover one other vertex. Thus, as covers all of the vertices, we have giving the desired equality.