Рим доминациясы — графтын чокуларына коргонуу ресурсу катары чечмелене турган бүтүн сандык энбелгилерди берип, бардык чокулардын белгилүү коңшулук шарттарында корголушун камсыз кылуу менен бирге энбелгилердин жалпы салмагын минималдаштырууну көздөгөн графтык оптималдаштыруу модели. Juan Carlos Valenzuela-Tripodoro, María Antonia Mateos-Camacho, Martín Cera López жана María Pilar Álvarez-Ruíz жүргүзгөн изилдөө бул моделдин эки өнүккөн түрүн — [k]-Рим доминациясын жана күчтүү Рим доминациясын — эсептөө татаалдыгы жана айрым граф үй-бүлөлөрүндөгү параметрлердин так маанилери жагынан изилдейт.

[k]-Рим доминациясы боюнча авторлор маселени Linear Extended Monadic Second-Order Logic (LinEMSOL) формасында туюнтат. Мунун натыйжасында ылайыктуу графтык көрсөтүү бар болгондо, чектелген clique-width класстарында маселе графтын иретине карата сызыктуу убакытта чечилиши мүмкүн. Күчтүү Рим доминациясы жагында болсо чечим маселесинин жылдыз-конвекс эки бөлүктүү графтарда NP-толук экени Restricted Exact 3-Cover маселесинен курулган кыскартуу аркылуу көрсөтүлөт.

Изилдөөнүн экинчи негизги багыты — так маанилер. Кош жылдыздар, айрым жолдор жана циклдер, t-катмарлуу дөңгөлөктөр, таажы графтары, цикл менен жалгыз чокунун корона көбөйтүндүсү жана айрым курт сымал граф класстары үчүн [k]-Рим же күчтүү Рим доминация сандары аныкталат. Натыйжалар эксперименттик эмес; алар графтык энбелгилөөлөргө, комбинатордук төмөнкү жана жогорку чектерге, логикалык туюнтулууга, татаалдык кыскартууларына жана конструктивдүү далилдерге негизделет.

Рим доминациясы деген эмне?

Рим доминациясы графтын чокуларына 0, 1 же 2 энбелгилерин берип, 0 энбелгилүү ар бир чокунун жок дегенде бир 2 энбелгилүү коңшусу болушун талап кылган чоку-энбелгилөө оптималдаштыруу модели; максат — бардык энбелгилердин жалпы салмагын минималдаштыруу.

Жөнөкөй, багытталбаган жана чектүү граф

\[ G=(V,E) \]

менен белгиленсин. Бул жерде \(V\) чокулардын жыйындысын, \(E\) болсо кырлардын жыйындысын билдирет. Классикалык Рим доминация функциясы

\[ f:V\rightarrow\{0,1,2\} \]

түрүндө болот. Эгер \(f(v)=0\) болсо, \(v\) чокусунун жок дегенде бир коңшусу \(u\) үчүн

\[ f(u)=2 \]

болушу керек.

Функциянын салмагы

\[ w(f)=\sum_{v\in V}f(v) \]

түрүндө. Графтын Рим доминация саны

\[ \gamma_R(G) \]

болсо бардык жарактуу Рим доминация функцияларынын ичиндеги эң кичине салмак.

“Рим” аталышы тарыхый коргонуу окшоштугунан келип чыккан: 0 энбелгилүү позицияда түздөн-түз коргонуу бирдиги жок; бирок коңшу позицияда эки бирдик болсо, ал коңшу өз коргонуусун толук жоготпостон бир бирдикти жардамга жөнөтө алат. Математикалык жактан маанилүүсү тарыхый окуя эмес, графтагы жергиликтүү коргонуу шарттары менен жалпы ресурс чыгымын бирге оптималдаштыруу.

Коңшулук жана активдүү коңшулук

Бир \(u\) чокусунун ачык коңшулугу \(N(u)\) — \(u\) менен жанаша турган чокулардын жыйындысы. Жабык коңшулук болсо

\[ N[u]=N(u)\cup\{u\} \]

деп аныкталат.

Бир энбелгилөө \(f\) берилгенде активдүү коңшулук

\[ AN(u)=\{w\in N(u):f(w)>0\} \]

жыйындысы болуп саналат. Бул түшүнүк өзгөчө [k]-Рим доминациясынын аныктамасында борбордук роль ойнойт.

[k]-Рим доминациясы классикалык моделден кандай айырмаланат?

\[k]-Рим доминациясы ар бир чокуга \(0\) менен \(k+1\) ортосунда энбелги берүүгө уруксат берет жана ар бир чокунун жабык коңшулугундагы жалпы энбелги салмагын кеминде \(k\) плюс активдүү коңшулардын санына тең кылып, классикалык Рим доминациясын кыйла жалпы ресурс-бөлүштүрүү моделине айлантат.

