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
Jak zmniejszyć liczbę skrzyżowanych krawędzi na schemacie?
Pracuję nad edytorem diagramów. Diagramy przedstawiają kształty 2D ( węzły ) połączone ze złączami ( krawędziami ). Chciałbym dodać operację, która, biorąc pod uwagę wybór węzłów, „rozplątuje” je: zmienia ich położenie, jeśli to możliwe, aby zmniejszyć liczbę przecinających się krawędzi (i jest w porządku, jeśli krawędzie będą musiały być rysowane …
1
Czy istnieje skuteczny algorytm do określania, czy wykres ma nietrywialny automorfizm?
Pracuję nad problemem związanym z kwadratami łacińskimi i chcę metody, która zasadniczo sprowadza się do problemu decyzyjnego: Dane wejściowe : skończony, prosty wykres G. Dane wyjściowe : YESjeśli G ma nietrywialny automorfizm, w NOprzeciwnym razie. W związku z tym... Pytanie : Czy istnieje skuteczny algorytm do określania, czy wykres ma …
2
Warunki, aby wykres dwudzielny był płaski, bez krawędzi biegnących wokół wierzchołków
Dwustronny wykres jest płaski, jeśli nie ma nieletnich lub .K.3 , 3K3,3K_{3, 3}K.5K5K_5 Szukam koniecznych i / lub wystarczających warunków, aby umożliwić rysunki planarne bez krawędzi „przechodzących” przez zestawy wierzchołków. Są to rysunki spełniające: Wszystkie wierzchołki jednej części są rysowane na jednej linii pionowej. Wierzchołki drugiej części są rysowane na …
1
Najcięższy plansza podrzędna
Rozważ następujący problem. Biorąc pod uwagę: Pełny wykres z rzeczywistymi nieujemnymi wagami na krawędziach. Zadanie: znajdź płaski wykres podrzędny o maksymalnej masie. („Maksimum” wśród wszystkich możliwych płaskich wykresów podrzędnych.) Uwaga: Podgraf maksymalnej wagi będzie triangulacją; jeśli cały wykres jest na wierzchołkach, będzie miał krawędzi.nnnm = 3 n - 6m=3)n-6m=3n-6 Pytanie: …
1
Jaki jest najbardziej wydajny algorytm i struktura danych do utrzymywania informacji o podłączonych komponentach na wykresie dynamicznym?
Powiedzmy, że mam niedokierowany skończony wykres rzadki i muszę być w stanie efektywnie uruchamiać następujące zapytania: IsConnected(N1,N2)IsConnected(N1,N2)IsConnected(N_1, N_2) - zwraca jeśli istnieje ścieżka między i , w przeciwnym razieTTTN1N1N_1N2N2N_2FFF ConnectedNodes(N)ConnectedNodes(N)ConnectedNodes(N) - zwraca zestaw węzłów, które są osiągalne zNNN Można to łatwo zrobić przez wstępne obliczenie połączonych elementów wykresu. Oba zapytania …
1
Minimalny rozcięcie na ważonych ukierunkowanych wykresach acyklicznych z potencjalnie ujemnymi wagami
Wystąpił następujący problem: Biorąc pod uwagę ukierunkowany wykres acykliczny z rzeczywistymi wartościami grubości krawędzi oraz dwoma wierzchołkami s i t, oblicz minimalny st st cut. Dla ogólnych wykresów jest to trudne NP, ponieważ można w prosty sposób zredukować maksymalne cięcie, po prostu odwracając wagi krawędzi (popraw mnie, jeśli się mylę). …
1
Dlaczego złożoność ujemnego anulowania cyklu ?
Chcemy rozwiązać problem minimalnego przepływu kosztów za pomocą ogólnego algorytmu anulowania cyklu ujemnego. Oznacza to, że zaczynamy od losowego prawidłowego przepływu, a następnie nie wybieramy żadnych „dobrych” cykli ujemnych, takich jak cykle o średnich kosztach minimalnych, ale używamy Bellman-Ford do odkrycia minimalnego cyklu i zwiększenia wzdłuż odkrytego cyklu. Niech będzie …
1
Problem chińskiego listonosza: znalezienie najlepszych połączeń między węzłami nieparzystego stopnia
Piszę program, rozwiązując problem chińskiego listonosza (znany również jako problem z inspekcją trasy) w niedokierowanym drafcie i obecnie napotykam problem, aby znaleźć najlepsze dodatkowe krawędzie do łączenia węzłów o dziwnym stopniu, dzięki czemu mogę obliczyć obwód Eulera. Może istnieć (biorąc pod uwagę rozmiar wykresu, który chce zostać rozwiązany) ogromna kombinacja …
3
Unikalna ścieżka na ukierunkowanym wykresie
Projektuję algorytm dla klasy, który określi, czy skierowany wykres jest unikalny w odniesieniu do wierzchołka vvv tak, że dla każdego u ≠ vu≠vu \ne v jest co najwyżej jedna ścieżka z vvv do uuu. Zacząłem od użycia BFS (wyszukiwanie szerokości), aby znaleźć najkrótszą ścieżkę od v do innego wierzchołka u, …
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.