Пълни графи и разделяне на отбори (пълни и многоделни графи)
Нека да разгледаме граф с 4 точки и 6-те звена, които ги свързват:
Граф при който са свързани всеки две от точките се нарича клика (пълен граф) т.е. в случая - 4-клика.
За да се направи клика с определена големина в СтруниМа, може да се използва плъзгащата лента в лявата част на темата за графи.
Колко е броят на ребрата в една n-клика?
За да намерим броят на ребрата (свързванията) в една клика можем да умножим броят на точките n по броят на точките, с които е свързана всяка от тях (n-1) и да разделим на 2 (в противен случай ще преброим всяка отсечка по два пъти). Например 9-кликата има (9.8):2=36 ребра:
Друг начин по който можем да ги преброим е да съберем 8-те оцветени ребра с оставащите 7 от връх номер 2. След това с оставащите 6 от връх номер 3 и т.н. Така визуално получаваме, че 8+7+6+5+4+3+2+1=(8.7)/2=36, тъй като преброяваме един и същи брой ребра по 2 различни начина.
Обобщавайки това за n-клика получаваме така известната формула за Гаусова сума - n+(n-1)+(n-2)+...+3+2+1=(n.(n-1)):2.
За да се направи граф, който няма нито едно свързване (празен граф или антиклика) може да се изключи чавката до плъзгащата лента:
Нека да разделим 6-те точки на два отбора от по 3 точки. Никои две точки от един отбор не са свързани и всеки две точки от различни отбори са свързани помежду си. Така получаваме двуделен граф K3,3:
За да увеличим броят на отборите, можем да използваме втората плъзгаща лента, а с първата да увеличаваме броят на точките. Така например, ако втората лента е на първа позиция и увеличим броят на точките до 9 получаваме двуделен граф K4,5(числата отговарят на броят на точките в отборите):
Можете ли да откриете триъгълник с върхове 3 от дадените точки, които са свързани с ребра помежду си в следния граф K5,6:
Ако има такъв триъгълник, то два от върховете му ще попадат в един отбор - но никои две точки в един отбор не са свързани помежду си. Тогава тук няма триъгълник. Това остава вярно за всеки двуделен граф.
Разсъждавайки аналогично за 3-делен граф (т.е. точките са разделени на 3 отбора) К3,3,3 - в него не може да се намери 4-клика:
Ако свържем само две от дадените точки (които не са свързани до момента), то ще получим 4-клика:
Известно свойство а тези графи е, че когато броят на точките в отборите е възможно най-близък помежду си, то полученият многоделен граф ни дава най-големия брой свързвания така, че никъде да не можем да намерим клика с големина с 1 повече от броят на отборите (теорема на Туран). Така например граф K5,6 ни дава най-големият брой свързвания (5.6=30) между 11 точки така, че никъде да няма триъгълник. Триделния граф K3,3,3 ни дава най-големия брой свързвания ((9.8):2 - 3.3 = 27) измежду 9 точки така, че да не можем да намерим 4-клика.
Можете да изследвате в обучителната тема "Скрити подграфи" в Графи и вериги:
Copyright: Mladen Valkov