Бир [k]-Рим доминация функциясы, кыскача [k]-RDF,

\[ f:V\rightarrow\{0,1,\ldots,k+1\} \\]

түрүндө аныкталат жана ар бир \(u\in V\) үчүн

\[ f(N[u])\geq k+|AN(u)| \]

шартын аткарышы керек.

Бул жерде

\[ f(N[u])=\sum_{v\in N[u]}f(v) \]

жабык коңшулуктагы энбелгилердин суммасы. \(|AN(u)|\) — \(u\) чокусунун оң энбелги алып жүргөн активдүү коңшуларынын саны. Демек талап кылынган минималдуу сумма \(k\) га гана эмес, ошол чокунун айланасында канча активдүү чоку бар экенине да көз каранды.

Графтагы минималдуу [k]-Рим доминация салмагы

\[ \gamma_{[kR]}(G) \]

менен белгиленет.

Булактын 1-сүрөтүндө бир эле графта классикалык Рим доминация энбелгилөөсү менен [k]-Рим энбелгилөөсү жанаша көрсөтүлөт. Мисалда классикалык маани

\[ \gamma_R(G)=6 \]

болсо, көрсөтүлгөн [k]-Рим мааниси

\[ \gamma_{[kR]}(G)=3(k+1) \]

түрүндө. Булар бардык графтар үчүн жалпы формулалар эмес, 1-сүрөттөгү белгилүү графтын энбелгилөөлөрүн түшүндүргөн маанилер.

Күчтүү Рим доминациясы эмнени моделдейт?

Күчтүү Рим доминациясы бир гана чабуулдун ордуна бир эле учурда бир нече коргоосуз коңшуну коргоону моделдөө үчүн оң энбелги алып жүргөн күчтүү чокунун 0 энбелгилүү коңшуларынын кеминде жарымына жетерлик коргонуу салмагын алып жүрүшүн талап кылган Рим доминациясынын варианты.

Графтын максималдуу даражасы \(\Delta\) болсун. Күчтүү Рим доминация функциясы, кыскача StRDF, чокуларды

\[ \left\{0,1,2,\ldots,\left\lceil\frac{\Delta}{2}\right\rceil+1\right\} \]

жыйындысынан энбелгилейт.

\[ B_0=\{w\in V:f(w)=0\} \]

0 энбелгилүү чокулардын жыйындысы болсун; ар бир \(v\in B_0\) үчүн бир коңшу \(u\) табылып,

\[ f(u)\geq 1+ \left\lceil \frac{|N(u)\cap B_0|}{2} \right\rceil \]

шарты аткарылышы керек.

Бул формулада \(|N(u)\cap B_0|\) — коргоочу \(u\) чокусунун 0 энбелгилүү коңшуларынын саны. Оң тараптагы 1 мүчө коргоочунун өзүнүн коргонуусун, шып функциясы менен эсептелген экинчи мүчө болсо ошол эле учурда коргой ала турган коргоосуз коңшулар үчүн талап кылынган кошумча мүмкүнчүлүктү билдирет.

Күчтүү Рим доминация саны

\[ \gamma_{StR}(G) \]

менен белгиленет.

Булактын 2-сүрөтүндө ошол эле мисал граф үчүн классикалык Рим доминация салмагы 6, ал эми күчтүү Рим доминация салмагы 8 деп көрсөтүлгөн. Бул сүрөт бир убактагы көп чабуул шарты бир эле графта көбүрөөк жалпы коргонуу салмагын талап кылышы мүмкүн экенин көрсөтүү үчүн колдонулган.

Жалпы төмөнкү жана жогорку чектер

Булак мурда белгилүү болгон үч негизги чекти колдонот. Биринчиден

\[ \gamma_R(G) \leq \gamma_{StR}(G) \leq \left( 1+\left\lceil\frac{\Delta}{2}\right\rceil \right)\gamma(G) \]

катышы берилет; бул жерде \(\gamma(G)\) классикалык доминация саны.

Ирети \(n\) болгон граф үчүн мындан тышкары

\[ \gamma_{StR}(G) \leq n-\left\lfloor\frac{\Delta}{2}\right\rfloor \]

жогорку чеги жана

\[ \gamma_{StR}(G) \geq \left\lceil\frac{n+1}{2}\right\rceil \]

төмөнкү чеги колдонулат. Бул чектер кийинки так-маани далилдеринде конструктивдүү энбелгилөө берген жогорку чек менен милдеттүү төмөнкү чекти бир эле мааниге алып келүүгө жардам берет.

Граф үй-бүлөлөрү эмне үчүн маанилүү?

