Смешанный тип дуальности в многообъектных задачах оптимизации с применением обобщенных алгебраических операций

К. Петросян

Государственный Университет Бухареста, Бухарест, Румыния

Ключевые слова. Обобщенные алгебраические операции Бен-Тала, — подлинейный функционал, смешанная дуальная задача, парето слабые решения.

ВВЕДЕНИЕ

Для разных предположений выпуклости функций (выпуклость, обобщенная выпуклость или обобщенная р выпуклость) в литературе Веир и Монд [1], Веир [2] и Егудо [3, 4] использовали понятия характерной оптимальности (англ: “ргорегеГАаепсу”, по смыслу Геоффриона) и оптимальности для получения некоторых результатов дуальности, где рассматриваются дуалы типа Вольфа и Монд-Веира. Васеиле Преда [5] определил понятие обобщенной (¥, р)выпуклости как продолжение для ¥ -выпуклости, определенной Хансоном и Мондом [6], и обобщенной р — выпуклоти, определенной Виалом [7]. Он также

использовал понятие (¥, р)выпуклости для получения некоторых важных

результатов для теории дуалов.

В этой статье мы определим смешанную дуальную задачу для задачи (УР). Дуалы же типа Вольфа или Монд-Веира являются частными случаями дуала смешанного типа. Мы получим несколько новых результатов для теории дуальности для проблемы (УР) под разными предположениями обобщенных

( Р, р) — выпуклостей.

Для простоты чтения ниже приведены некоторые определения обобщенной (.Р, р) — выпуклости из [5], использующие обобщенные алгебраические операции Бен-Тала вместо обычных:

Определение 1.1. Функционал Р: Сх Сх Яп ^ Я называется ^ р)подлинейным, если для любых х, X е С, выполняются условия Р(х, х°, с Ф с2 )< Р(х, х0, с)[+] Р(х, х0, с2), Уе1, с2 е Я.

р(х, х0 ,а® с)< а [•] Р(х, х0, с), Уа е Я, а > 0, с е Я1.

Пусть, Р(Ь,р)сублинейный функционал а /: С^ Я является (Ь,р)-дифференцируемой функцией в точке х0 е С, ре Я и (•,•): Сх С ^ Я.

Определение 1.2. Функция / называется (Ь,р, Р,р) выпуклой функцией в точке х , если для всех хе С имеет место

/(х)-/х°) > Р(х, х°,V*/х°))[+] С2 (х, х°)[^]р.

Из вышеприведенного определения мы можем предложить следующие обобщения (х, р, Р, р) — выпуклости.

Определение 1.3. Функция / называется хЬ, р, Р, р) квазивыпуклой в

точке х0 , если для всех хе С имеет место

//х) < /х0) ^ Рхх,х°,V*/х0)) <-С2хх,х0)[^]р,

или эквивалентно,

Р х х, х°, У/хх°) > С2 х х, х° )[^]р /х) > /х°)

Определение 1.4. Функция /называется хЬ, р, Р,р) — псевдовыпуклой в точке х0 , если для всех хе С имеет место

Рхх, х0, V*/ х0) > — С2 хх, х0)[•]р /х) > //х0)

Определение 1.5. Функция / называется строго (, р, ¥, р)псевдовыпуклой в точке X , если для всех X е С , X X0 имеет место ¥(х, х0,) >-ё2 (х, х0)[*]р /(X) > /(х0) или эквивалентно,

/(х)< )^ ¥(х, х°, У*/(X0)) <-ё2 (х, X0)[*]рОбозначим через X множество допустимых решений задачи (УР), Р ={1,2,…,р} и М = {1,2,…,

т

Далее, мы дадим определение новых операторов, как продолжение для обоих обобщенных операторов умножения и для одного из операторов сложения, определенных Бен-Талом.

Определение 1.6. Для двух скалярных значений а е Я и Д е Я скалярное произведение этих двух чисел относительно реальной функции р Бен-Тал

определил как а [•] Д = р(р^Д) . Произведение векторов Д е Як , где к > 1

мы определим следующим образом:

аМв= Е аНД.

_ 1=1 _

Определение 1.7. Для скалярного значения а е Я и вектора Xе Я произведение вектора X со скалярным значением а относительно векторной функции Ь Бен-Тал определил как а® X = ЬТХ (аЬ (X)) . Произведение вектора

а е Як и матрицы Xе Мк/п, где к > 1 мы определим следующим образом:

к

а® X =@а! ® X

1=1

Определение 1.8. Для двух скалярных значений а е Я и Д е Я скалярное сложение этих двух чисел относительно реальной функции р Бен-Тал определил как аг[+]в = р— (р(а) + р(в)). Сложение векторов а,Де Як, где к > 1, мы определим следующим образом:

сс[+]Д = (р1 (р() + р(Д1)),…,р-х (р(ак) + р(Дк)))е Як .

2. СМЕШАННАЯ ДУАЛЬНОСТЬ

Пусть, ]х некоторое подмножество множества М И У2 = М ]х, а е Яр , в е Ят, и пусть, е вектор пространства Яр, у которого все компоненты единицы. Мы будем изучать смешанный тип дуала для задачи (VР) :

тах ^(и)Н(в.л Н(u))е,

а®У* / (u )0в<^* g (и ) = 0,

[•]«,, (» )> 0,

^ а = 1, а > 0, в > 0, и е С.

. ;=1

Далее в этой работе по умолчанию мы будем предполагать функцию ф строго растущей и ф(0) = 0. Также будем предполагать Ь(0) = 0 для векторфункции Ь. Для получения нужных результатов нам необходимо доказать еще одно дополнительное свойство (Ь, ф) -дифференцируемых функций.

Лемма 2.1. Допустим, что функции /, g: Яп ^ Я(Ь, ф) дифференцируемые в точке X. а е Я. Тогда имеют место следующие утверждения:

(а)        ^ /(х) 0 V*g(х) = V* ( /(х) [+] g(х)),

(Ь)       а®V* / (x) = V* («[•] (х)).

Доказательство: Для (а), из определения (Ь, ф) дифференцируемости

имеем:

V* f (х)Ф V* £ (х) = И(И (у* f (х)) + И (у* ъ (х))) = И(V ? (0Цх) + у Ъ (?)

подпись: і=цх)подпись: і=ці=((у ((‘))+’у Ъ М| = *’ (у(? (‘)+г (‘)))„)=(у «

= у (х) = у* (/ ()[+]ъ (х)).

Доказательство (а) закончено.

Для (Ь) обозначим 5(х) = а [•] (х) и рассмотрим значение 5(х) :

5(х) = ф((-1 (х)) = ф(а[* (И-1 (х))) = аф f(И(х))) = а?(х). Теперь левую часть уравнения (Ь) можно раскрыть следующим образом:

подпись: а ®у* /(х) = ь 1 (а(v* /(х)) = ь 11 ау /(ґ) = ь - (у5(х)‘           )} = К’ (у(а-?(0)|„„) = у’5(х) = у’(А#

Лемма доказана.

Теорема 2.1. (Слабая дуальность). Допустим, что для всех допустимых решений х задачи (УР) и для всех допустимых решений (и,а,в) дуальной

задачи (ЫПР)

Р.,2 НЪл (•) является (И, ф, ¥, р) — квазивыпуклой в точке и и допустим, что одно из следующих условий удовлетворяется:

а, > 0 для всех У е Р, и f (• )МвЛ-] &,( •) является и (И,ф, ¥, р) квазивыпуклой и (И,ф, ¥, р11) — псевдовыпуклой в точке и , У е Р и

р[+а[^А > 0.

а1 > 0, У е Р для всех У е Р, и f (• )[+влН &,( •) является (,ф, ¥, р) -квазивыпуклой в точке и и существует такой А е Р, что ^ (•) [+]в]’ [•] (•) является строго (И,ф, ¥, р1к ) — псевдовыпуклой в точке и , и

аМ^На >0.

(Ф) а, > 0 для всех 1е Р, »[• ] f (• )[+Р]1 [•](•) и является (,ф, ¥, р2) -псевдовыпуклой в точке и , и

р[+А2 > 0

Тогда следующие условия не могут выполняться одновременно:

У!е Р, $(х)< $(и)[+р^ [•]gJl (и),        (1) ЗУе р $(х)< ^(и)[+]в [•]gJl (и).     (2)

Доказательство: Пусть, х некоторое допустимое решение задачи (1Р) и пусть, (и, а, в) некоторое допустимое решение задачи (МРЁ) . Тогда будем иметь

в М gJ2 ( [^] gJ2 (и)   (3)

Из неравенства (3) и из условия (а), используя лемму 2.1 (Ь), получим

Е(х, и,в/2 «V*gJ2 (и))<-^2 (х, и)[-]р (4)

С другой стороны, из допустимости (и, а, в) для задачи (МРЁ) и из подлинейности Е получим

подпись: (5)Е(X, и, а ® V* /(и)Ф в/1 « V*gJl (и)) [+] Е(X, и, вJг « V*gJ2 (и)) >

> Е(х, и,а« V* /(и)0в®V*g(и)) = 0.

Имея в виду монотонность функции р, из (4) и (5) будем иметь:

подпись: (6)Е(х,u,а®V*/(и)®в^ «V*gJ (и))> (х,и)[^]р

Для условия (б) из подлинейности Е и (6) получим

подпись: р
т
i=1
подпись: >а у [*]Е (х, u,а®V* ( (и)®вЛ «V* gJl (и))

подпись: (7)подпись: >> Е(х,u,а®V*/(и)®в^ «V*gJl (и))> (х,и)[.]р

>-2 (х, и)[.]

 

Т

1=1

 

«1. 2 (хи)[•,

 

а

 

 

подпись: (8)подпись: либоТак как аУ > 0 , 1 е Р, из (7) следует, что, либо VI е Р , Е(х, и, «V* $ (и)Ф вJ1 « V*gJl (и)) = -</2 (х, и)[•]#,,

подпись: (9)З1 е Р, Е(х, и,«V* $(и)ФвА « V*gJl (и)) > </2 (х, и)[•]р,

подпись: лучим:
подпись: (10)

подпись: $1 (х)мв мgjl (х)> $1 (и)мв нgjl (и) , viе р.

Если (8) имеет место, то из условия (Е, р^.) — псевдовыпуклости в (Ь) поТак что (1) и (2) не могут выполняться, так как в (10) X должно было быть

ЗУ є р, Ї, (х)[+р^ [•] gJl (х)> Ї, (и)[+]р^ [.] (и), VI є Р, (12)

которое означает, что (1) и (2) не могут выполняться одновременно.

Для условия (с) мы видим из вышеприведенных аргументов, что, условие

строго (Р, р1к)-псевдовыпуклости и (8) дают в результате (12). То же самое с условием ( , Рі,) квазивыпуклости и (9). Значит, (1) и (2) в этом случае не

могут выполняться.

Допустим теперь, что условие (ф) справедливо. Снова, из (6) следует, что

(13)

(14)

(15)

Последнее неравенство означает, что (1) и (2) не могут выполняться одновременно, так как а1 > 0 для всех i е Р. Доказательство завершено.

В Теореме 2.1 мы пользуемся условием а1 > 0, Vi’е Р. Конечно, без этого условия нам нужно будет предложить другое условие для получения нужных результатов, что приводит нас к следующей теореме.

Теорема 2.2. (Слабая дуальность). Допустим, что для любого допустимого решения X задачи (УР) и для любого допустимого решения (и, а, в) дуальной

задачи (ЫРЁ) , выполняется одно из следующих условий:

(а)        в1г [• ](•) является (Л, ф, Р, р) — квазивыпуклой в точке и и

{1 (• Л+К [•] ёь является строго (Ь,ф, Р, рХ1) — псевдовыпуклой в точке и и

1 є Р, и

<Ь) в [•]В1г (•) является (Ъ,р, Р, р) — квазивыпуклой в точке и и а [•] I(• )[+]в!, [•] &, является строго (Д р, Р, р2) — псевдовыпуклой в точке и , и

р[+]р2 > °(с)   в А [•] В л, (•) является строго (Д р, Р, р) — псевдовыпуклой в точке и и Г1 (• Л+К [•] ёз, (•) является (Д р, Р, р, ) — квазивыпуклой в точке и , У е Р и р[+]а[^]р1 > 0.

И для функции ё (•,•) справедливо следующее утверждение:

х, и е С и * ф и ^ ё (х, и )ф 0,           (16)

Ю вЛ [•] ё!, (•) является строго (Д р, Р, р) — псевдовыпуклой в точке и ,

а [•]’ (• )[+№[•] ел-) является (Др, Р, р1У) — квазивыпуклой в точке и ,

р[+]р2 > 0, а для функции ё(•,•) справедливо утверждение (16).

Тогда условия (1) и (2) не могут выполнятся одновременно: Доказательство: Для условия (а), объединяя (8) и (9), получим

Р(х, и®У* ((и)0в/1 ®V*ВJl (и)) > — ё2 (х, и^^р^, Уе Р (17)

Что означает для хФ и, используя условие (а),

Ъ ( х) [+] вк М В>1 ( х)> Ъ ( и)[+]в!1 Н ё!1 ( и) , У е Р (18)

Для условия (Ь) имеем (13) и поэтому (14), но со строгим знаком неравенства. То есть

аН Г ( х)[+]в!1 Н ёл ( х) > аН Г ( и) [+] вЛ Н В>1 ( и) , х Ф и (19)

Для условия (с) мы сначала имеем (17) со строгим знаком неравенством для хФ и, и поэтому (18).

Для условия (Й) мы сначала имеем (13) со строгим знаком неравенства для хФ и, и поэтому (19).

Оба из условий (18) и (19) означают, что (1) и (2) не могут выполняться одновременно, имея в виду, что х является допустимым решением задачи

(УР) . Доказательство теоремы завершено.

В доказательствах предыдущих двух теорем мы использовали неравенство в МВл,(и) > 0 в условиях задачи (МОР) . Если использовать это же условие

со знаком равенства в задаче (МОР), можно будет доказать следующую теорему, форма которой раньше не встречалась в литературе.

Теорема 2.3. (Слабая дуальность) Допустим, что для любого допустимого решения Xдля задачи (УР) и для любого допустимого решения (и, а,в) для

дуальной задачи (ЫРР) выполняется любое из следующих условий:

аі > 0 для всех і є Р, їі (• )Нв, [• ] §, (•) является и (,р, Р, Рі )псевдовыпуклой и (, р, Р, Рг ) — квазивыпуклой в точке и и , і є Р и а[і]р> 0;

аі > 0 для всех і є Р и а[і ] / (^)[ + ]в[^] § (•) является (,р, Р ,0)псевдовыпуклой в и ;

І, (і)[+]в[і]§(і) является строго (Др, Р, р1) — псевдовыпуклой в

точке и, і є Р и от [•] р > 0;

(ф) а[і] /(і)[+]в[і]§(•) является строго ( Др, Р, 0) — псевдовыпуклой в точке и ;

(е) 4 (• >[+]в[-]§(•) является (Др, Р, рі) — квазивыпуклой в точке и , і є Р и а[^]р > 0 , а функция (І(•,•) удовлетворяет условию (16);

ю <*[•] {(•)[+]в[^]§(0 является (Др, Р, р) — квазивыпуклой в точке и р > 0 , а функция (І (•,•) удовлетворяет условию (16);

Тогда условия (1) и (2) не могут выполняться одновременно. Доказательство: Используя Р(X, и, 0) в определении 1.1 и условие равенства градиентов в задаче (ЫПР), получим

Р (х, и,а®У*/( и )Фв®У* § (и )) = 0.            (20)

Для условия (а) имеем

Р(х,и,а®У*/’(u)®в®V*§(и))> А[•]</(х,и)[]р) (21)

І і=1 J

Аналогично строкам от (7) до (12) мы также получим (11) и (12), используя

в/2 [•] В,2 (и)> ^ Рі’] В( Х)£ 0 в [•] В,2 (Х)^ 0, УХ є Х . (22)

Доказательство для условия (Ь) аналогично строкам от (13) до (14).

Для (с) доказательство аналогично строкам от (17) до (18), имея (18) в результате.

Для (ф) из (20) и строго (Р ,0) — псевдовыпуклости функции а [•] е (• )[+]в[-] § (•) в и имеем:

«[• ] /(х)[+]вНк(х)>а[^] /(и)[+в]к(и), хф и (23)

Так что, тут тоже получится (19), используя (22).

Для (е) имеем (21) со строгим знаком неравенства для х Ф и, и из полинейности Е имеем:

ЗУе Р, Е(х, uV* ((и)0в<^*к(и))> 0 , (24)

Из условия квазивыпуклости функции ^ (• )[+]в[-] к (•) в точке и имеем:

ЗУе Р Г,(х)К№]к(х)> ^(и)К№]к(и)   (25)

Так что, результат тоже верен, исходя из условий (22).

И наконец, для ( /) из (20) имеем:

Е(х, и, а®V* /’(и)0в[^*к(и))>-^2 (х, )[•]#, хф и (26)

Аналогично имеем (23) и (19) Доказательство завершено.

Заметим, что (19) эквивалентно утверждению, что и является единственным оптимальным решением задачи:

подпись: (р),и„подпись: 2
1=1
р (а[• ]((х)Нв,Нк,(х)))

min

,в)

То есть, результаты, полученные из условий (Ь) или ^) в теореме 2.2, или условий ^) или (!) в теореме 2.3, можно выразить через следующую лемму.

Лемма 2.2: Допустим, что (и, а, в) является допустимым решением для

задачи (MDP) . Если и единственное решение задачи (Р)(ав) , то условия

(1) и (2) не могут выполняться одновременно.

Теорема 2.4: (Сильная дуальность) Допустим, что х° допустимое решение задачи ^Р), х° оптимальное решение задачи ( VP) и удовлетворяет условиям Кун-Такера для задачи ^Р~). Тогда существуют такие а0, в°, что (,а0,в°) допустимое решение задачи (MDP) и в° [•]к(х°) = 0. Далее, если условия слабой (УР) и (MDP), то (ха,а°, в°) -дуальности удовлетворяются (любая из Теорем 2.1, 2.2 and 2.3) между задачами является оптимальным решением задачи (MDP).

Доказательство: Существование и допустимость решения (ха,а°, в°) для задачи (MDP) в° [•] к(х0) = 0 с (которая подразумевает в” [•] (х0) = 0) по

лучаются аналогично Теореме 2.2 из [1]. Оптимальность решения (X ,a°, ß° ) для задачи (MDP) получается аналогично Теореме 3 из [4].

Теорема 2.5. (Строго обратная дуальность). Пусть X1 допустимое решение задачи (VP) и пусть (и°,a°,ß°)допустимое решение дуальной задачи (MDP). Допустим, что и° является единственным оптимальным решением задачи (P)(u0,a0,ß0 ) (или любое из условий (b) и (d) из теоремы 2.2, или (d) и (f) из теоремы 2.3), и

at [•] ф»)=a [.]( f{u^[+]ß,i[-g!i(u") e) (27)

Тогда и ° = X и X0 является оптимальным решением задачи ( VP) . Доказательство: Имеем ßj [.] gJi (x°)< 0. Если ßJ [.] gJi (x0)< 0 то из (27)

a"[•]((x“)[+]ß0, [•]gj, (X))<«"[•]( f(и°)[+]ß0 [.]gji (u")e). (28)

что противоречит условию оптимальности и0 для задачи ( P)(0 a0 ß0 ). То есть мы имеем.

ßJ,[.] gj, ( x0 ) = 0       (29)

И из (27) получим,

a" [•] f (X )[+KH g^ )e = a° [•]( f (и" )[+]ßJi [•] gj, (и° ) e) (30)

Так как и является единственным оптимальным решением задачи

Получим и° = X из (30). Далее из леммы 2.2, (29) и из (1) и (2) не существует такой X G X , чтобы f ( x) < f (и» )= f (/ ) для всех i G P и

f, (x) < fi ( X ) хотя бы для одной i G P ; то есть X оптимальна для задачи ( VP) . Доказательство завершено.

ЛИТЕРАТУРА

Weir T., Mond B. Generalized convexity and duality in multiple objective programming, Bull. Austral. Math. Soc. 29 (1989). РР. 287-299.

Weir T. A duality theorem for multiple objective fractional optimization problem, Bull. Austral. Math. Soc. 34 (1986). РР. 415-425.

Egudo R.R. Efficiency and multiobjective duality in non-linear programming, J. Inform. Optim. Sci. 8 (1987). РР. 155-166.

Egudo R.R. Efficiency and generalized convex duality for multiobjective programs, J. Math. Anal. Appl. 138 (1989). РР. 84-94.

Preda V. On efficiency and duality for multiobjective programs, J. Math. Anal. Appl. 166 (1992). РР. 365-377.

Hanson M.A., Mond B. Further generalizations of convexity in mathematical programming, J. Inform. Optim. Sci. 3 (1982). РР. 22-35.

Vial J.P. Strong and weak convexity of sets and functions, Math. Oper. Res. 8 (1983). РР. 231-259.

Mukherjee R.N. Generalized convex duality for multiobjective fractional programs, J. Math, Anal. Appl. 162 (1991). РР. 309-316.

Avriel M. Nonlinear programming: Analysis and Methods, Prentice-Hall, Englewood Cliffs, NJ. 1976.

MIXED DUALITY TYPE IN THE MULTIOBJECT OPTIMIZATION PROBLEMS USING GENERALIZED ALGEBRAIC OPERATIONS

K. Petrosyan

In this article we discuss the following multiobjective nonlinear problem of optimizations: (VP)min f (x), g (x) < 0, x e C Where f = ( f, f2,…, / ) : R" ^ Rp,

g = (, g2,…, gm): R" ^ Rm, f and g(h,<p) — are differentiable functions, and

minimum is meant to be taken in meaning of pareto. Some theorems of duality are obtained between solutions of this problem, and corresponding to it mixed-type dual problem, where are used concepts of generalized algebraic operations and (h, <p)differentiability.

Keywords. Generalized algebric operations of Ben-Tal, (h, <p) — sublinear functional, mixed-type dual problem, weak pareto solutions.

УДК 519.17

О ПАРАМЕТРАХ |дп, |д12 И |д22 ПОЛНЫХ ДВУДОЛЬНЫХ ГРАФОВ

А.М. Хачатрян

Иджеванский филиал Ереванского Государственного Университета

Для любых натуральных чисел т и П найдены точные значения параметров Д11, д12 и д22 полного двудольного графа Ктп.

Ключевые слова: полный двудольный граф, реберная раскраска, интервальный спектр.

Введение. Обозначения, определения, цель работы

В работе рассматриваются неориентированные связные графы без кратных ребер и петель [1], содержащие хотя бы одно ребро. Множество вершин графа С обозначаем через У(С), множество ребер через Е(С) . Степень

вершины X в графе С обозначаем через бС (х), наибольшую из степеней вершин графа С через А (С).

Если Б непустое конечное подмножество множества N натуральных чисел, то через 1(Б) и ЦБ) обозначаем, соответственно, его наименьший и наибольший элемент. Непустое конечное подмножество Б множества N назовем интервалом, если из 1 є N , 1(Б) < 1 < Ь(Б) вытекает 1 є Б . Интервал Б с

1(Б) = д, |Б| = Ь обозначаем через 1п1(д,Ь).

Правильной реберной 1 — раскраской (1 є N) графа С назовем функцию ф :Е(С) ^ 1п1 (1, 1) , удовлетворяющую условиям:

для VI, 1 < і < 1, существует хотя бы одно ребро Є(і) є Е(С) с ф(е(і)) = і;

для любых двух смежных ребер е’ є Е(С) , е" є Е(С) ф(е’) Ф ф(е") . Наименьшее значение 1 , при котором существует правильная реберная 1 раскраска графа С , обозначается через х'(С).

Множество всех правильных реберных t — раскрасок графа G, где Xf(G) < t < |E(G)|, обозначим через a(G, t).

Определим множество a (G) всех правильных реберных раскрасок графа G :

|E(G)|

a(G) = У a(G,t).

t=X'(G)

Если фєа (G) и x є V (G), то множество { ф(е) / Є є E (G) , e смежно с x } назовем спектром вершины x графа G при раскраске ф и обозначим через Sg(x, ф) ; если Sg (x, ф) является интервалом, то скажем, что ф интервальна в x ; через fG (ф) обозначим число |{ z є V(G) / Sg (z, ф) является интервалом}|.

фєа (G) назовем интервальной раскраской графа G , если fG (ф) = |V(G)|.

Определение интервальной реберной раскраски графа было дано в [2].

Поскольку не для всех графов существует интервальная реберная раскраска (простейшим примером служит граф К3), то возникает важная задача исследования для данного графа G поведения функции fG (ф) при ф єа (G, t) и t, удовлетворяющем неравенству x(G) < t < |E(G)|. Изучение этой задачи было начато в [3].

Для графа G и натурального числа t, удовлетворяющего неравенству X'(G) < t < |E(G)| , положим [3]:

Ui(G,t) = min fG(9);

фєа (G,t)

М-2 (G, t) = max ^gM .

фєа (G,t)

Для графа G положим [3]:

un(G) = min u,(G,t);

^11V ‘ X,(G)<t<|E(G)|

u12(G) = max u,(G,t);

^12      x4G)<t<|E(G)|

u 21 (G) = min u 2 (G, t);

^21V ‘ x’(G)<t<|E(G)|

u 22(G) = max u 2(G,t).

^22V ‘ X'(G)<t<|E(G)r2

Очевидно, что параметры Un, U12, U21 и U22 корректно определены для

любого графа. Их точные значения найдены для простых цепей, простых циклов, простых циклов с одной хордой, «лестниц Мебиуса» и для полных графов [3-5]. Точные значения параметров u11 и u22 для деревьев найдены в [6]. Точное значение параметра д12 для деревьев найдено в [7].

Если С граф с х'(С) = А (С), А (С) < 1 < |Е(С)|, £ є а(С,1) , то для любого ] 1 <]< 1, обозначаем Е(С,£,] “{еє Е(С)/£(е) = ] ; £ назовем гармонической 1 — раскраской графа С, если для VI, 1 < і < А (С), подмножество

и Е(С,£, ] ребер графа С является паросочетанием [1].

і< ]< і >і(шо^А (С)))

Пусть С граф с х (С) =А(С), А(С) < 1 <|Е(С)|, и £ его гармоническая 1-раскраска. Определим последовательность £0, £Ц, … , £*-х'(С) правильных реберных раскрасок графа С следующим образом:

если 1 = х'(С), то £0 “£ ,

если    1 >х'(С) + 1, то £0 “£, а для V], 1 < ] < 1 — х'(С), и для Ve є Е(С)

£* () = |^н(е),  если £*(е) * Щ^-ДеЭ/е є Е(С)}) £](е) “{^(е)-А(С), если ^(е) = Ц{£*,(е)/еєЕ(С)}) .

Замечание 1. Пусть С граф с х'(С) =А(С), А(С) < 1 < |Е(С)|, и £ его гармоническая 1-раскраска. Все раскраски £0, £1, … , £*-х'(С) определяются однозначно.

Замечание 2. Пусть С граф с х'(С) = А(С), А(С) < 1 < |Е(С)|, и £ его гармоническая 1 — раскраска. Легко видеть, что для V], 0 < ‘] < 1 — х'(СЬ £* является гармонической (1 ]) — раскраской графа С.

Замечание 3. Пусть С граф с х'(С) = А(С), А(С) < 1 < |Е(С)|, и £ его гармоническая 1 — раскраска. Вершина 20 є V (С) такова, что а^) = а(с) и £ интервальна в г0. Тогда для V], 0 < ] < 1 — Х'(С), £ * интервальна в г0.

Целью работы является вычисление точных значений параметров , д12

и д22 полного двудольного графа Кш п при любых натуральных ш и п. Для

достижения цели использованы методы теории графов и теории комбинаторных алгоритмов.

Всюду в работе, при рассмотрении любого полного двудольного графа ^ полагаем что ш > n, V(Kш,n) = {х1 … , xn, Уl, … , Уш}, Е(Кш,п) = {(х^ У])/ 1 < і < n, 1 < ] < ш} . Очевидно, при любых натуральных m> П X'(Km,n) =A(Km,n) = m

Результаты

Утверждение 1. Для любых m е N , n е N имеет место равенство

m +1, если n = 1 MKm,n) =“1, если m = n = 2

в остальных случаях.

Доказательство.

Случай 1. n = 1.

Ясно, что Km n дерево, и поэтому в рассматриваемом случае доказываемое равенство вытекает из результатов работы [6].

Случай 2. m = n = 2 .

Ясно, что Kmn = C4, и поэтому в рассматриваемом случае доказываемое

равенство вытекает из результатов работы [4].

Случай 3. m > 3, n = 2 или m > n > 3.

Определим функцию ф:E(Kmn) ^ Int(1,m + n-1). Для любых натуральных i, j, удовлетворяющих неравенствам 1 < i < n, 1 < j < m, положим:

1,         если i = n, j = m

ф((х.^)) = < i + j-1, если 1 < i < n-1, 1 < j < m-1

i + j, если i = n, 1 < j < m — 1 или 1 < i < n — 1, j = m .

Легко видеть, что феа (Km n,m + n — 1) и fK (ф) = 0.

m,n      Km,n

Утверждение 1 доказано.

Лемма. Для Vn е N и Vфеа(Kn+1n,n + 1) fK i (ф) = n + 2.

Доказательство. Выберем произвольное n е N и рассмотрим произвольную раскраску феа(К+1n,n + 1). Ясно, что для Vi, 1 < i < n,

SK (x., ф) = Int(1, n +1). Так как для Vt , 1 < т< n + 1, подмножество

Kn+1,n 1

E(Kn+1n, ф, t) является паросочетанием мощности n в графе Kn+1n, то для каждого из этих значений т существует единственное j(ф, т) , где 1 < j^, т) < n +1, для которого т£ SK i (yj(фт), ф) . Отсюда, из соотношения

феа(К^+1,n,n + 1) и равенства dKn+1n (У1) = dKn+1n (У2) = … = dKn+1n (Уп+1) = n вытекает, что для любых тх,т2, удовлетворяющих неравенству 1 <тх <т2 < n +1,

верно неравенство ](ф, т1) Ф ](ф, т2) . Отсюда следует, что БК 1 (У](ф1), ф) и

Ч+1,п(У](ф, П+1),

ф) являются интервалами, а для VI, 2 < т< П, Бк 1 (Укф т), ф) не является интервалом. Следовательно, !к 1 (ф) = П + 2 .

