Pytania otagowane jako graphs

Pytania o grafy, dyskretne struktury węzłów, które są połączone krawędziami. Popularne smaki to drzewa i sieci o dużej pojemności.

1
Znajdź proste cykle na wykresie ukierunkowanym
Dla mnie ten problem wygląda bardzo interesująco. Już miał znaleźć prosty cykl (tj. Cykl, w którym nie ma powtarzalnych węzłów) na ukierunkowanym wykresie. Moje rozwiązanie wygląda następująco, tzn. Ten wykres jest problemem przypadku: Wiem, że na wykresie jest cykl, w którym można znaleźć „tylne krawędzie” w wyszukiwaniu z głębokością pierwszą …
1
Znajdź najdłuższą ścieżkę od korzenia do liścia na drzewie
Mam drzewo (w sensie teorii grafów), takie jak następujący przykład: Jest to ukierunkowane drzewo z jednym węzłem początkowym (korzeń) i wieloma końcowymi węzłami (liście). Każda krawędź ma przypisaną długość. Moje pytanie brzmi: jak znaleźć najdłuższą ścieżkę, zaczynając od korzenia i kończąc na którymś z liści? Podejście brutalnej siły polega na …
3
Jak podejść do problemów związanych z dynamicznym wykresem
Zadałem to pytanie przy ogólnym przepełnieniu stosu i skierowano mnie tutaj. Świetnie będzie, jeśli ktoś będzie w stanie wyjaśnić, w jaki sposób ogólnie podejść do częściowych lub w pełni dynamicznych problemów graficznych. Na przykład: Znajdź najkrótszą ścieżkę między dwoma wierzchołkami na niekierowanym wykresie ważonym dla wystąpień, gdy krawędź jest usuwana …
2
Najkrótsza nie przecinająca się ścieżka dla wykresu osadzonego w płaszczyźnie euklidesowej (2D)
Jakiego algorytmu użyłbyś do znalezienia najkrótszej ścieżki wykresu, która jest osadzona w płaszczyźnie euklidesowej, tak aby ścieżka nie zawierała żadnych skrzyżowań własnych (w osadzaniu)? Na przykład na poniższym wykresie chcesz przejść z . Zwykle algorytm taki jak algorytm Dijkstry tworzyłby następującą sekwencję:( 0 , 0 ) → ( - 3 …
1
Wydajny algorytm odzyskiwania przejściowego zamknięcia ukierunkowanego wykresu acyklicznego
Próbuję rozwiązać problem z grafem (nie jest to praca domowa, tylko po to, aby ćwiczyć swoje umiejętności). Podaje się DAG , gdzie jest zbiorem wierzchołków, a krawędziami. Wykres jest reprezentowany jako lista przylegania, więc jest zbiorem zawierającym wszystkie połączenia . Moim zadaniem jest znalezienie których wierzchołki są osiągalne z każdego …
1
Kroki gwarantujące wyjście z labiryntu
Biorąc pod uwagę dwuwymiarowy labirynt, w którym możesz wydać 4 polecenia „ruch w górę / dół / prawo / lewo”. Znając labirynt, ale nie wiedząc, gdzie jest człowiek, jak znaleźć minimalną sekwencję poleceń, która gwarantuje wyjście z labiryntu? Szukam pojedynczej sekwencji poleceń, która zadziała bez względu na to, od którego …
2
Wykres resztkowy w maksymalnym przepływie
Czytam tutaj o problemie z maksymalnym przepływem . Nie mogłem zrozumieć intuicji stojącej za wykresem rezydualnym. Dlaczego podczas obliczania przepływu bierzemy pod uwagę tylne krawędzie? Czy ktoś może mi pomóc zrozumieć pojęcie wykresu resztkowego? Jak zmienia się algorytm w niekierowanych grafach?
2
Znajdowanie najkrótszych i najdłuższych ścieżek między dwoma wierzchołkami w DAG
Biorąc pod uwagę nieważony DAG (skierowane acykliczny wykres) oraz dwa wierzchołki i , jest możliwe znalezienie najkrótszej ścieżki, a najdłuższy z na w czasie wielomianowym? Długości ścieżek są mierzone liczbą krawędzi.s t s tD=(V,A)D=(V,A)D = (V,A)ssstttsssttt Interesuje mnie znalezienie zakresu możliwych długości ścieżek w czasie wielomianowym. Ps., To pytanie jest …
1
Czy wszystkie drzewa o minimalnej rozpiętości MST są osiągalne przez Kruskala i Prim?
Uważam, że to prawda, ale nie udało mi się uzyskać formalnego dowodu. Ale czy to prawda, że ​​każde minimalne drzewo opinające jest osiągalne dzięki zastosowaniu algorytmu Kruskala? Podobnie, czy dotyczy to algorytmu Prim? EDYCJA: Aby być bardziej precyzyjnym, chcę wiedzieć, czy otrzymując MST dla połączonego, niekierowanego, ważonego wykresu, czy jest …
4
Przejściowa redukcja DAG
Szukam algorytmu O (V + E) do znajdowania redukcji przechodnich przy danym DAG. To oznacza usunięcie jak największej liczby krawędzi, abyś mógł dosięgnąć v od ciebie, dla dowolnych v iu nadal możesz sięgnąć po usunięciu krawędzi. Jeśli jest to standardowy problem, proszę wskazać mi jakieś rozwiązanie modelowe.
13 algorithms  graphs  dag 
4
Algorytm Dijsktry zastosowany do problemu sprzedawcy podróżującego
Jestem nowicjuszem (całkowicie początkującym w teorii złożoności obliczeniowej) i mam pytanie. Powiedzmy, że mamy „problem sprzedawcy podróży”, czy poniższe zastosowanie algorytmów Dijkstry rozwiąże ten problem? Od punktu początkowego obliczamy najkrótszą odległość między dwoma punktami. Idziemy do rzeczy. Usuwamy punkt źródłowy. Następnie obliczamy następny najkrótszy punkt odległości od bieżącego punktu i …
1
Badania w teorii grafów a algorytmy grafowe
Mam bardzo ogólne pytanie. Jest to związane z badaniami. Interesuje mnie teoria grafów. Zrobiłem w tym kurs. Zrobiłem kilka tematów związanych z teorią grafów z punktu widzenia robienia tego jako student matematyki, a także studiowałem niektóre algorytmy grafów. Idę na staż badawczy z teorii grafów. Ale w mojej głowie jest …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.