szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 24 mar 2017, o 21:02 
Użytkownik

Posty: 10
Lokalizacja: Kraków
zakladamy ze G jest grafem dwudzielnym G=(X,Y,E) oraz 1  \le  |X|  \le  |Y|

wykaz ze jesli G jest hamiltonowski to ma pelne skojarzenie
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 25 mar 2017, o 14:29 
Użytkownik

Posty: 1074
Lokalizacja: Lublin/Warszawa
No to jak jest hamiltonowski to znaczy, że ma cykl Hamiltona (cykl przechodzący przez każdy wierzchołek grafu). Graf jest dwudzielny, więc każdy jego cykl ma parzystą długość. Bierzemy co drugą krawędź z tego cyklu Hamiltona i dostajemy pełne skojarzenie (widać, że każdy wierzchołek jest w tym skojarzeniu).
Góra
Mężczyzna Offline
PostNapisane: 25 mar 2017, o 23:58 
Użytkownik

Posty: 10
Lokalizacja: Kraków
hmm wiem wiem, ale jak to zapisac tak poprawnie ? zeby na kolokwium bylo tak przejrzyscie ? bo ja tak samo uwazam , tylko kwestia zapisu ? :P
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Graf - najmniejsza i największa liczba spójności  Matm  2
 Graf i zbiór  Polek  3
 Graf planarny bez trójkątów  lidka95  1
 Graf planarny - maksymalna ilość dorysowanych krawędzi  brylcio16  1
 Czy graf jest dwudzielny?  blade  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl