Pytania otagowane jako graph-theory

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
Czy pochodna wykresu jest związana z listami przyległości?
Niektóre prace Conora McBride'a, Diff , Dissect , wiążą pochodną typów danych z ich „typem jednootworowych kontekstów”. Oznacza to, że jeśli weźmiesz pochodną typu, pozostanie ci typ danych, który pokazuje, jak typ danych wygląda od wewnątrz w danym punkcie. Na przykład, jeśli masz listę (w Haskell) data List a = …
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?
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 …
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.
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
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 …
2
Problem izomorfizmu grafów dla grafów znakowanych
W przypadku grafów nieznakowanych problemem izomorfizmu grafów można zająć się szeregiem algorytmów, które działają bardzo dobrze w praktyce. Oznacza to, że chociaż najgorszy przypadek czasu działania jest wykładniczy, zwykle ma on czas działania wielomianowego. Miałem nadzieję, że sytuacja jest podobna w przypadku wykresów oznaczonych. Jednak naprawdę ciężko mi znaleźć jakiekolwiek …
2
Najdłuższy cykl zawarty w dwóch cyklach
Czy następujący problem NP-jest kompletny? (Zakładam, że tak). Wprowadź: niekierowany wykres, na którym zbiór zboczy może zostać rozłożony na dwa proste cykle rozłączne od krawędzi ( nie są one częścią danych wejściowych).k∈N,G=(V,E)k∈N,G=(V,E)k \in \mathbb{N},G=(V,E) Pytanie: Czy istnieje prosty cykl w o długości większej niż ?kGGGkkk Oczywiście problem dotyczy NP, a …
2
Chromiczny wielomian kwadratu
Rozważ kwadrat, ABCD. Intuicyjnie wydawało mi się, że jego wielomian chromatyczny to λ ( λ - 1 ) ( λ - 1 ) ( λ - 2 )λ(λ-1)(λ-1)(λ-2))\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2) tam, gdzie dostępne są kolory λλ\lambda .. Oznacza to, że istnieje λλ\lambda sposobów na wybranie koloru …
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.