Wyznacz najmniejsza mozliwie liczbę M, aby prawdziwe było to twierdzenie: W grupie naukowej zlozonej z n fizyków, każdy ma co najmniej M znajomych. Wtedy istnieje taka czworka, w której kazdy zna sie z każdym.
n=2008
M=?
"kwartet" fizyków
-
mol_ksiazkowy
- Użytkownik
- Posty: 11375
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
-
mol_ksiazkowy
- Użytkownik
- Posty: 11375
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
-
rahl
"kwartet" fizyków
kazdy fizyk to wierzcholek, a krawedz to relacja "znajomy". tworzysz sobie dwudzielny graf pelny. widac, ze nie znajdziesz szukanej czworki, bo zadne 2 wierzcholki z tego samego zbioru sie nie znaja, stad dla M=1004 kwartet nie istnieje. dla M=1005 graf jest zawsze spojny, a zarazem przypadek M=1004 pokazuje, ze dodanie jednego stopnia zawsze spowoduje znalezienie kwartetu.