ПРИКЛАДНI ЗАДАЧI МЕТОДУ j-ПЕРЕТВОРЕНЬ ГРАФІВ

В. I. Петренюк

За два минулих десятиріччя стався бурхливий розвиток теорії графів   зокрема її найважчої та найзмістовнішої топологічної частини теоріі укладань графів на 2-многовиди,   вивчення   структури графів заданного роду, оцінка роду композиції графів виражена через роди їхніх частин, декомпозиція графів відносно інших   топологічних інваріантів. Зокрема було отримано один з найглибших результатів-теорему Робертсона-Сеймура згідно якої в нескінченій множині графів існують два таких, що один є мінором іншого,тобто шляхом зтягування   та вида лення ребер одного графа можливо отримати інший граф.

Якщо рані ше е перспективних методів в топологічній теорії графів було два : м етод обертань та метод j -перетворень, то зараз таким є метод мінорів. Зауважимо, що автором методу j -перетворень графів Хоменком М.П. було отримано результат аналогічний вищезгаданаму ще у 1973р.

Робочим методом автора є метод j -перетворень графів як топологічних просторів. Основна задача полягала у оцінці роду графа як j -образа настунніх   j -перетворень :

-деякого площинного графа та зірки заданого на множині точок   із числом досяжності більше 1 ;

- деякого площинного графа та графа К ₄ , чи К _2,3   на множині точок   із числом досяжності більше 1 ;

  -графів К _3,3 чи К ₅ та графів К ₄ чи   К _2,3   на множині точок   із числом досяжності   1 ;

   Отримані результати роздруковувалися   здебільшого як препринти чи депонувалися в ДНТБ (УкрНІІНТІ) , тому є маловідомими   широкому загалу. Нашою метою буде ознайомлення i з ними за розбитим на групи списком л i тератури.

           Стосовно   оц i нювання роду графа ( spliticial ) як j -образа деякого площинного графа та графа К ₄ , чи К _2,3   на множині точок   із числом досяжності більше 1 було отримано деякий результат частково надрукований в [27]. А саме::

Нехай - простий скінчений граф без кратних ребер та петель,   , та для деякої множини точок   , визначене число . Під точкою графа розумітимемо або вершину або якусь внутрішню точку ребра. Для графа   маємо       та , де   - точка ребра , - пара несуміжних ребер графа ; зауважимо, що пари кінцевих вершини цих ребер розділяють одна одну на площіні. Тобто маємо співвідношення для :

Для   має місце наступне співвідношення:

Зауважимо, що , - 2 мінімальні графи. З адача полягатиме у визначенні ейлерового роду графа , який є - оброзом площінного - мінімального графа та   , , отриманного наступним - перетворенням: , де   ,

таким, що задовольняє наступним умовам ; причому, якщо

В [15-21} розглянуто наступні питання:

-              структура площинних графів із заданим   числом досяжності   деякої підмножини   множини їх точок,

-              спеціальний   клас площиннх графів, оцінка роду спеціальних       графів,

-              список   3-м і німальних площинних графів площинних графів,

-              про алгоритм встановлення 3-властивості   графів, характеризація спеціальних площинних графів.

В   [1-14] розглянуто:

-      структурні властивості площинних графів із заданою множиною точ o к   дос я ж ною на тор і ,

-              про к-планарні графи,

-              узагальнена q -характеристика деякої підмножини   множини   точок площинного графа,

-                дві характеристики   дуального графа площиного графа,

-              узага л ьнена оцінка роду простого графа як j -образа

деякого площинного графа та зірки,

В   [26] розглянуто задачу про знаходження oц i нки роду графа, який розбито на два п i дграфа меншого роду i з трьома сп i льними вершинами.

В   [27] розглянуто наступні питання:

  структурн і властивості   площинних графів із заданою множиною точок   досяжності більше 1 для ототожнення із усіма множинами вершин графа К _2,3 ,

  структурн і властивості   площинних графів із заданою множиною точок   досяжностію більше 1 ототожнення із множинами вершин графа К ₄ ,  

  оцінка роду j -образа t -мінімального площин ого графа та графа К4 , заданого на множинах точок досяжності більше 1.

Ненадрукован о   наступні результати :

  j -перетворення графа К _3,3 та К ₄ , К _3,3 та К _2,3 , j -перетворення графа К ₅ та К ₄ , К ₅ та К _{2, 3} та списки 4-мінімальних плоских і 2-незведених графів.

Список лiтератури  

1. Two Characteristics of the Planar Graph Dual Graph. Materials of the International Conference “Artificial Intellect. Intellectual and Multiprocessor Systems – 2004”. September 20-25, 2004, Crimea, Ukraine pp. 230-231.

2. Generalized Estimation of the Simple Graph Genus. The research collection “Artificial Intellect.” vol 4, 2004 pp. 34-45.

3. Some Applications of fi-method. The Fourth European Congress of Mathematicians. Stockholm 2004, poster session #6-19.

4. Algorithms of Construction Special Graph.Works of 8-th seminar on discrete mathematics. Moscow, MGU, 2004 pp 353.

5. Graph-modelling Approaches to the Complex Automated System. The Collection of Scientific jobs of the Kirovograd State Technical University / Engineering in agricultural manufacture branch mechanical engineering, automation. - Kirovograd , vol 14, 2004. pp 513-516.

6. Software of Algorithms of Modeling of movement wheel of Machines. The collection of scientific jobs of the Kirovograd state technical university / Engineering in agricultural manufacture branch mechanical engineering, automation. - Kirovograd, 2004,vol 34. pp.312-318.

7. About the k- planar Graphs. preprint of DNTB14.07.03   \#97-2003 of WINITI 9(379)   #78 18p.

8. The Generalized Q-characteristic the of.the Planar graph. preprint DNTB 14.07.03 #98-2003 of WINITI 9(379) #79 10p.

9. The Generalized Estimation of the Genus of the Simple Graph. preprint DNTB 14.07.03 #100-2003 9 (379) #81 18p.

10. Two Characteristics of the Dual Graph of.the Planar Graph. preprint DNTB 14.07.03 #99-2003 9 (379) 80 13p.

11. The Structheral Property of Graph-models on Torus. Kremenchug, Scientifical works of KDTU vol.#3(20) 2003, pp.75-79.

12.  About the Property of the Planar Graph-model. Kiev, V-conference ''UPSA-.2003'', pp.92-93

13. Generalized Characteristic of Set of Points of the Planar Graph-models. Dnepropetrovsk,\ conf. ''Ukraine-scientific-2003'' vol.#30, 38-40pp.

14. Structural Properties Planar Graphs with Some set of Points set Achievable on Torus. preprint DNTB      14.07.03 #96-2003 of WINITI 9 (379) #77 19p.

15. Characterization of the Special Planar Graph. preprint DNTB 17.04.90 754-90 30p.

16. (in the co-authorship) About Building KD(21) by means the Performance.\ Collection of the proceedings of   a seminar of discrete mathematics\ and applications. Moscow, MGU 1997 pp.166-167.

17. Characterization of the 3-minimal Planar Graph. Collection of the proceedings of   a seminar of discrete mathematics\ and applications. Moscow, MGU 1998 p.217

18. About Algorithm of an Establishment of 3-property   of Planar Graphs..preprint DNTB 11.03.90 #428-90 23p.

19. About Structure of Planar Graphs with the Given Reachability Number of some set of their Points. preprint DNTB 22.09.1986 #2245-86. 51p.

20. About an Estimation of the Genus of Special Graphs. preprint DNTB 22.09.1986 2259-86 32p.

21. List of 3- minimal   Planar Graphs. preprint DNTB 31.10.86 #2450-86. 7p.

22. About one Approach to Description of Unigraphs. I. preprint DNTB 12.11.86. \#2570- 86 51p.

23. About one Approach to Description of Unigraphs. II. preprint DNTB 12.11.86. \#2569- 86 28p

24. About one Characteristic of the Planar Graph. preprint DNTB 09.08.1985 #1761-85 2p.

25. About one Class Planar Graphs. preprint DNTB 09.08.1985 #1760-85 35p.

26. Nature   of the genuse of 3-amalgamation graphs.(to appeare in the research collection “Artificial Intellect.”)

27. Upper   Estimation of the Genus of Spliticial Graphs. .\ Collection of   proceedings of   a seminar of theoretical cybernetics and applications.Penza, 2005 pp.116