Жалпы оптималдаштыруу маселесин бардык графтарда чечүү кыйын болушу мүмкүн; бирок дарактар, жолдор, циклдер, эки бөлүктүү графтар же чектелген clique-width класстары сыяктуу түзүлүшү өзгөчө граф үй-бүлөлөрүндө күчтүүрөөк алгоритмдик жана жабык-формадагы натыйжалар алынат. Бул изилдөөнүн негизги мамилеси да эки багыттуу: жалпы маселе кайсы түзүлүштөрдө эсептөө жагынан жеңил же оор экенин аныктоо жана айрым граф үй-бүлөлөрүндө оптималдуу салмакты түздөн-түз формула менен эсептөө.

Изилдөөдө колдонулган айрым граф үй-бүлөлөрү

Изилдөөнүн Ыкмасы жана Жыйынтыктары

[k]-Рим доминациясы кайсы граф класстарында сызыктуу убакытта чечилет?

[k]-Рим доминациясы LinEMSOL оптималдаштыруу маселеси катары туюнтулгандыктан, чектелген clique-width ге ээ граф класста ылайыктуу \(r\)-туюнтма кириш менен кошо берилсе же натыйжалуу түзүлсө, минималдуу [k]-Рим доминация функциясы графтын иретине карата сызыктуу убакытта аныкталышы мүмкүн.

MSOL жана LinEMSOL мамилеси

Монадалык Экинчи Тартип Логикасы, башкача айтканда MSOL, жекече чокулар боюнча гана эмес, чокулар жыйындылары боюнча да кванторлоого мүмкүнчүлүк берет. Графтын жанаша болуу катышы

\[ R(u,v) \]

менен берилсе, көптөгөн комбинатордук касиеттер логикалык формулалар аркылуу аныкталышы мүмкүн.

LinEMSOL бул түзүлүштү монадалык жыйындылардын кардиналдуулуктарынан түзүлгөн сызыктуу максат функциялары менен кеңейтет. Макалада [k]-Рим энбелгилөөсү

\[ f=(V_0,V_1,\ldots,V_{k+1}) \]

түрүндө чокулар жыйындарына бөлүнөт; \(V_j\) — энбелги мааниси \(j\) болгон чокулардын жыйындысы.

Бул жыйындардын \(V\) жыйындысынын partition-ы болушу жана ар бир чоку [k]-RDF шартын аткарышы логикалык түрдө туюнтулат. Оптималдаштыруу максаты

\[ \min \left\{ \sum_{j=1}^{k+1}j|V_j| : \operatorname{Partition}(V) \land [k]\text{-}\operatorname{RDF} \right\} \]

түрүндө.

Бул туюнтма энбелги салмагын түздөн-түз минималдаштырат. Courcelle мамилеси аркылуу маселе ылайыктуу ажыратуу/көрсөтүү болгондо чектелген clique-width класстарында сызыктуу-убакыт алгоритмине өткөрүлүшү мүмкүн.

Булактын Corollary 2 бөлүмүндө натыйжа \(f(k)\cdot n\) формасында берилет жана мисал класстар катары cographs, distance-hereditary graphs, complete graphs, trees, series-parallel graphs жана outerplanar graphs аталат.

Күчтүү Рим доминациясы эмне үчүн NP-толук?

Изилдөө күчтүү Рим доминациясынын чечим маселеси жылдыз-конвекс эки бөлүктүү графтарда NP-толук экенин Restricted Exact 3-Cover мисалынан белгилүү бир жылдыз-конвекс эки бөлүктүү граф түзүп, exact cover бар болушу менен төмөн салмактуу күчтүү Рим энбелгилөөсүнүн бар болушун эквиваленттүү кылуу аркылуу далилдейт.

Чечим маселеси

Кириш катары бир

\[ G=(V,E) \]

граф жана оң \(k\) бүтүн саны берилет. Суроо төмөнкүдөй:

\[ \text{Ağırlığı }f(V)\leq k\text{ olan bir StRDF var mı?} \]

Талапкер энбелгилөөнүн StRDF шарттарын жана салмак чегин полиномдук убакытта текшерүүгө мүмкүн болгондуктан, маселе NP ичинде.

RX3Cден кыскартуу

Restricted Exact 3-Cover маселесинде

\[ |X|=3q \]

жана \(C\) үч элементтүү ички жыйындардын үй-бүлөсү; ар бир \(x\in X\) так үч башка жыйында орун алат. Суроо — \(X\) жыйындысын кесилишсиз толук жаба турган \(C^\ast\subseteq C\) үй-бүлөсү барбы.

Булак бул мисалдан \(\Gamma(I)\) аттуу жылдыз-конвекс эки бөлүктүү граф түзөт жана күчтүү Рим салмак босогосун

