Ile krawędzi może mieć maksymalnie graf dwudzielny

Marien · Post autor: **Marien** » 3 paź 2016, o 15:24

Mam problem z następującym zadaniem: Ile krawędzi może mieć maksymalnie graf dwudzielny \(\displaystyle{ G(U,V,E)}\), gdzie \(\displaystyle{ \left| U\right| =\left| V\right|=20}\) i nie istnieją w nim takie krawędzie, że \(\displaystyle{ (u _{i},v _{j}) \wedge (u _{j},v _{j})}\).

Mruczek · Post autor: **Mruczek** » 3 paź 2016, o 18:20

Czy w tym warunku chodzi o to, że \(\displaystyle{ i \neq j}\)?

Marien · Post autor: **Marien** » 3 paź 2016, o 18:28

Mruczek · Post autor: **Mruczek** » 3 paź 2016, o 18:37

Ok, graf dwudzielny bez tego warunku, który zawiera po \(\displaystyle{ x}\) wierzchołków w każdym zbiorze, może mieć maksymalnie \(\displaystyle{ 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 \(\displaystyle{ j}\), albo krawędzie łączące dowolny inny wierzchołek z \(\displaystyle{ U}\) niż \(\displaystyle{ j}\) z wierzchołkiem \(\displaystyle{ j}\) w \(\displaystyle{ 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 \(\displaystyle{ x^{2} - x}\) krawędzi, bo krawędzi łączących przeciwległe wierzchołki jest \(\displaystyle{ 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 \(\displaystyle{ j}\), zawsze dodaje jedną krawędź, ale kosztuje nas usunięcie innych \(\displaystyle{ x - 1}\) krawędzi o końcu w \(\displaystyle{ V}\) w \(\displaystyle{ j}\) i początku gdzie indziej, co się nie opłaca jeżeli zbiory mają przynajmniej po \(\displaystyle{ 3}\) wierzchołki (czyli gdy \(\displaystyle{ x \ge 3}\)). Dla mniejszych grafów można sprawdzić na palcach.

Marien · Post autor: **Marien** » 3 paź 2016, o 18:54

Czyli dla grafu \(\displaystyle{ K _{20,20}}\) graf może mieć maksymalnie 400 krawędzi. A z tym dodatkowym warunkiem nie bardzo rozumiem ile będzie krawędzi.

Mruczek · Post autor: **Mruczek** » 3 paź 2016, o 18:55

Tutaj \(\displaystyle{ x = 20}\).
\(\displaystyle{ x^{2}-x = 20 ^{2} - 20 = 380}\) wg mnie.

Marien · Post autor: **Marien** » 3 paź 2016, o 19:10

Dziękuję, a jeszcze mam pytanie ile będzie krawędzi jeśli zmienimy warunek na następujący:
jeśli istnieją krawędzie \(\displaystyle{ (u_{i} ,v _{i} )}\) , \(\displaystyle{ (u_{j} ,v _{j} )}\) to nie mogą istnieć krawędzie \(\displaystyle{ (u_{i} ,v _{j} )}\) , \(\displaystyle{ (u_{j} ,v _{i} )}\) ?

Mruczek · Post autor: **Mruczek** » 3 paź 2016, o 19:23

Moim zdaniem \(\displaystyle{ 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 \(\displaystyle{ ( u_{j} , v _{j} )}\). Po dodaniu \(\displaystyle{ k}\)-tej takiej krawędzi (gdzie \(\displaystyle{ 1 \le k \le x - 1}\)) musimy usunąć (albo inaczej: ustawić jako zabronione, które nie mogą występować) \(\displaystyle{ 2k}\) poprzecznych krawędzi aby warunek dalej zachodził (bo usuwamy wszystkie krawędzie postaci \(\displaystyle{ (u _{i}, v_{j} )}\), gdzie \(\displaystyle{ i}\) to jeden z indeksów wierzchołków zbioru \(\displaystyle{ U}\) wcześniej dodanych krawędzi, oraz krawędzie postaci \(\displaystyle{ (u _{j}, v_{i})}\) analogicznie).

Marien · Post autor: **Marien** » 3 paź 2016, o 20:11

A nie będzie to czasem mniej niż poprzednio?

Mruczek · Post autor: **Mruczek** » 3 paź 2016, o 20:18

Dlaczego miałoby być mniej? Uzasadnij dlaczego uważasz, że mój przykład jest niepoprawny.

Marien · Post autor: **Marien** » 3 paź 2016, o 20:32

Ok myliłam się