Witam forumowiczów!
Chciałbym prosić o pomoc w rozwiazaniu i wytłumaczeniu mi kilku zadań, które szczególnie radują moje serce.
1)Wiemy, że zachodzi nastepujące twierdzenie :
"kazdy graf nieskierowany o szesciu wierzchołkach i przynajmniej dziesięciu krawędziach zawiera klikę trzyelementowa"
Korzystając z tego faktu udowodnij, że kazdy graf nieskierowany, który ma osiem wierzchołków i nie mniej niz \(\displaystyle{ 17}\) krawedzi, zawiera klikę trzyelementową.
myslę, że trzeba tutaj tak napisać graf o ośmiu wierzchołkach aby go uprościć do postaci twierdzenia, z tym, że nie mam pojecia jak sie do tego zabrać.
2) Udowodnij, że \(\displaystyle{ R(5,3) = 14}\) - brak koncepcji
3) W przestrzeni wybrano \(\displaystyle{ 17}\) punktów , w położeniu ogólnym i każdą parę tych punktów połączono odcinkiem jednego z trzech kolorów - czerwonym, zielonym albo niebieskim. UDOWODNIJ, że na pewno powstał w ten sposób jednokolorowy trójkąt.
4) Rozwiązując zadanie o Studentach Pierwszego Roku milcząco zakładalismy, że nikt nie zna sam siebie. Czy rozwiązanie zostanie poprawne, jeżeli nie będziemy robić takiego założenia?
Trudne(?) grafy
Trudne(?) grafy
Ostatnio zmieniony 20 wrz 2012, o 00:16 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
-
mol_ksiazkowy
- Użytkownik
- Posty: 11373
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Trudne(?) grafy
wsk Jeden punkt jest ustalony , z polaczen tego punktu z pozostałymi 16 punktami musza istniec szesc w tym samym kolorze, itd3) W przestrzeni wybrano 17 punktów , w położeniu ogólnym i każdą parę tych punktów połączono odcinkiem jednego z trzech kolorów - czerwonym, zielonym albo niebieskim. UDOWODNIJ, że na pewno powstał w ten sposób jednokolorowy trójkąt.
Trudne(?) grafy
1. No rysowanie raczej nic nie da, bo jeśli nie pokażesz na podstawie tego rysunku ogólnej metody upraszczania, to tak właściwie pokażesz tylko jakiś 1 przypadek, a masz to zrobić dla wszystkich przypadków.
Powinieneś raczej pokazać, że z tych \(\displaystyle{ 8}\) wierzchołków zawsze możesz wybrać \(\displaystyle{ 6}\) tak, żeby między nimi było min. \(\displaystyle{ 10}\) krawędzi i wtedy skorzystać z założenia. Możesz sobie np. uporządkować wierzchołki malejąco według ich stopnia i pokazać, że suma stopni pierwszych \(\displaystyle{ 6}\) to zawsze co najmniej 20 (i skorzystać z prostego faktu \(\displaystyle{ \sum_{v \in V}deg(v) = 2\left| E\right|}\), który mam nadzieje, ze jest Ci znany).
Teraz zauważyłem jeszcze, że to min. 20 to musi być oczywiście po odrzuceniu tych krawędzi łączących się z pozostałymi \(\displaystyle{ 2}\) wierzchołkami, ale chyba i tak da radę to zrobić tym sposobem.
Powinieneś raczej pokazać, że z tych \(\displaystyle{ 8}\) wierzchołków zawsze możesz wybrać \(\displaystyle{ 6}\) tak, żeby między nimi było min. \(\displaystyle{ 10}\) krawędzi i wtedy skorzystać z założenia. Możesz sobie np. uporządkować wierzchołki malejąco według ich stopnia i pokazać, że suma stopni pierwszych \(\displaystyle{ 6}\) to zawsze co najmniej 20 (i skorzystać z prostego faktu \(\displaystyle{ \sum_{v \in V}deg(v) = 2\left| E\right|}\), który mam nadzieje, ze jest Ci znany).
Teraz zauważyłem jeszcze, że to min. 20 to musi być oczywiście po odrzuceniu tych krawędzi łączących się z pozostałymi \(\displaystyle{ 2}\) wierzchołkami, ale chyba i tak da radę to zrobić tym sposobem.