Лемма доказана.

Утверждение 2. Для любых т е К, П е N имеет место равенство

подпись: м12 (кт,п)т + п, если п = 1 или т = п т +1, если п Ф1 и т п = 1 п, если п Ф1 и т п > 2.

Доказательство.

Случай 1. П = 1.

В рассматриваемом случае Ктп дерево, и поэтому доказываемое

равенство вытекает из результатов работы [7].

Случай 2. т = п .

В рассматриваемом случае Кт П является регулярным графом, и поэтому

доказываемое равенство вытекает из результатов работы [4].

Случай 3. п ф 1 и т п = 1.

Из леммы вытекает, что в рассматриваемом случае для Vф е а (Кт П,П +1) ^ (ф) = П + 2 , откуда следует равенство ц1 (Кт П ,П +1) =

= П + 2 . Очевидно, для установления нужного равенства достаточно показать, что для VI, т < 1 < тп , имеет место неравенство цх(Кт П, 1) < П + 2 .

Определим функцию у :Е(Ктп) ^ 1п1(1,тп) : для любых натуральных

^, удовлетворяющих неравенствам 1 < i < П, i < j < т, положим

у ((х^)) = (т 1)(i -1) + j ; для любых натуральных ^, удовлетворяющих

неравенствам 2 < i < П, 1 < j < i — 1, положим у((х^)) = (т 1)i + j +1.

Легко видеть, что у является гармонической тп — раскраской графа Кт П

с ^ (у) = П .

1Чт,п

Нетрудно убедиться, что для Vp,0 < р < тп т, И для V], 1 < j < П — 1, 5К (у], Ур) не является интервалом.

1Чт,п ^ J г

Следовательно, для Vp,0 < р < тп т , ^ (ур) < П + 2. Отсюда и из за1     1          Кт,п    р

мечания 2 следует, что для VI, т < 1 < тп, верно неравенство

^1(Кт,п,1) < П + 2.

Случай 4. п Ф 1 и т п > 2.

Очевидно, в рассматриваемом случае для Vфеа(Kmn,m) и VI, 1 < 1 < П , имеет место равенство БК (х., ф) = ГпЩ т) , и поэтому fK (ф) > П ,

кт,п 1  кт,п

ц1 (Ктп,т) > П. Покажем, что ц1(Ктп,т) < П. Очевидно, для установления последнего неравенства достаточно указать раскраску р0 еа(Ктп,т) с

^ (Ф0) = п.

1Чт,п ‘ и

Определим функцию р0 :Е(Ктп) ^ Ш(1,т) . Для любых натуральных 1, ^ удовлетворяющих неравенствам 1 < 1 < п — 1, 1 < j < т, положим р0 ((х;, Уj)) = j — 1 +1; для j , удовлетворяющих неравенству п +1 < j < т , положим ф0((хп,у^) = j-п; для любых натуральных 1^, удовлетворяющих неравенствам 2 < 1 < п -1, 1 < j < 1 — 1, положим р0 ((х; ,Уj)) = т — 1 + j +1; для j , удовлетворяющих неравенству 1 < j < п , положим р0 ((хп, у^) = т п + j. Легко убедиться, что р0 е а(Кт п ,т) , fк (ф0) = п .

Таким образом, (Кт п ,т) = п .

Очевидно, для установления нужного равенства достаточно показать, что для VI, т < 1 < тп , имеет место неравенство цх(Кт п, 1:) < п .

Определим функцию 9 :Е(Ктп) ^ 1пЦ1,тп): для любых натуральных

j, удовлетворяющих неравенствам 1 < 1 < п — 1, 1 < j < т, положим 9((х1,у])) = (т — 1)(1 — 1) + j; для j, удовлетворяющих неравенству п +1 < j< т, положим 9((хп,у^) = т(п-1) + j-п; для любых натуральных 1^, удовлетворяющих неравенствам 2 < 1 < п — 1, 1 < j < 1 — 1, положим 9((х1,у])) = (т — 1)1 + j +1; для j , удовлетворяющих неравенству 1 < j < п , положим 9 ((хп, Уj)) = тп п + j.

Легко видеть, что 9 является гармонической тп — раскраской графа Кт п , интервальной в х; для V!, 1 < 1 < п. Нетрудно убедиться, что для Vp,0 < р < тп т, и для V], 1 < j < т, БК (yj, 9р) не является интервалом. Отсюда и из замечания 3 вытекает, что для Vp,0 < р < тп т , верно равенство ^ (9р) = п . Отсюда и из замечания 2 следует, что для VI, т < 1 < тп ,

Кт,п р

Ш (Кт,п , 1) < п.

Утверждение 2 доказано.

Утверждение 3. Для любых т е М п е N имеет место равенство

^22 (Кт,п) = т + п.

Доказательство вытекает из результатов работы [8].

ЛИТЕРАТУРА

Harary F. Graph Theory. Addison-Wesley, Reading, MA, 1969.

Асратян А.С., Камалян Р.Р. Интервальные раскраски ребер мультиграфа // Прикладная математика, Вып. 5, ЕГУ, 1987. СС. 25-34.

Давтян Н.Н., Камалян Р.Р. О границах экстремумов числа вершин с интервальным спектром во множестве правильных реберных t-цветных раскрасок «лестниц Мебиуса» при варьировании t // Сборник научных статей Годичной научной конференции (5-10 декабря 2008г.) Российско-Армянского (Славянского) университета. Ер.: Изд-во РАУ, 2009. СС. 81-84.

Давтян Н.Н., Камалян Р.Р. О свойствах числа вершин с интервальным спектром в правильных реберных раскрасках некоторых графов // Вестник Российско-Армянского (Славянского) университета. Серия физико-математические и естественные науки, № 2, 2009. СС. 33-42.

Хачатрян А.М. О границах экстремумов числа вершин с интервальным спектром во множестве правильных реберных t-цветных раскрасок полных графов при варьировании t // Сборник научных статей Годичной научной конференции (6-10 декабря 2010г.) Российско-Армянского (Славянского) университета, в печати.

Давтян Н.Н. О наименьшем и наибольшем возможных числах вершин с интервальным спектром на множестве правильных реберных раскрасок дерева // Матемагические вопросы кибернетики и вычислительной техники. Т. 32. Ер., 2009. СС. 107-111.

Давтян Н.Н., Камалян Р.Р. О параметре ц12 дерева // Сборник научных статей Годичной научной конференции (30 ноября 4 декабря 2009г.) РоссийскоАрмянского (Славянского) университета. Ер., Изд-во РАУ, 2010. СС. 149-151.

Камалян Р.Р. Интервальные раскраски полных двудольных графов и деревьев // Препринт ВЦ АН Арм. ССР и ЕГУ. Ер., 1989. 11 с.

ON PARAMETERS , ^12 AND ^22 OF COMPLETE BIPARTITE GRAPHS A.M. Khachatryan

Материал взят из журнала Вестник выпуск Физико-математические и естественные науки