Задача за запознанства, TST Монголия 20...г.

[drago]

Oт две седмици ми е хванала окото една задача, която стои нерешена в в artofproblemsolving.
Тя е за някакви запознанства м/у 2 групи хора, но аз ще я цитирам на езика на графите.

Имате граф [tex]G[/tex], върховете му са: [tex]V(G)= \Gamma_1 \cup \Gamma_2, \, |\Gamma_1| = |\Gamma_2| = n[/tex]. Няма свързани върхове вътре в [tex]\Gamma_1[/tex] и в [tex]\Gamma_2[/tex] (bipartite graph).

За всеки връх [tex]v \in V(G)[/tex], за ребрата [tex]d(v)[/tex] инцидентни с него имаме:
[tex]d(v) \leq d < \frac{n}{2}[/tex], където [tex]d[/tex] е естествено число.

Докажете, че може да добавим още известно количество ребра в [tex]G[/tex], т.е. да свържем още някои двойки върхове [tex]v_1v_2, \, v_1 \in \Gamma_1,\, v_2 \in \Gamma_2[/tex],така че за новия граф от всеки връх да излизат точно [tex]2d[/tex] ребра.

[ptj]

Ако [tex]d=1[/tex], то очевидното решение е допълване до хамилтонов цикъл. Вероятно тази идея може да се приложи и в общия вариант. Т.е. да се докаже , че съществува обединение на [tex]d[/tex] на брой непресичащи се (без общи ребра) хамилтонови цикла през всички върхове, така че графа G да е техен подграф. Подходящ начин е с някоя конструкция и индукция.

П.П. От казаното даже веднага се вижда решението- новите ребра се включват в нов цикъл.

[drago]

Ptj, или напиши читаво решение или недей спами!

[ptj]

Идеята е вървяща, но не знам кога ще намеря време да я формализирам, не е спам. Единствената подробност е, че в индукцията ще се иска на предната стъпка да бъдат реализирани всички възможни решения с хамилтонови цикли.

[drago]

@ptj: Някакво развитие?

[ptj]

Не ми е дошла музата да го опиша, а и отдавна не съм писал за графи. Но самата идея мисля, че е безпроблемна.

[drago]

Едно е да мислиш, друго е да стане!
Най-добре го напиши! Това е момента на истината.

[ptj]

O.K. Засега идейно:

1. Нека [tex]G_1[/tex] е произволен граф с [tex]2n[/tex] върха и [tex]n[/tex] ребра, така че всеки връх от него е инцидентен точно с един. Образуваме множеството на всички графи [tex]M_1=[/tex]{[tex]G_1'[/tex]}, получени от [tex]G[/tex] чрез добавянето на ребра до образуването на хамилтов цикъл в него (през всички върхове). Очевидно те изпълняват условието на задачата.

2. Нека за всички графи [tex]G_d[/tex] с върхове разделени на 2 групи от по [tex]n[/tex] (на брой), и ребра само с краища в двете от тях (максималната инцидентност за връх не надвишава [tex]d[/tex]) е изпълнено:
Могат да се добавят определен брой ребра, така че всеки от тях (графа [tex]G_d')[/tex] да съдържа точно [tex]d[/tex] на брой хамилтонови цикли, нямащи общи ребра помежду кои да е два от тях. Нека това множество означим с [tex]M_d[/tex] .

3. Нека вземем граф [tex]G_{d+1}[/tex] (аналогично на т.2 , но с максимална инцидентност за връх [tex](d+1)[/tex]. Като отделим по едно ребро от всеки връх може да получим два нови графа [tex]G_d[/tex] и [tex]G_1[/tex], така че [tex]G_{d+1}=G_d\cup G_1[/tex]. Достатъчно е да покажем, че за всяко [tex]G_d'[/tex] съществува поне един хамилтонов цикъл съдържащ ребрата от [tex]G_1[/tex](без те да имат сечение с ребрата на [tex]G_d'[/tex].
...

[drago]

Две неща:
1.

... Като отделим по едно ребро от всеки връх може да получим два нови графа [tex]G_d[/tex] и [tex]G_1[/tex], така че [tex]G_{d+1}=G_d\cup G_1[/tex]...

Това не е вярно. Мога да ти дам контрапример. Не е задължително в един граф, всеки от върховете, на който има степен поне d+1, d>1, да има matching.

2.

Достатъчно е да покажем, че за всяко [tex]G_d'[/tex] съществува поне един хамилтонов цикъл съдържащ ребрата от [tex]G_1[/tex](без те да имат сечение с ребрата на [tex]G_d'[/tex].
...

Toва не мога да кажа дали е вярно или не, но имам чувство, че е по-трудно от самата задача.

[ptj]

За първото ми покажи контра пример, защото може да говорим за различни неща. Когато нямаля степента на всички върхове с 1-ца очевидно влизам в граф от точка 2.

Колкото до второто, ще помисля малко за реализацията (може би с подходящо подреждане). Достатъчно е да съществува една такава комбинация, не ми трябват всички.

[drago]

G, V(G)={1,2,3,4,5,1',2',3',4',5'}. Ребрата са: E(G)={11', 12', 13', 21', 22', 23', 34', 35', 44', 45', 54', 55' }

Хайде сега махни няколко ребра, така че да намалиш степента на всеки връх с единица.

[ptj]

G, V(G)={1,2,3,4,5,1',2',3',4',5'}. Ребрата са: E(G)={11', 12', 13', 21', 22', 23', 34', 35', 44', 45', 54', 55' }

Хайде сега махни няколко ребра, така че да намалиш степента на всеки връх с единица.

{11';22';;44';55'} и добавям към тях реброто {33'}

В твоя граф 3 и 3' са инцидентни само с 2 върха.

[drago]

Разбирам това, което пишеш:

... Като отделим по едно ребро от всеки връх може да получим два нови графа ...

какво значи да отделиш по едно ребро от всеки връх ?

Виж, не се заяждам. Много добре разбирам какво искаш да извъртиш. Проблемът е, че не става, а и аз не мога да го преправя, че да става.
Не знам решение на тази задача.
Ако искаш да пишеш още нещо, първо го обмисли хубаво и го напиши както трябва!

[ptj]

Прав си , че не е издържано, но писах за да разбереш идеята. Виж поправката ми.

Това за отделянето на ребрата мога за да го кажа и по друг начин:
Oтделям подграф със същите върхове и инцидентност на ребрата най-много [tex]d[/tex]. Оставащите ребра или образуват или ги допълваме до граф [tex]G_1[/tex].

П.П. Даже и за т.3 измислих хитрост, но ще я обяснявам утре.

[drago]

Tова хич не е толкова лесна задача, както изглежда. Накрая открих този проблем в една книга - Laszlo Lovasz, "Combinatorial Problems and Exercises".
Доказателството се опира на няколко последователни твърдения-дадени като задачи в книгата. Ключово е едно НДУ за f-factorization- последното понятие означава следното:
Ако имаме една функция f(v), която на всеки връх на даден граф G съпоставя естествено число.
Пита се съществува ли подграф G_1 на G (който се получава от G като изтрием някои ребра) такъв че [tex]f(v) = deg_{G_1}(v)[/tex] за всеки връх v. т.е. дали може да изтрием част от ребрата на даден граф и да получим друг,с предарително зададена степен за всеки връх.
За двустранни графи(bipartite) в книгата е дадено едно НДУ за съществуване на такова f-factorization, което се прилага за допълнителния граф на този от задачата.

[ptj]

Мисля, че я има издадена на руски или български някъде около 1989-90г.

П.П. Някой ден ще се потрудя по моето доказателство, но не мога да кажа кога точно.