\[ 6q+2 \]

деп тандайт.

Курулушта эки бөлүктүү класстар

\[ A=\{a,x_i,z_i:i\in[3q]\}, \qquad B=\{c_j,a_1,a_2:j\in[3q]\} \]

түрүндө. Демек

\[ |A|=6q+1, \qquad |B|=3q+2. \]

\(x_i\) чокусу \(c_j\) чокусуна тиешелүү элемент тиешелүү үчтүк жыйындын ичинде болсо гана байланышат. Мындан тышкары \(a\) бардык \(c_j\) чокуларына жана \(a_1,a_2\) ге; ар бир \(c_j\) өзүнүн \(z_j\) чокусуна байланышат.

PDFдеги 3-сүрөт бул кыскартуу графынын каркасын көрсөтөт. Сүрөттүн илимий милдети RX3C жыйын мүчөлүгүнүн графтын жанаша болуу структурасына кантип коддолгонун көрсөтүү.

Далилдин түз багытында exact cover \(C'\) бар болсо тандалган \(c_j\) чокуларына 3, айрым \(z_i\) чокуларына 1 жана борбор \(a\) га \(q+2\) энбелги берилип, жалпы салмагы

\[ (q+2)+3q+2q=6q+2 \]

болгон күчтүү Рим доминация функциясы түзүлөт.

Тескери багытта салмагы эң көп \(6q+2\) болгон оптималдуу StRDFнин түзүлүшү кадам-кадам чектелип, так \(q\) даана \(c_j\) чокусу 3 энбелгисин алып жүрүшү керектиги жана алар \(X\) тин exact cover-ын түзөрү көрсөтүлөт. Ошентип RX3C мисалынын “ооба” жообу менен StRDN мисалынын “ооба” жообу эквиваленттүү болуп калат.

[k]-Рим доминациясында таяныч чокулар

Булактын Lemma 1 бөлүгү жалбырак жана таяныч чокулардын оптималдуу энбелгилөөдөгү жүрүм-турумун чектейт. \(k\geq2\) үчүн алсыз таяныч чоку \(v\) жана ага байланышкан жалбырак \(u\) үчүн

\[ k\leq f(u)+f(v)\leq k+1. \]

Эгер сумма так \(k\) болсо, милдеттүү түрдө

\[ f(u)=k,\qquad f(v)=0. \]

Күчтүү таяныч чоку \(v\), башкача айтканда кеминде эки жалбыракка коңшу болгон чоку үчүн оптималдуу [k]-Рим энбелгилөөсүндө

\[ f(v)=k+1 \]

жана \(v\) ге байланышкан бардык жалбырактарда

\[ f(u)=0 \]

болору көрсөтүлөт. Бул лемма кийинки дарак жана кош жылдыз жыйынтыктарынын негизги курулуш элементи болуп саналат.

[k]-Рим доминациясында кандай так маанилер алынды?

Изилдөө кош жылдыздар үчүн түз формулаларды, \(n\equiv0\pmod3\) болгондо жолдор жана циклдер үчүн жалпы жабык форманы жана жолдордун [k]-Рим reinforcement саны үчүн конгруэнттүүлүк класстарына жараша жыйынтыктарды берет.

Кош жылдыздар

\(S_{1,q}\) бир алсыз жана бир күчтүү таяныч чокусу бар кош жылдыз болгондо

\[ \gamma_{[kR]}(S_{1,q})=2k+1 \]

жыйынтыгы алынат.

Эки борбор тең кеминде эки жалбыракка ээ болсо, башкача айтканда \(p,q\geq2\) үчүн

\[ \gamma_{[kR]}(S_{p,q})=2k+2. \]

Экинчи формуланын артындагы түзүлүш жөнөкөй: эки борбор тең күчтүү таяныч чоку жана Lemma 1 боюнча ар бири \(k+1\) салмак алып жүрөт; жалбырактардын оптималдуу энбелгиси 0.

Жол жана циклдердеги энбелги түзүлүшү

Булак кеминде төрт чокулуу жол же циклде минималдуу [k]-Рим функциясында айрым орто деңгээлдеги энбелгилер төрт удаалаш чокуда үзгүлтүксүз кайталана албасын көрсөтөт. \(k\) жуп болгондо тыюу салынган түзүлүш үч удаалаш чокуга чейин күчөйт.

Мындай жергиликтүү түзүлүштүк чектөөлөр оптималдуу энбелгилер кандай периоддук үлгүлөрдү түзүшү мүмкүн экенин түшүнүүгө жана так маанилерди чыгарууга жардам берет.

Жол менен циклди салыштыруу

Цикл ошол эле иреттеги жолго бир кыр кошуу менен алынгандыктан, булак

\[ \gamma_{[kR]}(C_n) \leq \gamma_{[kR]}(P_n) \]

теңсиздигин берет.

Белгилүү бир оптималдуу жол энбелгилөөсүндө \(V_1=\varnothing\) жана \(V_{k+1}=\varnothing\) шарттары аткарылса, күчтүүрөөк жыйынтык

\[ \gamma_{[kR]}(C_n) \leq \gamma_{[kR]}(P_n)-1 \]

алынат.

\(n\equiv0\pmod3\) учурдагы так маани

\(n\) үчкө бөлүнсө, \(P_n\) жана \(C_n\) үчүн натыйжалуу доминациялоочу жыйын ар үч чокунун бирин тандоо менен түзүлөт. Бул учурда

\[ \boxed{ \gamma_{[kR]}(C_n) = \gamma_{[kR]}(P_n) = (k+1)\frac{n}{3} } \]

болот.

Бул жерде ар бир тандалган доминациялоочу чоку \(k+1\) салмак алып жүрөт жана жабык коңшулуктар графты кайталанбастан жаап чыгат.

Жол графтарындагы reinforcement

Булак [k]-Рим reinforcement санын \(r_{[kR]}(G)\) менен белгилейт жана негизги максат катары графтын [k]-Рим доминация санын азайтуу үчүн канча жаңы кыр жетиштүү экенин изилдейт.

Булак ичиндеги нотация эскертүүсү: Definition 1де \(F\subseteq E(G)\) деп жазылган; бирок ошол эле аныктама \(G+F\) ни “\(F\) деги кырларды кошуу” деп түшүндүрөт жана кийинки далилде баштапкы жолдо жок кырлар кошулат. Ошондуктан бул жерде аныктаманын басылган түрү унчукпай өзгөртүлгөн жок, жыйынтыктар Proposition 10догу ачык конструкциялар аркылуу берилди.

\(n\geq4\) үчүн булак

\[ r_{[kR]}(P_n)\in\{1,2\} \]

жыйынтыгын берет.

Далилде колдонулган жол маанилери тиешелүүлүгүнө жараша

\[ \gamma_{[kR]}(P_n) = (k+1)\frac{n}{3}, \qquad n\equiv0\pmod3, \]

\[ \gamma_{[kR]}(P_n) = (k+1)\left\lfloor\frac{n}{3}\right\rfloor+k, \qquad n\equiv1\pmod3, \]

жана

\[ \gamma_{[kR]}(P_n) = (k+1)\left\lfloor\frac{n}{3}\right\rfloor+k+1, \qquad n\equiv2\pmod3 \]

түрүндө.

Күчтүү Рим доминациясында кайсы граф үй-бүлөлөрү үчүн так формулалар табылды?

Изилдөө \(t\)-катмарлуу дөңгөлөктөр, таажы графтары, \(C_m\circ K_1\) корона графтары жана ар бир омуртка чокусунда кеминде эки жалбырак болгон айрым курт сымал графтар үчүн күчтүү Рим доминация санын так аныктайт; жалпыраак курт сымал графтар үчүн болсо жогорку чек берет.

\(t\)-катмарлуу дөңгөлөктөр

\(W_{m,t}\), бир \(C_m\) циклине бири-бирине коңшу эмес \(t\) борбордук чоку байланыштырганда түзүлөт. Proposition 11 күчтүү Рим доминация саны \(m\) жана \(t\) нин чоңдук жана паритет шарттарына жараша өзгөрөрүн көрсөтөт:

\[ \gamma_{StR}(W_{m,t})= \begin{cases} \left\lceil\dfrac{t}{2}\right\rceil+2, & m=3,\ t\geq2,\\[6pt] \left\lceil\dfrac{t}{2}\right\rceil+3, & m=4,\ t\geq2,\\[6pt] \left\lceil\dfrac{m}{2}\right\rceil+t, & m\geq5,\ t=2,\\ & \text{veya }m\text{ çift},\ m\geq5,\ t=3,\\[6pt] \left\lceil\dfrac{m-1}{2}\right\rceil+ \left\lceil\dfrac{t+1}{2}\right\rceil+2, & m,t\text{ tek},\ m\geq5,\ t\geq3,\\ & \text{veya }m\geq6,\ t\geq4,\ m+t\text{ tek},\\[6pt] \dfrac{t}{2}+4, & m=5,\ t\text{ çift},\ t\geq4,\\[6pt] \dfrac{m}{2}+\dfrac{t}{2}+2, & m,t\text{ çift},\ m\geq6,\ t\geq4. \end{cases} \]

Бул бөлүктүү түзүлүш кокустук эмес. Цикл чокулары жана борбордук чокулар бир учурда канча коргоосуз коңшуну коргошу керек экендиги \(m\) жана \(t\) нин паритетине жараша оптималдуу күчтүү чоку жайгашуусун өзгөртөт.

Таажы графы

Таажы графы \(C(n)\), \(K_{n,n}\)-ден толук дал келтирүү алынып салынуу менен түзүлөт жана жалпы \(2n\) чокуну камтыйт. Булак төмөнкү так маанини берет:

\[ \boxed{ \gamma_{StR}(C(n))= \begin{cases} n+1,&n\equiv1\pmod2,\\ n+2,&n\equiv0\pmod2. \end{cases} } \]

Так \(n\) да жалпы төмөнкү чек менен конструктивдүү жогорку чек дал келип, \(n+1\) берет. Жуп \(n\) да оптималдуу чечимде эки башка эки бөлүктүү класста күчтүү чоку болушу керек экени көрсөтүлүп, төмөнкү чек \(n+2\) ге көтөрүлөт.

PDFдеги 4-сүрөт \(C(3)\) таажы графында минималдуу күчтүү Рим доминация функциясынын мисалын көрсөтөт.

Цикл-корона графы \(C_m\circ K_1\)

Циклдин ар бир чокусуна бир жалбырак кошулганда \(C_m\circ K_1\) графы түзүлөт. Proposition 13 төмөнкү так формуланы берет:

\[ \boxed{ \gamma_{StR}(C_m\circ K_1)= \begin{cases} \dfrac{3m}{2},&m\equiv0\pmod4,\\[6pt] \dfrac{3m+1}{2},&m\equiv1\pmod2,\\[6pt] \dfrac{3m+2}{2},&m\equiv2\pmod4. \end{cases} } \]

Жогорку чек цикл чокуларында ар төрт чокуда кайталанган өзгөчө \(2,0,0,2\) сымал энбелги түзүлүшү жана жалбырак энбелгилери менен курулат. Төмөнкү чекте болсо өзгөчө \(m\equiv0\pmod4\) учурда discharging, башкача айтканда жүктү кайра бөлүштүрүү аргументи колдонулат.

Discharging ыкмасы эмне кылат?

Далилдин башында ар бир чокунун жүгү өз энбелгисине тең деп алынат:

\[ s_0(v)=f(v). \]

Андан кийин айрым жалбырактардан цикл чокуларына жана 2 энбелгилүү цикл чокуларынан коңшуларына жарым же бир толук бирдик жүк өткөрүлөт. Бул өткөрүү жалпы жүктү өзгөртпөйт:

\[ \sum_{v\in V}s(v) = \sum_{v\in V}f(v). \]

Бирок кайра бөлүштүрүлгөн жүктөр ар бир цикл чокусунда кеминде \(3/2\) өлчөмүндөгү орточо салым алууга мүмкүндүк берет. Натыйжада

\[ \gamma_{StR}(G) \geq \frac{3m}{2} \]

төмөнкү чеги келип чыгат жана конструктивдүү жогорку чек менен дал келгенде так маани далилденет.

Өзгөчө курт сымал графтар

Омуртка \(v_1,\ldots,v_n\) чокуларынан турсун жана ар бир \(v_i\) ге

\[ x_i\geq2 \]

жалбырак байланышсын. Бул учурда ар бир омуртка чокусу күчтүү таяныч чоку. Proposition 14:

\[ \boxed{ \gamma_{StR}(C) = \sum_{i=1}^{n} \left( 1+ \left\lceil\frac{x_i}{2}\right\rceil \right) } \]

так маанини берет.

Жогорку чек үчүн ар бир омуртка чокусуна

\[ f(v_i)= 1+ \left\lceil\frac{x_i}{2}\right\rceil \]

энбелгиси, бардык жалбырактарга болсо 0 энбелгиси берилет. Төмөнкү чек ар бир күчтүү таяныч чоку жана анын жалбырактары жалпы кеминде ушул эле салмакты талап кыларынан алынат.

PDFдеги 5-сүрөт бул түзүлүштү визуалдуу көрсөтөт: омурткадагы күчтүү таяныч чокулар 2 же 3 сыяктуу оң энбелгилерди алып жүргөндө, байланышкан жалбырактар 0 энбелгилүү. Сүрөттүн ролу жабык формуладагы ар бир омуртка чокусунун жергиликтүү салымын көрүнүктүү кылуу.

Жалпыраак курт сымал граф үчүн жогорку чек

Булак акырында омурткада күчтүү таяныч чокулардан тышкары \(k\) даана алсыз таяныч чоку жана таяныч чокулардын ортосунда таяныч эмес чокулардан турган \(q\) даана \(P_{r_j}\) ички жол болушуна уруксат берет. Бул жалпыраак учурда так маани эмес, төмөнкү жогорку чек берилет:

\[ \boxed{ \gamma_{StR}(C) \leq \sum_{i=1}^{n} \left( 1+\left\lceil\frac{x_i}{2}\right\rceil \right) + 2k + \sum_{j=1}^{q} \left\lceil\frac{2r_j}{3}\right\rceil } \]

Биринчи сумма күчтүү таяныч чокуларды жана алардын жалбырактарын, \(2k\) мүчөсү алсыз таяныч чокуларды, акыркы сумма болсо таяныч чокулардын ортосундагы аралык жолдордун күчтүү Рим доминация чыгымын билдирет.

Булак сүрөттөрүнүн илимий функциялары

Изилдөө колдогон жыйынтыктар

Изилдөө [k]-Рим доминациясын ылайыктуу түзүлүштүк граф класстарында LinEMSOL жана Courcelle алкагы аркылуу сызыктуу-убакыт чечимине келтирүүгө болорун; күчтүү Рим доминациясы жылдыз-конвекс эки бөлүктүү графтарда NP-толук экенин; ошондой эле айрым кош жылдыз, жол, цикл, дөңгөлөк, таажы, корона жана курт сымал үй-бүлөлөрдө доминация параметрлерин жабык формада эсептөөгө болорун математикалык далилдер менен колдойт.

Натыйжалар графтык оптималдаштыруу маселесинин татаалдыгы чокулардын жана кырлардын санына гана эмес, графтын түзүлүштүк классына да күчтүү көз каранды экенин көрсөтөт: жалпы же айрым эки бөлүктүү класстарда чечим маселеси оор болушу мүмкүн, ал эми чектелген clique-width/treewidth түзүлүшү кошумча алгоритмдик рычаг берет.

Изилдөө колдобогон жыйынтыктар

Макала реалдуу аскердик, логистикалык же инфраструктуралык тармакта эксперимент жүргүзбөйт. “Коргонуу бирдиги” деген тил граф теориясынын тарыхый жана концептуалдык түшүндүрмөсү. Натыйжалар реалдуу дүйнөдөгү ресурс бөлүштүрүүгө түздөн-түз натыйжалуулук кепилдигин бербейт. LinEMSOL натыйжасы бардык графтарда сызыктуу-убакыт алгоритми бар дегенди билдирбейт; ал чектелген clique-width жана ылайыктуу көрсөтүү божомолуна көз каранды. NP-толуктук натыйжасы да ар бир жеке граф мисалын практикада чечүү мүмкүн эмес дегенди билдирбейт; ал маселе классынын эң начар жагдайдагы эсептөө татаалдыгын билдирет.

Ошондой эле t-катмарлуу дөңгөлөк, таажы, корона жана өзгөчө курт сымал граф формулалары көрсөтүлгөн граф үй-бүлөлөрү жана параметр шарттары үчүн гана жарактуу; каалаган графтын күчтүү Рим доминация санын бул формулалардан чыгаруу мүмкүн эмес.

Булактагы эки нотация маселеси

Биринчиден, кириш бөлүмүндө \(P_n\) узундугу \(n\) болгон жана \(u_0,u_1,\ldots,u_n\) чокуларынан турган жол деп аныкталса, кийинки жыйынтыктарда \(P_n\) “ирети \(n\)” болгон жол деген мааниде колдонулат. Ошондуктан бул Verianla текстинде жыйынтыктар берилгенде тиешелүү теорема же сунуштун өзүндөгү “ирети \(n\)” деген сөз айкашы негиз катары алынган; кириш аныктамасы унчукпай кайра жазылган эмес.

Экинчиден, [k]-Рим reinforcement аныктамасында булак \(F\subseteq E(G)\) деп жазат; бирок \(G+F\) ни кыр кошуу операциясы деп аныктайт жана Proposition 10 конструкцияларында жолдо мурда болбогон \(v_2v_4\), \(v_6v_8\), \(v_1v_3\) жана \(v_1v_4\) кырларын кошот. Бул ачык булак-ички шайкешсиздиктен улам Verianla аныктамадагы жыйын туюнтмасын божомол менен өзгөрткөн эмес.

Булак жана Ыкма Жөнүндө Эскертүү

Түпнуска изилдөө: Complexity and Exact Values for [k]-Roman and Strong Roman Domination for Specific Graph Families

Авторлор: Juan Carlos Valenzuela-Tripodoro; María Antonia Mateos-Camacho; Martín Cera López; María Pilar Álvarez-Ruíz.

Corresponding author: Juan Carlos Valenzuela-Tripodoro.

Мекемелер: Departamento de Matemáticas, Universidad de Cádiz, Algeciras, İspanya; Departamento de Matemática Aplicada I, Universidad de Sevilla, Sevilla, İspanya; Departamento de Estadística e IO, Universidad de Cádiz, Algeciras, İspanya.

Журнал: Mathematics.

Басма: MDPI.

Библиографиялык жазуу: Mathematics 2026, 14(9), 1535.

DOI: 10.3390/math14091535.

Макаланын процесси: Алынган 19 Февраль 2026; ревизия 6 Апрель 2026; кабыл алынган 28 Апрель 2026; жарыяланган 1 Май 2026.

Булак түрү: Рецензияланган теориялык математика / дискреттик математика / граф теориясы боюнча изилдөө макаласы.

Лицензия: Creative Commons Attribution (CC BY).

Маалыматтардын абалы: Авторлор изилдөөдө жаңы маалымат түзүлбөгөнүн же талданбаганын билдиришет. Изилдөөнүн далил материалын граф түзүлүштөрү, математикалык аныктамалар, теоремалар, сунуштар жана далилдер түзөт.

Автордук салымдар: Концептуалдаштыруу, методология, текшерүү жана изилдөөгө төрт автордун баары салым кошкон. Алгачкы долбоор Martín Cera López жана María Pilar Álvarez-Ruíz; кароо жана редакциялоо Juan Carlos Valenzuela-Tripodoro жана María Antonia Mateos-Camacho тарабынан жүргүзүлгөн. Булак бардык авторлор изилдөөгө тең салым кошконун өзүнчө белгилейт.

Каржылоо: Juan Carlos Valenzuela-Tripodoro; Испаниянын Илим, Инновация жана Университеттер министрлигинин PID2022-139543OB-C41 долбоору жана Европа Комиссиясынын Horizon Europe Marie Skłodowska-Curie Actions Staff Exchanges алкагындагы 101182819 номерлүү COVER долбоору тарабынан жарым-жартылай колдоого алынган. Martín Cera López; Андалусия Аймактык Өкмөтүнүн Изилдөө, Өнүктүрүү жана Инновация Планынын FQM-240 долбоору жана PPIT-FEDER SOL2024-31708 “Mathematics for Cybersecurity and Smart City Development” долбоорунан жарым-жартылай колдоо алган.

Кызыкчылыктардын кагылышы: Авторлор кызыкчылыктардын кагылышын билдиришкен эмес.

Булак түзүлүшү боюнча эскертүү: Макалада өзүнчө “Conclusions” бөлүмү жок. Негизги илимий мазмун Proposition 15 менен аяктагандан кийин автордук салымдар, каржылоо, маалыматтардын жеткиликтүүлүгү жана кызыкчылыктардын кагылышы жөнүндө билдирүүлөр берилет. Ошондуктан Verianlaдагы “изилдөө колдогон / колдобогон” баалоолор макалада далилденген жыйынтыктардан гана чыгарылган; булакка таандык эмес жаңы жыйынтык бөлүмү катары берилген эмес.

Негизги методологиялык чек: Изилдөө эксперименттик же эмпирикалык эмес. Алгоритмдик татаалдык жыйынтыктары көрсөтүлгөн граф классына жана көрсөтүү божомолдоруна; так-маани формулалары болсо тиешелүү граф үй-бүлөлөрүнө, паритет жана конгруэнттүүлүк шарттарына көз каранды.

Нотация чеги: Булактагы \(P_n\) узундук/ирет колдонулушу менен reinforcement аныктамасындагы \(F\subseteq E(G)\) туюнтмасы булакта көрүнгөндөй ички шайкешсиздикти камтыйт. Бул Verianla тексти бул пункттарды жашырган эмес жана белгисиз оңдоону булак жыйынтыгы катары көрсөткөн эмес.

Визуалды кайра чийүүгө ылайыктуулук: Ылайыктуу. Беш булак сүрөтүнүн баары граф-теориялык схема болгондуктан, түйүндөрдүн позициялары жана энбелгилөө логикасы сакталып, Verianla үчүн оригиналдуу вектордук граф схемалары түзүлүшү мүмкүн. Максат пикселдик көчүрмө эмес, ошол эле математикалык байланыштарды жаңы дизайн менен көрсөтүү.

Verianla Live / Live Figure: Жарым-жартылай ылайыктуу. Айрыкча 1–2-сүрөттө энбелгилер коргонуу шартын кантип аткарары этап-этабы менен белгилениши жана 3-сүрөттө RX3Cден \(\Gamma(I)\) ге өтүү кадамдап көрсөтүлүшү source-derived Live Figure катары баалуу. Колдонуучуга графты же \(k\) маанисин өзгөртүп жаңы оптималдуу жыйынтык чыгарууга уруксат берилбеши керек; бул булакта жасалбаган жаңы эсептөө болуп калат.