szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta Offline
 Tytuł: graf spójny
PostNapisane: 29 mar 2015, o 14:24 
Użytkownik

Posty: 232
Lokalizacja: Kraków
Ile cykli ma graf spójny, w którym |V|=|E| (gdzie |V| -liczba wierzchołków, |E|-liczba krawędzi)?
Czyli żeby spełniony był ten warunek możemy wziąć poszczególne cykle, np. C_{3}, C_{5} itd., tak? Wtedy mamy 1 cykl. Jeżeli weźmiemy jakieś drzewo to możemy dorysować jeszcze jedną krawędź, żeby warunek był spełniony, dobrze myślę?Czy są jeszcze jakieś przypadki że tych cykli będzie więcej?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
 Tytuł: graf spójny
PostNapisane: 29 mar 2015, o 17:18 
Użytkownik

Posty: 1390
Lokalizacja: Poznań
Zauważ, że minimalny (co do liczby krawędzi) graf spójny ma e=v-1 krawędzi gdzie e[/tex/ - liczba krawędzi, [tex]v - liczba wierzchołków.. Taki graf nie ma żadnego cyklu.. W związku z tym odpowiedź nasuwa się sama.. Jeśli dorzucisz kolejną krawędź utworzysz dokładnie jeden cykl.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Graf spójny  niunian  0
 Kolorowanie wierzchołków (graf z petlami)  sputnik1957  3
 Graf k-krytyczny  nieOna3  0
 Czy graf dwudzielny musi być spójny?  dragonn  2
 Graf półhamiltonowski  uczen23  7
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl