Су „Св. Климент Охридски
Изтегляне 278.49 Kb.
|
- Навигация на страницата:
- 4.2. Glue алгоритми
- 4.3. Описание на glue алгоритъм
- Теорема 4
- Констуиране на обширни примери на LP
- Непосредтвено търсене
- [Ka1]
- [Sch]
Таблица 1: Граници за e (G ) в (4,5,n )-good графи G от LPi , 0≤ i≤ 3. Таблица 1 показва резултатите от оптимизирането на броя на ребрата е за LPi , 0≤ i≤ 3. Всички резултати, с изключение на тези за LP0, не дават приемлив резултат за n = 28. Минимизацията на ∆ = g  + h - n в LP3 за n = 27 дава 4, тогава във всеки (4,5,27)-good граф G има поне 4 върха x V (G) и такива, че:
(а) F (b) H За F 4.2. Glue алгоритми: Ако разполагаме с (3,5,n )-good граф F и (4,4,m)-good граф H, използвйки този тип алгоритми може да намерим всички (4,5,n +m+1)-good графи G такива, че за някой връх x V (G), графите F и H са изоморфни съответно на F и H. Подобни методи за намирането на (3,l )-good графи са описани в [MZ,RK].
Макар да изглежда достатъчно ясно какво трябва да се напарави, е доста трудно да се постигне достатъчна ефективност, затова glue алгоритъма, който трябва да използваме в нашият случай, поставя едни от най-сложните изисквания измежду всички останали алгоритми от този тип. Brendan McKay и Stanislaw Radziszowski прилагат два независими glue алгоритъма. Единият следва предишни одходи за разрешаване, а втория е описан накратко по-надолу. 4.3. Описание на glue алгоритъм: Нека v е връх на граф G, чиято околност поражда графа. Задата на glue алгоритъма е за всяка двойка от върхове x , y такава, че x V (F) и y V (H), да реши дали {x ,y } е ребро от G. Тези двойки са nm, което е твърде голям брой ако са прилага подход, при който всяка двойка се разглежда като 0-1 променлива. Алгоритъмът споменат в предишният абзац, както и единият от алгоритмите използвани от Brendan McKay и Stanislaw Radziszowski работи с определени множества от променливи, като например множества от ребра с общ връх x V (F) и някоя крайна точка на V (H). Нека наричаме такива множества конус с връхна точка x. Вторият използван алгоритъм се отнася до регулярни множества от конуси.
Нека LH да е мрежа от всичко подмножества на V(H), където е включена частична наредба. Ако s≤ S (s  S V (H)), тогава с LH(s ,S) ще означаваме подмрежа на LH образувана от всички u такива, че s ≤ u ≤ S. Размерността на L = LH(s, S) ще означаваме с dim (L) и тя е равна на |S| - |s|. Да отбележим, че L има 2 елемента, всеки един от които ще разглеждаме като потенциален кандидат за основа на конус. За всяко x V (G), регулярно множество от конуси ще бележим с Reg (x ,s ,S) т.е. множество което съдържа всички конуси с връх x и основа от LH(s, S). За всяко u V (H) нека с α(u) и β(u) да означим кликите и независимите подграфи на H породени от u. Да предположим, че C и R, за 1 ≤ i ≤ 2, са конус и регулярно множество от конуси и са такива, че C = (x, u), s ≤ u≤ S и R=Reg (x ,s ,S). Да отбележим, че ако C и C са от G, тогава ако {x, x} е ребро от F, то α(s ) ≤ 1. Ако {x, x} не е ребро на F, тогава β( ) ≤ 2. Тези условия позволяват елиминирането на голям брой възможни двойки от конуси и то след само един тест не регулярните множества R и R, тъй като α(u) и β(u) се изчисляват само по веднъж за всички u LH. Използва се рекурсивен алгоритъм за определянето на множесвото от конуси за всеки връх на F. Ако разглеждаме само регулярни множества R = Reg (x ,s ,S) с s =S т.е от нулева размерност, този подход е еквивалентен на работа с прост конус. Ако рамерността на R е голяма можем да го разделим на две регулярни множества с по-малка размерност. Ако резмерността на регулярните множества се поддържа в някакви средни граници, то ефективността на този алгоритъм надминава тези на предишните методи.
Таблица 2 съдържа известните стойности и граници за e (4,5,n ) и E (4,5,n ), които Brendan McKay и Stanislaw Radziszowski установяват с този алгоритъм. точните стойности са намерени с помоща на точно дефинирани номерация. За границите – горната граница за E () и долната граница за e () са получени чрез оптимизиране на съответните случаи на LP3, с изкючение на границата 151 на E(4,5,26), която е получена от glue алгоритъм. горните граници за e () и долните граници за E () са остановени чрез констуирани графи. Повечрто от тях могат да бъдат подобрени с иключение на 116 и132 за n = 24, за които се смята,че са истинските стойности. В момента са известни над 300000 неизоморфни (4,5,24)-good графи, остновени чрез търсене в по-малко множество получен от glue алгоритъм. нито един от тези графи не се разширява до (4,5,25)-good граф.
Резултатите получено от двата алгоритъма съвпадат за положителни конструкции и твърдят, че (4,5,27)-good граф не съществува в всеки от 80 случая описани в (а) и (б) по-горе. Отук получаваме и новата горна граница за R (4,5) 27. алгоритъмътизползван от Brendan McKay и Stanislaw Radziszowski не е подходящ за установяване на това дали 26 не е по-добра горна граница, тъй като разглежданите случаи са значителни повече. броя на тези случаи може да се намали ао се открие по силна система LP4 или чрез по детайлно изследване на LP3. Директното прилагане на теорема 1(както в [MR2]) към резултатите от LP3 показва, че R(5, 5) ≤ 52 т.е. с 3 по-малко от получената от Уокър граница през 1971 [Wa2]. Аналогично, известните вече стойности за E (3,6,n ) [MZ,RK], долните граници за e (4,5,n ) от таблица 2 и теорема 1 показват, че подобрение на R (4,6)≤44 [Wa2] с 1. Получаваме следната теорема:
За постигането на описаните по-горе резултати за изполявани различни алгоритми и в следващете няколко абзаца ще се спрем на някои от тях и на приложението им за търсене на други графи на Ремзи, както и в други комбинаторни задачи. За изучаването на (5,5)-good и (4,6)-good графи са необходими познания за (3,6)-good и (4,5)-good (както и за (5,4)-good) графи. Всички (3,6)-good графи са известни [MZ,RK], така че е възможно прилагането на тази техника за получаването на по=добри резултати за горните граници за R (5,5) и R(4,6). Основни софтуерни компоненти за извършването на тези подобрения са:
Николай Хаджииванов. „Числа на Рамзи”, Народна Просвета, София, 1982 г. Маршал Хол – Комбинаторика, „Мир”, Москва 1970 За 4 част: [Ka1] J.G. Kalbfleisch, Construction of Special Edge-Chromatic Graphs, Canadian Math. Bull., Vol. 8 (1965) 575-584. [Ka2] J.G. Kalbfleisch, Chromatic Graphs and Ramsey’s Theorem, Ph.D. thesis, University of Waterloo, January 1966. [Mc] B.D. McKay, Nauty User’s Guide (Version 1.5), Technical Report TR-CS-90-02, Computer Science Department, Australian National University (1990). [MR1] B.D. McKay and S.P. Radziszowski, The First Classical Ramsey Number for Hypergraphs is Computed, Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’91, San Francisco, (1991) 304-308. [MR2] B.D. McKay and S.P. Radziszowski, New Upper Bound for the Ramsey Number R (5,5), to appear in Proceedings of Sixteenth Australasian Conference on Combinatorial Mathematics and Combinatorial Computing. [MZ] B.D. McKay and K. Zhang, The Value of the Ramsey Number R (3,8), to appear. [RK] S.P. Radziszowski and D.L. Kreher, On R (3,k ) Ramsey Graphs: Theoretical and Computational Results, Journal of Combinatorial Mathematics and Combinatorial Computing, 4 (1988) 37-52. [Sch] L.E. Schrage, User’s Manual for LINDO, The Scientific Press, 1981. [Wa1] K. Walker, Dichromatic Graphs and Ramsey Numbers, Journal of Combinatorial Theory, 5 (1968) 238-243. [Wa2] K. Walker, An Upper Bound for the Ramsey Number M(5,4), Journal of Combinatorial Theory, 11 (1971) 1-10. Каталог: files -> files files -> Р е п у б л и к а б ъ л г а р и я files -> Дебелината на армираната изравнителна циментова замазка /позиция 3/ е 4 см files -> „Европейско законодателство и практики в помощ на добри управленски решения, която се състоя на 24 септември 2009 г в София files -> В сила oт 16. 03. 2011 Разяснение на нап здравни Вноски при Неплатен Отпуск ззо files -> В сила oт 23. 05. 2008 Указание нои прилагане на ксо и нпос ксо files -> 1. По пътя към паметник „1300 години България files -> Георги Димитров – Kreston BulMar files -> В сила oт 13. 05. 2005 Писмо мтсп обезщетение Неизползван Отпуск кт Изтегляне 278.49 Kb. Сподели с приятели:
|