GRY-Online.pl --> Archiwum Forum

teoria grafów - zadanie z grupa sześciu osob

25.04.2007
11:54
[1]

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?

25.04.2007
11:58
[2]

yasiu [ Senator ]

dołączam się do pytania - bo twierdzenie wydaje sie nieprawdziwe :)

25.04.2007
11:59
[3]

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.

25.04.2007
12:01
smile
[4]

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

25.04.2007
12:43
[5]

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? ;)

25.04.2007
22:33
[6]

Didier z Rivii [ life 4 sound ]

ksiazka niestety nie pomogla wiec mzoe teraz ktos z was sprobuje? ;)

25.04.2007
23:06
[7]

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...

25.04.2007
23:24
[8]

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 :/

25.04.2007
23:35
[9]

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?

25.04.2007
23:37
[10]

Didier z Rivii [ life 4 sound ]

Mazzop --> wlasnie znalazlem to co napisales na jakiejs anglojezycznej stronie :)
niemniej wielkie dzieki :) juz dalej sobie dam rade :)

© 2000-2022 GRY-OnLine S.A.