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

Posty: 318
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 2019
Góra
Mężczyzna Offline
PostNapisane: 2 maja 2017, o 12:21 
Użytkownik

Posty: 1093
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 fibonacciego - zadanie 13  heux  2
 ciag rekurencyjny a delta 0  anios0025  1
 Układanie liczb w ciąg  Natasha  2
 Zasada szufladkowa, ciąg kolejnych dni  iridescent  2
 ciąg Fibonacciego - zadanie 17  masabmw  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl