szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 maja 2017, o 02: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 12:21 
Użytkownik

Posty: 1088
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 
 ciąg - zadanie 4  Arvit  3
 Liczby ustawione w ciąg  Czingisham  2
 Ciąg liczbowy - wyznaczenie jawnej postaci - zadanie 2  lukasz_xyz  1
 zd ciag z pierwiastkami  notokey  0
 Ciąg binarny  brasco  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl