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.

2
Rekonstrukcja wykresów z rozkładu stopni
Biorąc pod uwagę rozkład stopni, jak szybko możemy zbudować wykres zgodny z danym rozkładem stopni? Szkic łącza lub algorytmu byłby dobry. Algorytm powinien zgłaszać „brak”, ponieważ nie można zbudować żadnego wykresu i dowolnego przykładu, jeśli można zbudować wiele wykresów.
1
Znajdź najkrótsze ścieżki na zważonym wykresie unipatycznym
Mówi się, że ukierunkowany wykres jest unipatyczny, jeśli dla dowolnych dwóch wierzchołków i na wykresie istnieje co najwyżej jedna prosta ścieżka od do .uuuvvvG=(V,E)G=(V,E)G=(V,E)uuuvvv Załóżmy, że otrzymałem wykres jednoczynnościowy taki, że każda krawędź ma dodatnią lub ujemną wagę, ale nie zawiera żadnych ujemnych cykli masy.GGG Z tego chcę znaleźć algorytm, …
2
Dlaczego nie możemy znaleźć najkrótszych ścieżek o ujemnych wagach, po prostu dodając stałą, aby wszystkie wagi były dodatnie?
Obecnie czytam wprowadzenie do algorytmów i przyszedłem przez algorytm Johnsona, który polega na upewnieniu się, że wszystkie ścieżki są pozytywne. algo zależy od znalezienia nowej funkcji wagi (w '), która jest dodatnia dla wszystkich krawędzi i zachowuje poprawność relacji najkrótszych ścieżek. Odbywa się to poprzez obliczenie wartości h (s), h …
3
Jakie jest znaczenie „szerokość” przy pierwszym wyszukiwaniu?
Uczyłem się o pierwszym wyszukiwaniu szerokości i przyszło mi do głowy pytanie, dlaczego tak nazywa się BFS. W książce Wprowadzenie do algorytmów CLRS przeczytałem następujący powód: Poszukiwanie szerokości jest tak nazwane, ponieważ równomiernie rozszerza granicę między odkrytymi i nieodkrytymi wierzchołkami na całej szerokości granicy. Nie jestem jednak w stanie zrozumieć …
1
Jak szybko możemy obliczyć rozmiar maksymalnego dopasowania na nieważonym grafie dwustronnym?
Czy istnieje sposób na obliczenie wielkości maksymalnego dopasowania na nieważonym grafie dwustronnym bardziej efektywnie (np. Szybciej) niż obliczenie maksymalnego dopasowania? Jest to dalekie ujęcie, ale często interesującym problemem jest unikanie takich niepotrzebnych obliczeń. Motywacja Problem, który próbuję rozwiązać, to match-2, w którym oba zestawy mają różne rozmiary. Muszę ustalić, czy …
1
Generuj sieci bez skali z rozkładami stopni mocy i prawa za pomocą Barabasi-Alberta
Próbuję odtworzyć sieci syntetyczne (wykresy) opisane w niektórych artykułach. Stwierdzono, że model Barabasi-Albert został wykorzystany do stworzenia „sieci rozkładach stopni mocy, P_A (k) ∝ k ^ {- λ}PA(k)∝k−λPA(k)∝k−λP_A(k) ∝ k^{-λ} ”. PAPAP_A to rozkład prawdopodobieństwa, który zwraca prawdopodobieństwo węzła o stopniu kkk . Na przykład PA(2)PA(2)P_A(2) wskazuje prawdopodobieństwo losowego wyboru …
3
Zrozumienie algorytmu problemu ze stacją benzynową
W przypadku problemu ze stacją benzynową podajemy miast i drogi między nimi. Każda droga ma długość, a każde miasto określa cenę paliwa. Jedna jednostka drogi kosztuje jedną jednostkę paliwa. Naszym celem jest przejście ze źródła do miejsca docelowego w najtańszy możliwy sposób. Nasz czołg jest ograniczony pewną wartością.{ 0 , …
1
Czy to trudne NP? Nie mogę tego udowodnić.
Mam problem i myślę, że jest to trudny NP, ale nie mogę tego udowodnić. Oto wykres warstw, w którym warstwa 0 jest najwyższą warstwą, a warstwa L najniższą. istnieje pewna ukierunkowana krawędź między warstwami, gdzie krawędź (A, B) wskazuje, że węzeł A może [pokrywać] węzeł B. A kiedy A może …
11 graphs  np 
1
Średnia długość ścieżek st (prostych) na skierowanym wykresie
Biorąc pod uwagę fakt, że wyliczenie ścieżki - jest problemem # P-zupełnym, czy mogłyby istnieć wydajne metody obliczające (lub przynajmniej przybliżające) średnią długość ścieżki - bez ich wyliczania? Co jeśli ścieżki mogą ponownie odwiedzać wierzchołki?t s tssstttsssttt Pomocne mogą być również odpowiednie wyniki na specjalnych wykresach.
1
Ukierunkowane znalezienie związku
Rozważ skierowany wykres na którym można dynamicznie dodawać krawędzie i tworzyć określone zapytania.GGG Przykład: las rozłączny Rozważ następujący zestaw zapytań: arrow(u, v) equiv(u, v) find(u) pierwszy dodaje strzałkę do wykresu, drugi decyduje, czy u ↔ ∗ v , ostatni znajduje kanoniczny reprezentant klasy równoważności ↔ ∗ , tj. r ( …
1
Wykresy, które powodują, że DFS i BFS przetwarzają węzły w dokładnie tej samej kolejności
W przypadku niektórych wykresów algorytmy wyszukiwania DFS i BFS przetwarzają węzły w dokładnie tej samej kolejności, pod warunkiem, że oba rozpoczynają się w tym samym węźle. Dwa przykłady to wykresy będące ścieżkami i wykresy w kształcie gwiazdy (drzewa o głębokości z dowolną liczbą dzieci). Czy istnieje sposób kategoryzowania wykresów spełniających …
1
Wnioskowanie o rodzajach uściślenia
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if …
11 programming-languages  logic  type-theory  type-inference  machine-learning  data-mining  clustering  order-theory  reference-request  information-theory  entropy  algorithms  algorithm-analysis  space-complexity  lower-bounds  formal-languages  computability  formal-grammars  context-free  parsing  complexity-theory  time-complexity  terminology  turing-machines  nondeterminism  programming-languages  semantics  operational-semantics  complexity-theory  time-complexity  complexity-theory  reference-request  turing-machines  machine-models  simulation  graphs  probability-theory  data-structures  terminology  distributed-systems  hash-tables  history  terminology  programming-languages  meta-programming  terminology  formal-grammars  compilers  algorithms  search-algorithms  formal-languages  regular-languages  complexity-theory  satisfiability  sat-solvers  factoring  algorithms  randomized-algorithms  streaming-algorithm  in-place  algorithms  numerical-analysis  regular-languages  automata  finite-automata  regular-expressions  algorithms  data-structures  efficiency  coding-theory  algorithms  graph-theory  reference-request  education  books  formal-languages  context-free  proof-techniques  algorithms  graph-theory  greedy-algorithms  matroids  complexity-theory  graph-theory  np-complete  intuition  complexity-theory  np-complete  traveling-salesman  algorithms  graphs  probabilistic-algorithms  weighted-graphs  data-structures  time-complexity  priority-queues  computability  turing-machines  automata  pushdown-automata  algorithms  graphs  binary-trees  algorithms  algorithm-analysis  spanning-trees  terminology  asymptotics  landau-notation  algorithms  graph-theory  network-flow  terminology  computability  undecidability  rice-theorem  algorithms  data-structures  computational-geometry 
3
Różnica między krawędziami poprzecznymi i przednimi w DFT
W pierwszym drzewie głębokości znajdują się krawędzie, które definiują drzewo (tj. Krawędzie, które zostały użyte podczas przejścia). Pozostały pewne krawędzie łączące niektóre inne węzły. Jaka jest różnica między krawędzią poprzeczną a przednią? Z wikipedii: Na podstawie tego drzewa łączącego krawędzie oryginalnego wykresu można podzielić na trzy klasy: krawędzie przednie, które …
2
Dlaczego uważa się, że DFS ma złożoność przestrzeni ?
Według tych notatek , DFS jest uważany za złożoność przestrzeń, gdzie jest współczynnik rozgałęzienia drzewa i jest maksymalna długość każdej ścieżki w przestrzeni stanów.O(bm)O(bm)O(bm)bbbmmm To samo zostało powiedziane na tej stronie Wikibook w Search Uninformed Search . Teraz „infobox” artykułu Wikipedii na temat DFS przedstawia następujące aspekty złożoności algorytmu: O(|V|)O(|V|)O(|V|) …
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.