cykl
: 03 cze 2018, 16:26
niech G=(V,E) bedzie grafem spójnym,|V|=60,|E|=59.Czy w G może istnieć cykl?Odpowiedz uzasadnij.
ktos może wie jak to rozwiązać?
ktos może wie jak to rozwiązać?
V - to liczba wierzchołków a E to liczba krawędzi? Mogę tylko naprowadzić i nie daje ręki że to będzie dobrze, ale moim zdaniem nie będzie cyklu gdyż 59 krawędzi to minimalna liczba krawędzi aby ten graf był spójny tudzież jeśli pójdziemy od jednego wierzchołka to nie wrócimy się do niego bo musieliśmy przejść - powtórzyć krok - chodzi mi o krawedz i wierzchołek.
Dlaczego sądzę że jest to minimalna liczba krawędzi, jeśli mamy 3 wierzchołki i chcemy aby graf był spójny wystarczy 2 krawedzie, gdy 4 wierzchołki tylko 3 krawedzi doszłem do wniosku że n-1 krawędzi jest wystarczająca liczba aby graf był spójny (n - liczba wierzchołków )
Proszę o poprawę jeśli się mylę..