Графи 2

[LazyWorker]

Даден е регулярен непълен граф G с n върха и степен d, където n е нечетно число. Каква е максималната мощност на клика в G?
Може ли някой да ми разясни по-подробно как се разсъждава при такъв тип задачи?

[drago]

При такива екстремални задачи за графи би следвало първо да се направи някаква оценка примерно в случая колко най-много може да е размера на макс. клика и после да се посочи пример, че такава съществува. Обикновено първата част е по-трудна. В конкр. сл. обаче това не е проблем. Не може да има клика с [tex]d+1[/tex] върха, тъй като тогава графа ще се състои само от тези върхове и би бил пълен. Значи макс. клика има размер [tex]\leq d[/tex]. Остава да се посочи пример. Това, че [tex]n[/tex] е нечетно мъничко усложнява нещата, тъй като иначе може да посочим съвсем лесен пример: вземаме две клики [tex]A_1,\ldots, A_d[/tex] и [tex]B_1.\ldots, B_d[/tex] и свързваме [tex]A_i[/tex] с [tex]B_i\,,\, i=1,2,\dots, d[/tex]. Това обаче ни е забранено, затова трябва да усложним примера мъничко...

[ptj]

Имам въпрос към 2-рата част - не трябва ли да се докаже тя за произволен регулярен граф изпълняващ условието на задачата, а не само за някои частни случаи?

Случая когато [tex]d[/tex] е четно не гарантира ли съществуването на хамилтонов цикъл в графа? Защото, ако е вярно, посредством премахване на ребрата му можем да намалим степента на графа с 2, а използвайки обратната идея с индукция да докажем 2-рата част...

[drago]

Щом се пита каква е макс. клика, значи търсим да посичм граф който я реализира. Както, ако те питат каква е макс. стойност на функцията не може да очакваш да доказваш, че всички стойности трябва да са такива.
Да не говорим, че има пример на регулярен граф, който не съдържа триъгълници(така че макс. клика в сл. е 2), например двуделен регулярен граф.
Относно Хамилтонов цикъл. В случая, когато d<n/2 няма голям шанс. Има разни класически теореми, виж в нета.
А... , когато n е нечетно d задължително трябва да е четно. Абе, стана голям буламач