Finał Konkursu MiNI (Politechnika Warszawska 2018)

Kangur, Alfik, Mistrzostwa w Grach Logicznych, Sejmik, Konkurs PW... Słowem - konkursy ogólnopolskie, ale nie OM.
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

Re: Finał Konkursu MiNI (Politechnika Warszawska 2018)

Post autor: Mruczek »

Fajne te grafy.
3:    
3 inaczej:    
3 jeszcze inaczej, najkrócej:    
Poza tym:
Dla \(\displaystyle{ n}\) parzystych zawsze \(\displaystyle{ 6}\) klik wielkości \(\displaystyle{ n}\) wystarcza do pokrycia tego grafu: bierzemy dwie rozłączne kliki \(\displaystyle{ A}\) i \(\displaystyle{ B}\) wielkości \(\displaystyle{ n}\) (jak powyżej) i dzielimy te kliki na połowy. Potem parujemy te połowy biorąc jedną połowę z \(\displaystyle{ A}\) i jedną z \(\displaystyle{ B}\), takich par jest \(\displaystyle{ 4}\), dla każdej z tych par dajemy klikę - te \(\displaystyle{ 4}\) kliki pokrywają pełny graf dwudzielny o zbiorach \(\displaystyle{ A}\) i \(\displaystyle{ B}\). Wszystkie pozostałe krawędzie znajdują się wewnątrz klik \(\displaystyle{ A}\) i \(\displaystyle{ B}\) i są już pokryte.
Awatar użytkownika
Sylwek
Użytkownik
Użytkownik
Posty: 2716
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 160 razy
Pomógł: 657 razy

Re: Finał Konkursu MiNI (Politechnika Warszawska 2018)

Post autor: Sylwek »

1:    
ODPOWIEDZ