Ile krawędzi może mieć maksymalnie graf dwudzielny
-
- Użytkownik
- Posty: 168
- Rejestracja: 25 mar 2011, o 19:09
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 41 razy
- Pomógł: 1 raz
Ile krawędzi może mieć maksymalnie graf dwudzielny
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})}\).
Ostatnio zmieniony 3 paź 2016, o 18:34 przez Marien, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Ile krawędzi może mieć maksymalnie graf dwudzielny
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.
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.
Ostatnio zmieniony 3 paź 2016, o 18:58 przez Mruczek, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 168
- Rejestracja: 25 mar 2011, o 19:09
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 41 razy
- Pomógł: 1 raz
Ile krawędzi może mieć maksymalnie graf dwudzielny
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.
-
- Użytkownik
- Posty: 168
- Rejestracja: 25 mar 2011, o 19:09
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 41 razy
- Pomógł: 1 raz
Ile krawędzi może mieć maksymalnie graf dwudzielny
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} )}\) ?
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} )}\) ?
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Ile krawędzi może mieć maksymalnie graf dwudzielny
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).