graf cykliczny i acykliczny

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
matematykapj
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 4 mar 2019, o 10:53
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 8 razy

graf cykliczny i acykliczny

Post autor: matematykapj »

Witam,

Szukam szukam i nie jestem nadal pewien.

Według tego co wyczytałem graf cykliczny to graf spójny, który posiada wszystkie wierzchołki stopnia drugiego. Czyli np taki graf: \(\displaystyle{ (A,B), (B,C), (C,A)}\).

Czyli jak dodam do tego wierzchołek np: \(\displaystyle{ (C,D)}\) to graf nie jest cykliczny. Ale czy możemy powiedzieć ze ma cykl? Czy cykl graf ma tylko wtedy gdy jest cykliczny? Dodatkowo moj graf po dodaniu \(\displaystyle{ (C,D)}\) jest acykliczny?

Pozdrawiam
Ostatnio zmieniony 20 maja 2019, o 12:42 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

graf cykliczny i acykliczny

Post autor: Mruczek »

Z podanej przez Ciebie definicji grafu cyklicznego wynika, że to po prostu cykl.

Tak, możemy powiedzieć, że po dodaniu \(\displaystyle{ (C, D)}\) ma cykl. Graf nie musi być cykliczny żeby mieć cykl. Po dodaniu \(\displaystyle{ (C, D)}\) nie jest acykliczny, bo zawiera cykl.
ODPOWIEDZ