Czy graf ma cykl o długości 4

Odpowiedz Nowy wątek
2019-05-28 01:33
0

Mam zadany graf o V wierzchołkach w postaci macierzy sąsiedztwa i mam napisać funkcję która sprawdza czy zadany graf ma cykl o długości 4. Złożoność oczekiwana O(V^3). Znalazłem algorytm na internecie że podnosząc macierz do potęgi 4 mamy w polu [i,j] ilość marszrut z wierzchołka i do wierzchołka j ale to są marszruty i można wiele razy przechodzić po danej krawędzi. Pytanie czy idzie ten algorytm przerobić tak żeby znajdował cykle a nie marszruty?

Pozostało 580 znaków

2019-05-28 06:42
0

czemu nie użyć alg. do cykli? https://eduinf.waw.pl/inf/alg/001_search/0133.php


Dziura w ścianie gdzie Panowie widzą Panie,
Rick and Morty, season 1.
Szukam tej dziury, jak coś dajcie znać gdzie jest :D

Pozostało 580 znaków

2019-05-28 07:59
0

Ponieważ mam znaleźć cykl dokładnie o długości 4 a nie czy istnieje cykl jakikolwiwek. A poza tym mam skorzystać właśnie z tego algorytmu tylko go przerobić.

Pozostało 580 znaków

2019-05-28 08:35
1

Znalazłem algorytm na internecie że podnosząc macierz do potęgi 4 mamy w polu [i,j] ilość marszrut

A poza tym mam skorzystać właśnie z tego algorytmu tylko go przerobić.

Skoro sam sobie znalazłeś ten algorytm "na internecie", to co Cię trzyma przy nim i czermu "właśnie jego masz przerobić"?

Ponieważ mam znaleźć cykl dokładnie o długości 4 a nie czy istnieje cykl jakikolwiwek

Przecież algorytm podrzucony przez @youmound znajduje konkretne cykle, a w przykładach nawet je printuje. Jaki to problem wziąć ten algorytm i przerobić odrzucając cykle, które nie mają wybranej długości? Przecież to jest jedno sprawdzenie długości cyklu. Jeden if cycle_length == 4. I tyle.


Prosząc o pomoc w wiadomości prywatnej odbierasz sobie szansę na otrzymanie pomocy od kogoś bardziej kompetentnego :)
edytowany 1x, ostatnio: superdurszlak, 2019-05-28 09:50

Pozostało 580 znaków

2019-05-28 08:41
1

wystarczy zmodyfikować wyżej już wspomniany dfs i numerować wierzchołki w taki sposób że gdy dodajemy wierzchołek na stos to dajemy mu numer +1 w stosunku do obecnego, jak znajdziemy cykl to sprawdzamy czy różnica w numerach wynosi 4. Tyle że to będzie miało złożoność O(V^2) na macierzy sąsiedztwa, więc coś mi chyba umyka :D


#Dżunior React Devloper wanna be#
Każdy algorytm w O(v^2) jest też w O(V^3), więc wszystko gra. - enedil 2019-05-31 00:33

Pozostało 580 znaków

2019-05-31 00:42
0

Jeśli zaś chodzi o rozwiązanie używające mnożenia macierzy, nic prostszego. Niech A będzie tą macierzą sąsiedztwa. A reprezentuje ilość marszrut długości 1 pomiędzy dowolnymi wierzchołkami. A^2 reprezentuje ilość marszrut długości 2, itd. Jeśli cykl jest długości 4, to albo jest prosty, albo składa się z dwóch cykli długości 2. To znaczy z że szukana odpowiedź to trace(A^4) - suma_kwadratów_przekątnej(A^2)

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0