--> Archiwum Forum
Didier z Rivii [ life 4 sound ]
teoria grafów - zadanie z grupa sześciu osob
zadanko brzmi
Wykaż, że w grupie sześciu osób zawsze znajdą się trzy, które albo znają się nawzajem, albo żadna z nich nie zna dwóch pozostałych.
czy ktos moze ma pomysl jak to rozwiazac przy pomocy grafów?
yasiu [ Senator ]
dołączam się do pytania - bo twierdzenie wydaje sie nieprawdziwe :)
Scatterhead [ łapaj dzień ]
masz 6 wierzchołków, załóżmy, że jeżeli połączymy dwa wierzchołki krawędzią, to będzie to oznaczało, że dane 2 osoby się znaja.
teraz trzeba udowodnić tezę. spróbuj tak poustawiać krawędzie, żeby dopasować je do treści zadania. gdy już dojdziesz do jakiegoś schematu, dlaczego tak się dzieje, przydałoby się to udowodnić, podkładając to pod jakieś twierdzenie, zapewne z ostatniego wykładu.
edit: z drugiej strony może być również jak pisze yasiu -> wtedy też zachowanie grafu w takim przypadku na pewno pasuje do jakiegoś twierdzenia, którego sie ostatnio uczyliście.
ja już niestety nie pamiętam za bardzo twierdzeń o grafach.
Didier z Rivii [ life 4 sound ]
Scatterhead --> wlasnie problem w tym ze material przedstawiany na wykladach nie pokrywa sie z tym cwiczeniowym niestety i dlatego ugrzazlem na tym zadanku
Didier z Rivii [ life 4 sound ]
moze ktyos jednak rozwiazal takie zdanie? zamowilem sobie do czytelni za godzinek ksiazke na ten temat ale moze wczesniej uda sie cos uzyskac? ;)
Didier z Rivii [ life 4 sound ]
ksiazka niestety nie pomogla wiec mzoe teraz ktos z was sprobuje? ;)
Mazzop [ ]
można skorzystać z zasady szufladkowej - dana osoba musi znać się albo nie znać się z co najmniej 3 osobami, na tej czwórce osób rozważ możliwe relacje...
Didier z Rivii [ life 4 sound ]
Mazzop --> sama zasade rozwiazania rozumiem ale nie wiem za bardzo jak to mozna udowodnic korzystajac z twierdzen teorii grafow :/
Mazzop [ ]
Oj tam, od razu jakieś twierdzenia, kredki w łapy i kolorować ;D
Relację znania się na czerwono, a relację nieznania się na niebiesko, i w grafie pełnym K6 zawsze będziesz miał trójkąt jednego koloru.
Jak już koniecznie coś pod twierdzenia, przerabiałeś liczby Ramseya?
Didier z Rivii [ life 4 sound ]
Mazzop --> wlasnie znalazlem to co napisales na jakiejs anglojezycznej stronie :)
niemniej wielkie dzieki :) juz dalej sobie dam rade :)