szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 26 paź 2015, o 22:11 
Użytkownik

Posty: 102
Lokalizacja: Polska
Udowodnij że dowolna grupa może być podzielona na dwie części tak, że co najmniej
połowa znajomych danej osoby jest w grupie, do której ta osoba nie należy.

Nie wiem jak się do tego zabrać, proszę o jakieś podpowiedzi.

-- 29 paź 2015, o 20:23 --

W końcu sam doszedłem do rozwiązania.
Na początku dzielimy znajomych na dwie losowe grupy.
Następnie bierzemy każą osobę której co najmniej połowa znajomych
nie jest w grupie do której ona nie należy. Przerzucamy tą osobę osobę do
drugiej grupy. Następnie jeżeli nie ma takiej osoby, to wtedy zadanie jest rozwiązane.
Natomiast jeżeli jest taka osoba to powtarzamy poprzedni schemat działania.
Z każdym przerzuceniem zwiększa się liczba przecięć(jeżeli narysujemy graf i dwie grupy oddzielimy linią).
Liczba krawędzi jest skończona więc liczba przerzuceń też jest skończona,
więc zawsze dojdziemy do sytuacji że nie możemy już nikogo przerzucić. cnd
Góra
Mężczyzna Offline
PostNapisane: 3 wrz 2016, o 16:48 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Tutaj jest rozwiązanie wzorcowe: http://archom.ptm.org.pl/?q=node/664.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podział 38 osobowej klasy na 2 grupy  Krys  4
 Matematyka dyskretna - teoria grafów  aleheca  7
 Znajdź ciąg posiadający co najmniej 1 element z każdej grupy  Cybran  4
 Teoria grafów, problem ze znalezieniem ilości klik  Kulfon  1
 Liczba grafów o polu 9-elementowym  Oxford  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl