Czy graf ma cykl o długości 4

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?

0

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

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ć.

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.

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

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)

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