Podać przykład grafu 3-spójnego takiego, że każde dwa najdłuższe cykle mają dokładnie 3 wierzchołki wspólne.
Jedyne co mi przychodzi do głowy to trójkąt. Co sądzicie o takim rozwiązaniu?
przykład grafu 3-spójnego
przykład grafu 3-spójnego
Mam dwie wątpliwości odnośnie tego rozwiązania:
1) czy punkt jest grafem spójnym?
2) czy cykl \(\displaystyle{ v_1,v_2,v_3,v_1}\) jest różny od cyklu \(\displaystyle{ v_2, v_3,v_1,v_2}\)? Czyli inaczej mówiąc - czy trójkąt ma tylko jeden cykl czy jest ich więcej?
1) czy punkt jest grafem spójnym?
2) czy cykl \(\displaystyle{ v_1,v_2,v_3,v_1}\) jest różny od cyklu \(\displaystyle{ v_2, v_3,v_1,v_2}\)? Czyli inaczej mówiąc - czy trójkąt ma tylko jeden cykl czy jest ich więcej?
-
- Użytkownik
- Posty: 1358
- Rejestracja: 4 lip 2009, o 13:27
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 222 razy
przykład grafu 3-spójnego
1) jest, z definicji: dla każdych dwóch wierzchołków istnieje ścieżka je łącząca -- w tym przypadku po prostu nie ma dwóch wierzchołków różnych, więc kwantyfikator przebiega zbiór zawierający tylko parę składającą się z dwóch tych samych elementów
2) wiesz co? myślę, że to zależy od potrzeb, ale jednak wszelkie zdroworozsądkowe argumenty stoją za tym, aby to był jeden i ten sam cykl
2) wiesz co? myślę, że to zależy od potrzeb, ale jednak wszelkie zdroworozsądkowe argumenty stoją za tym, aby to był jeden i ten sam cykl