szukanie zaawansowane
 [ Posty: 11 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 3 paź 2016, o 15:24 
Użytkownik

Posty: 165
Lokalizacja: Polska
Mam problem z następującym zadaniem: Ile krawędzi może mieć maksymalnie graf dwudzielny G(U,V,E), gdzie \left| U\right| =\left| V\right|=20 i nie istnieją w nim takie krawędzie, że (u _{i},v _{j})  \wedge (u _{j},v _{j}).
Góra
Mężczyzna Offline
PostNapisane: 3 paź 2016, o 18:20 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Czy w tym warunku chodzi o to, że i \neq j?
Góra
Kobieta Offline
PostNapisane: 3 paź 2016, o 18:28 
Użytkownik

Posty: 165
Lokalizacja: Polska
Tak
Góra
Mężczyzna Offline
PostNapisane: 3 paź 2016, o 18:37 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Ok, graf dwudzielny bez tego warunku, który zawiera po x wierzchołków w każdym zbiorze, może mieć maksymalnie x^{2} krawędzi.
Co mówi ten dodatkowy warunek?
Wierzchołki o takim samym indeksie rysujemy naprzeciwko siebie. Wtedy w tym grafie może być albo krawędź łącząca wierzchołki leżące naprzeciwko siebie o indeksach j, albo krawędzie łączące dowolny inny wierzchołek z U niż j z wierzchołkiem j w V.
Weźmy graf w którym nie ma żadnych krawędzi łączących wierzchołki leżące naprzeciwko siebie, a są wszystkie pozostałe. Wtedy ten graf ma x^{2} - x krawędzi, bo krawędzi łączących przeciwległe wierzchołki jest x. Okazuje się, że ten graf ma maksymalnie wiele krawędzi. Dołożenie do tego grafu jednej krawędzi łączącej przeciwległe wierzchołki j, zawsze dodaje jedną krawędź, ale kosztuje nas usunięcie innych x - 1 krawędzi o końcu w V w j i początku gdzie indziej, co się nie opłaca jeżeli zbiory mają przynajmniej po 3 wierzchołki (czyli gdy x  \ge 3). Dla mniejszych grafów można sprawdzić na palcach.
Góra
Kobieta Offline
PostNapisane: 3 paź 2016, o 18:54 
Użytkownik

Posty: 165
Lokalizacja: Polska
Czyli dla grafu K _{20,20} graf może mieć maksymalnie 400 krawędzi. A z tym dodatkowym warunkiem nie bardzo rozumiem ile będzie krawędzi.
Góra
Mężczyzna Offline
PostNapisane: 3 paź 2016, o 18:55 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Tutaj x = 20.
x^{2}-x =  20 ^{2} - 20 = 380 wg mnie.
Góra
Kobieta Offline
PostNapisane: 3 paź 2016, o 19:10 
Użytkownik

Posty: 165
Lokalizacja: Polska
Dziękuję, a jeszcze mam pytanie ile będzie krawędzi jeśli zmienimy warunek na następujący:
jeśli istnieją krawędzie (u_{i} ,v _{i} ) , (u_{j} ,v _{j} ) to nie mogą istnieć krawędzie (u_{i} ,v _{j} ) , (u_{j} ,v _{i} ) ?
Góra
Mężczyzna Offline
PostNapisane: 3 paź 2016, o 19:23 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Moim zdaniem 381, czyli jedną więcej niż poprzednio. Do grafu z poprzedniego zadania (czyli pełnego dwudzielnego bez krawędzi łączących przeciwległe wierzchołki) dodajmy jedną krawędź łączącą przeciwległe wierzchołki. Ten graf spełnia nowy warunek. Do tego grafu będziemy teraz dodawali kolejne takie krawędzie ( u_{j} , v _{j} ). Po dodaniu k-tej takiej krawędzi (gdzie 1 \le k   \le x - 1) musimy usunąć (albo inaczej: ustawić jako zabronione, które nie mogą występować) 2k poprzecznych krawędzi aby warunek dalej zachodził (bo usuwamy wszystkie krawędzie postaci (u _{i}, v_{j}  ), gdzie i to jeden z indeksów wierzchołków zbioru U wcześniej dodanych krawędzi, oraz krawędzie postaci (u _{j}, v_{i}) analogicznie).
Góra
Kobieta Offline
PostNapisane: 3 paź 2016, o 20:11 
Użytkownik

Posty: 165
Lokalizacja: Polska
A nie będzie to czasem mniej niż poprzednio?
Góra
Mężczyzna Offline
PostNapisane: 3 paź 2016, o 20:18 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Dlaczego miałoby być mniej? Uzasadnij dlaczego uważasz, że mój przykład jest niepoprawny.
Góra
Kobieta Offline
PostNapisane: 3 paź 2016, o 20:32 
Użytkownik

Posty: 165
Lokalizacja: Polska
Ok myliłam się
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 11 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Graf hamiltonowski - zadanie 3  Fray  0
 graf planarny -dowód  manduka  4
 Graf, cykl Eulera  Gera  2
 pytanie o graf, czy jest pełny  Popiolkas  3
 Na ile sposobów Magda może się ubrać.  see-you  4
cron
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl