szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 maja 2017, o 03:14 
Użytkownik

Posty: 319
Lokalizacja: Gorzów Wlkp.
Witam

Cytuj:
Mam takie zadanko. Czy istnieje graf, który ma taki ciąg stopni wierzchołków (6, 6, 5, 5, 4, 4, 4, 4), ale nie ma skojarzenia doskonałego?

Znalazłem na razie graf, który ma skojarzenie doskonałe.
Wydaję mi się, że nie ma takiego grafu o takim ciągu stopniu, który by go nie miał, ale nie wiem jak to udowodnić.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 2 maja 2017, o 13:21 
Użytkownik

Posty: 1073
Lokalizacja: Lublin/Warszawa
Z tw. Diraca ten graf ma cykl Hamiltona. Ten cykl ma parzystą długość, więc można wziąść z niego co drugą krawędź i mamy skojarzenie doskonałe. Nie istnieje graf bez skojarzenia doskonałego.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Najkrótszy ciąg cyfr - zagadko/problem  Tetriando  3
 Ustawienie liczb w ciąg  princess691  1
 ciąg rekurencyjny?  rozprzedstud  2
 Ciąg rekurencyjny - zadanie 33  K4mil5  12
 Nieskończony ciąg liczb pierwszych  faramka  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl