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: 1086
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 Fibonacciego - zadanie 25  cis123  1
 Nieskończony ciąg liczb pierwszych  faramka  3
 Wyznaczyć ciąg an , rekurencja liniowa niejednorodna  marcin1509  3
 Znajdź funkcję tworzącą / ciąg na podstawie wzoru  jatospale  1
 Układanie kolorowych kul w ciąg  Majorkan  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl