Една лесна задачка с графи

[luboslav_p]

Даден е граф G с n върха. Да се докаже, че част от ребрата на G могат да се премахнат и да получим двуделен граф G₁(двуделен граф е граф, за който множеството върхове може да се разбие на 2 множества, за всяко от които никои два върха от това множество не са свързани с ребро) , за който за всеки връх v от G да е изпълнено d(v,G₁)≥1/2d(v,G), където с d(v,G) означаваме степента на върха v в графа G.
Горното условие може да се зададе и малко по-различно: имаме n ученика, като някои се познават. Да се докаже, че можем да ги разделим в две стаи така, че всеки ученик познава поне толкова ученика в другата стая, колкото познава в своята.

[Реклама]

[zhivko_sh]

Ясно е, че има краен брой разбивания на върховете на 2 множества. Затова можем да изберем това от тях, за което ребрата между върхове в двете множества е максимален (т.е. графът се разбива на множества A и B , като ребрата между върхове от А и върхове от B е максимален). Сега изтриваме всички вътрешни ребра в A и всички вътрешни в B , т.е. да останат само тези между A и B. Такова разделяне върши работа, защото ако допуснем, че за някой връх C например в A степента му в новия граф е < 1/2 от степента му в стария, то значи сме изтрили повече ребра вътре в A с връх C отколкото са останали между A и B(през цялото време говорим само за ребрата с един от върховете в C). Но тогава можем да преместим C от A в B и получаваме ново разбиване с повече ребра между A и B, което е противоречие.

[luboslav_p]

Това е най-краткото и ясно решение. Ето още една хубава задача.
Под разстояние между два върха ще разбираме дължината на най-краткият път, който ги свързва. Диаметър на един граф ще означаваме с максималното разстояние измежду разстоянията за всички двойки върхове. С G₁ ще означаваме графът допълнение на G т.е. графът получен от G чрез премахване на всички ребра от G и добавяне на всички ребра, липсващи в G. Да се докаже, че ако диаметърът на G е по-голям от три, то диаметърът на G₁ е по-малък от три.

[zhivko_sh]

Ясно е, че ако в първоначалния граф два върха не са свързани с ребро, то в допълнението му съответните върхове са свързани и значи разстоянието между тях е 1, което ни устройва. Значи е смислено да гледаме само двойките върхове в началния граф, които са свързани с ребро. Да разгледаме такива 2 върха А и B, които са свързани с ребро и да допуснем, че всеки друг връх е свързан с поне един от върховете А и B. Тогава от всеки връх до всеки връх може да се стигне най-много през 3 ребра(в най-лошия случай 1 ребро за да се стигне от първия връх до A или B, после още 1 от A до B, и трето да се стигне до другия искан връх) - надявам се да е ясно, щото ме мързи тука да пиша случаи, но мисля, че все пак е очевидно за какво става дума. Това обаче е противоречие с условието. Значи за всяка двойка свързани с ребро върха има трети връх, който не е свързан нито е един от тях и значи в допълнението той е свързан и с 2та, т.е. разстоянието между тях в допълнението е не повече от 2(даже е точно 2, тъй като самите върхове не са свързани с ребро, т.е. не може да е 1). В резюме: ако два върха в началото са свързани с ребро, то в допълнението разстоянието между тях е 2, а ако не са били свързани с ребро, то в допълнението разстоянието е 1. Ясно е, че това е краят на задачата.