Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

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

Strona 1 z 1

[ Posty: 11 ]

Autor

Wiadomość

Marien Offline

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

Napisane: 3 paź 2016, o 14:24

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

Mruczek Offline

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

Napisane: 3 paź 2016, o 17:20

Posty: 1088
Lokalizacja: Lublin/Warszawa

Czy w tym warunku chodzi o to, że $i \neq j$ ?

Góra

Marien Offline

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

Napisane: 3 paź 2016, o 17:28

Posty: 165
Lokalizacja: Polska

Tak

Góra

Mruczek Offline

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

Napisane: 3 paź 2016, o 17:37

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

Marien Offline

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

Napisane: 3 paź 2016, o 17:54

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

Mruczek Offline

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

Napisane: 3 paź 2016, o 17:55

Posty: 1088
Lokalizacja: Lublin/Warszawa

Tutaj $x = 20$ .
$x^{2}-x = 20 ^{2} - 20 = 380$ wg mnie.

Góra

Marien Offline

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

Napisane: 3 paź 2016, o 18:10

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

Mruczek Offline

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

Napisane: 3 paź 2016, o 18:23

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

Marien Offline

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

Napisane: 3 paź 2016, o 19:11

Posty: 165
Lokalizacja: Polska

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

Góra

Mruczek Offline

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

Napisane: 3 paź 2016, o 19:18

Posty: 1088
Lokalizacja: Lublin/Warszawa

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

Góra

Marien Offline

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

Napisane: 3 paź 2016, o 19:32

Posty: 165
Lokalizacja: Polska

Ok myliłam się

Góra

Poprzedni | Następny

	Strona 1 z 1	[ Posty: 11 ]

Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Zobacz podobne tematy
Tytuł tematu	Autor	Odpowiedzi
[Teoria grafów] dowód, graf dwudzielny, graf planarny	matinf	3
Czy może istnieć graf spełniający takie warunki?	magnes	1
graf hamiltonowski, macierz permutacyjna	bobi85	0
graf, promień dowód	aGabi94	2
dla jakich n istnieje graf n-wierzochołkowy o st.3wierzchołk	bastek91	5

[Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]