Mam problem z poniższym zadaniem:
Jeżeli graf posiada 12 trójkątów, jaka jest największa ilość 4-wierzchołkowych klik które może posiadać?
W jaki sposób do tego pojdeść?
Teoria grafów, problem ze znalezieniem ilości klik
- Errichto
- Użytkownik
- Posty: 1629
- Rejestracja: 17 mar 2011, o 18:55
- Płeć: Mężczyzna
- Lokalizacja: Suwałki
- Podziękował: 28 razy
- Pomógł: 272 razy
Teoria grafów, problem ze znalezieniem ilości klik
Zapewne trzeba tu się mocno rozpisać, eleganckiego rozwiązania nie ma. Musisz rozpatrzeć przypadek dwóch/trzech rozłącznych 4-wierzchołkowych klik (ile wtedy mamy trójkątów?), co gdy dwa 4-wierzchołkowce mają część wspólną, w szczególności gdy 3 wierzchołki są wspólne. A jak wtedy dorzucimy jeszcze jedną krawędź to mamy 5-klikę, która da \(\displaystyle{ {5 \choose 4}}\) żądanych 4-wierzchołkowych klik.
Dużo pisania i przypadków.
Dużo pisania i przypadków.