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
problem z wykresem sieci społecznościowej
Oto problem: Jest połączony wykres z węzłami reprezentującymi wiele osób. Każdy węzeł / osoba ma opinię na dany temat, np. Atut vs clinton, papierowe książki kontra kindle itp Celem jest, aby każdy węzeł na wykresie podzielał tę samą opinię, wybierając konkretny podzbiór węzłów, w określonej kolejności. Jeśli większość przyjaciół osoby …
3
Traktowanie grafów niekierowanych jako podkategorii grafów ukierunkowanych
Z grubsza, wykres bezkierunkowy jest bardzo podobny do wykresu skierowanego, gdzie dla każdej krawędzi (v, w) zawsze jest krawędź (w, v). To sugeruje, że akceptowalne może być wyświetlanie nieukierunkowanych wykresów jako podzestawu kierowanych wykresów (być może z dodatkowym ograniczeniem, że dodawanie / usuwanie krawędzi można wykonać tylko w pasujących parach). …
2
Jak skutecznie produkować wszystkie sekwencje binarne o równej liczbie zer i jedynek?
Binarnej sekwencji o długości nnn właśnie uporządkowaną sekwencję x1,…,xnx1,…,xnx_1,\ldots,x_n , tak że każdy xjxjx_j oznacza albo 000 lub 111 . Aby wygenerować wszystkie takie sekwencje binarne, można użyć oczywistej struktury drzewa binarnego w następujący sposób: katalog główny jest „pusty”, ale każde lewe dziecko odpowiada dodaniu 000 do istniejącego łańcucha, a …
2
NP-Kompletność problemu kolorowania wykresu
Alternatywne sformułowanie Wymyśliłem alternatywne sformułowanie do poniższego problemu. Alternatywne sformułowanie jest w rzeczywistości szczególnym przypadkiem poniżej problemu i wykorzystuje dwuczęściowe wykresy do opisania problemu. Uważam jednak, że alternatywny preparat jest nadal trudny do NP. Alternatywne sformułowanie wykorzystuje rozłączny zestaw przychodzących i wychodzących węzłów, co upraszcza definicję problemu. Biorąc pod uwagę …
5
Konwersja digrafu na niekierowany wykres w odwracalny sposób
Szukam algorytmu do konwersji digrafu (grafu kierunkowego) na graf niekierowany w sposób odwracalny, tzn. Digraf powinien być odtwarzalny, jeśli otrzymamy wykres niekierowany. Rozumiem, że przyjdzie to kosztem niekierowanego wykresu mającego więcej wierzchołków, ale nie mam nic przeciwko. Czy ktoś wie jak to zrobić lub może zasugerować jakieś referencje? Z góry …
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 …
1
Czy potrafimy znaleźć k najkrótszych ścieżek między wszystkimi parami szybciej niż wielokrotne rozwiązywanie problemu parami?
Chcę produkować kkk najkrótsza droga (kkkbyłoby mniej niż 10) między wszystkimi parami na wykresie. Wykres to (właściwie mapa metra): dodatnio ważony bezkierunkowy rzadki z około 100 węzłami Mój obecny plan ma zastosowanie kkknajkrótsza ścieżka trasy do każdej pary; Teraz szukam bardziej wydajnej alternatywy (prawdopodobnie z programowaniem dynamicznym).
3
Jak rozwiązać problem aranżacyjny w Archive Nationale of France przy użyciu teorii grafów?
Dobry wieczór! Właśnie odbywam staż w Archives Nationales of France i napotkałem sytuację, którą chciałem rozwiązać za pomocą wykresów ... I. Zakurzona sytuacja Chcemy zoptymalizować rozmieszczenie książek w mojej bibliotece zgodnie z ich wysokością, aby zminimalizować koszty archiwizacji. Wysokość i grubość książek są znane. Książki ułożyliśmy już w porządku rosnącymH1,H2,…,HnH1,H2,…,HnH_1,H_2,\dots,H_n(Nie …
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 …
3
Kompaktowa reprezentacja ścieżek na wykresie
Mam podzbiór prostych ścieżek na wykresie. Długość ścieżek jest ograniczonaredd. Jaki jest najbardziej zwarty sposób (pod względem pamięci), w jaki sposób mogę reprezentować ścieżki, tak aby nie były reprezentowane żadne inne ścieżki oprócz wybranych? Zauważ, że chcę użyć tej reprezentacji w algorytmie, który będzie powtarzał się przez ten podzbiór ścieżek …
1
Znalezienie najkrótszej ścieżki między dwoma węzłami
Biorąc pod uwagę ważony digraf G=V,EG=V,EG=V,Ei funkcja wagi, d(u,v)d(u,v)d(u,v), zwykle można użyć algorytmu Dijkstry, aby uzyskać najkrótszą ścieżkę. Interesuje mnie to, jak uzyskać2nd2nd2^{nd}- najkrótsza ścieżka, 3rd3rd3^{rd}-krótko i tak dalej. Pytania: Czy istnieje skuteczny algorytm do uzyskania i-tej najkrótszej ścieżki między dwoma węzłami na wykresie ważonym? Czy istnieje skuteczny algorytm pozwalający …
2
Projekt oceny rówieśniczej - wybór wykresu w celu uzyskania dokładnych rankingów / ocen
Tło. Piszę kod do półautomatycznej gradacji, używając gradacji rówieśniczej jako części procesu gradacji. Uczniowie otrzymują pary esejów na raz, a uczniowie mają suwak do wyboru, który jest lepszy io ile lepszy. np. suwak może wyglądać mniej więcej tak: A---X-B Na podstawie wyników oceny rówieśniczej eseje są klasyfikowane, a nauczyciel oceni …
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.