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ć.
Góra
Mężczyzna Offline
PostNapisane: 2 maja 2017, o 13:21 
Użytkownik

Posty: 1087
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 
 Ilość ustawień w ciąg  alla2012  3
 Dowód, ciąg Fibonacciego  Magda0601  3
 Niemalejący ciąg cyfr liczby  patry93  7
 ciąg o komponentach zero i jeden  bebece  1
 Ciąg zadany rekurencyjnie..  luckaminski  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl