Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Графтар теориясында, графтың домдық бөлінісі – графты бір-бірімен қиылыспайтын , , , жиындарына бөлу, мұнда әрбір Vi жиыны граф G үшін доминантты жиынтық болып табылады. Оң жақтағы сурет графтың домдық бөлінісін көрсетеді; мұнда доминантты жиынтық сары түсті төбелерден, жасыл түсті төбелерден және көк түсті төбелерден тұрады. Доматикалық сан – домдық бөліністің ең үлкен саны, яғни, бір-бірімен қиылыспайтын доминантты жиынтықтардың ең үлкен саны. Суреттегі графтың домдық саны 3-ке тең. Домдық санның кем дегенде 3 екенін көру оңай, себебі біз 3 өлшемді домдық бөлініс ұсындық. Домдық санның ең көп дегенде 3 екенін көрсету үшін, алдымен қарапайым жоғарғы шекараны қарастырайық.
In graph theory, a domatic partition of a graph is a partition of into disjoint sets , , , such that each Vi is a dominating set for G. The figure on the right shows a domatic partition of a graph; here the dominating set consists of the yellow vertices, consists of the green vertices, and consists of the blue vertices. The domatic number is the maximum size of a domatic partition, that is, the maximum number of disjoint dominating sets. The graph in the figure has domatic number 3. It is easy to see that the domatic number is at least 3 because we have presented a domatic partition of size 3. To see that the domatic number is at most 3, we first review a simple upper bound.
Жоғарғы шектері
Графтың ең төменгі дәрежесі болсын. Графтың доматикалық саны ең көп дегенде тең болады. Мұны мыналай қарастырайық: дәрежесі бар төбе және оның көршілерінен тұратын жиынды қарастырайық. Біз (1) әрбір үстемдік жиынында кем дегенде бір төбе болуы керек екенін (үстемдік) және (2) әрбір төбе ең көп дегенде бір үстемдік жиынында болуы керек екенін (біртіндеп бөліну) білеміз. Сондықтан, ең көп дегенде үстемдік жиыны болуы мүмкін. Суреттегі графтың ең төменгі дәрежесі бар, сондықтан оның доматикалық саны ең көп дегенде 3-ке тең. Осылайша, оның доматикалық саны дәл 3 екенін көрсеттік; суретте максималды өлшемді доматикалық бөлініс көрсетілген.
Let be the minimum degree of the graph The domatic number of is at most To see this, consider a vertex of degree Let consist of and its neighbours. We know that (1) each dominating set must contain at least one vertex in (domination), and (2) each vertex in is contained in at most one dominating set (disjointness). Therefore, there are at most disjoint dominating sets. The graph in the figure has minimum degree , and therefore its domatic number is at most 3. Hence we have shown that its domatic number is exactly 3; the figure shows a maximum size domatic partition.
Төменгі шектер
Егер графикте оқшауланған төбе болмаса (яғни ≥ 1), онда домдық саны кем дегенде 2-ге тең. Мұны мынадан көруге болады: (1) оқшауланған төбе болмаса, әлсіз 2-бояу домдық бөлініс болып табылады, және (2) кез келген графтың әлсіз 2-бояуы болады. Басқаша айтқанда, (1) максималды тәуелсіз жиын – үстемдік жиын, және (2) максималды тәуелсіз жиынның толықтығы да оқшауланған төбелер болмаса, үстемдік жиын болып табылады. Оң жақтағы суретте әлсіз 2-бояу көрсетілген, ол сонымен қатар 2-өлшемді домдық бөлініс: қара түйіндер – үстемдік жиын, ал ақ түйіндер – тағы бір үстемдік жиын (ақ түйіндер максималды тәуелсіз жиынды құрайды). Толық ақпарат алу үшін әлсіз бояу туралы қараңыз.
If there is no isolated vertex in the graph (that is, ≥ 1), then the domatic number is at least 2. To see this, note that (1) a weak 2 coloring is a domatic partition if there is no isolated vertex, and (2) any graph has a weak 2 coloring. Alternatively, (1) a maximal independent set is a dominating set, and (2) the complement of a maximal independent set is also a dominating set if there are no isolated vertices. The figure on the right shows a weak 2 coloring, which is also a domatic partition of size 2: the dark nodes are a dominating set, and the light nodes are another dominating set (the light nodes form a maximal independent set). See weak coloring for more information.
Есептеу күрделілігі
1-өлшемді доматикалық бөлікті табу тривиалды: 2 өлшемді доматикалық бөлікті табу (немесе оның жоқ екенін анықтау) оңай: оқшауланған түйіндер бар-жоғын тексеріңіз, егер жоқ болса, 2-ден әлсіз түстің бояуын табыңыз. Дегенмен, максималды өлшемді доматикалық бөлікті табу есептеу жағынан қиын. Атап айтқанда, домдық сан проблемасы деп белгілі келесі шешімдік проблема NP-толық: граф пен бүтін санды берілгенде, графтың домдық саны кем дегенде екенін анықтаңыз. Сондықтан, берілген графтың домдық санын анықтау мәселесі NP-қиын, ал максималды өлшемді доматикалық бөлікті табу мәселесі де NP-қиын. Оптималдық факторының ішіндегі өлшемге ие доматикалық бөлікті табуға мүмкіндік беретін логарифмдік жуықтау кепілдігі бар полиномиалдық уақытты жуықтау алгоритмі бар. Алайда, ықтимал күрделілік теориялық болжамдар бойынша, сублогарифмдік жуықтау коэффициенті бар полиномиалдық уақытты жуықтау алгоритмі жоқ. Нақтырақ айтқанда, тұрақты үшін жуықтау коэффициентімен доматикалық бөлуге арналған полиномиалдық уақытты жуықтау алгоритмі NP-дегі барлық проблемаларды сәл суперполиномиалдық уақытта шешуге мүмкіндік береді.
Finding a domatic partition of size 1 is trivial: let Finding a domatic partition of size 2 (or determining that it does not exist) is easy: check if there are isolated nodes, and if not, find a weak 2 coloring. However, finding a maximum size domatic partition is computationally hard. Specifically, the following decision problem, known as the domatic number problem, is NP complete: given a graph and an integer , determine whether the domatic number of is at least Therefore, the problem of determining the domatic number of a given graph is NP hard, and the problem of finding a maximum size domatic partition is NP hard as well. There is a polynomial time approximation algorithm with a logarithmic approximation guarantee, that is, it is possible to find a domatic partition whose size is within a factor of the optimum. However, under plausible complexity theoretic assumptions, there is no polynomial time approximation algorithm with a sub logarithmic approximation factor. More specifically, a polynomial time approximation algorithm for domatic partition with the approximation factor for a constant would imply that all problems in NP can be solved in slightly super polynomial time .