Wszystko

Najnowsze

Archiwum

wonsz_smieszek
  • 1
@MatexN: tak, zachłanne algorytmy kolorowania polegają po prostu na tym, że bierzesz kolejne wierzchołki i starasz się pokolorować używając jak najmniejszej liczby kolorów. Czyli kolorujesz kolorem 1 dopóki się da (nie ma krawędzi łączącej dwa wierzchołki o tym samym kolorze). Jak się nie da, to kolejny wierzchołek kolorem 2. Potem kolejny próbujesz znów kolorem 1, jak się nie da, to kolorem 2, jeżeli też się nie da, to wprowadzasz kolor
  • Odpowiedz
x.....x
x.....x
  • 2
Mam taki graf. Moimi E' są krawedzie b,f,g,i.
Graf G [E'] to tylko te krawędzie czy też ten wierzcholek dolny 12?
Analogicznie w G [E\E'] nie rysuję tych krawedzi, ale mam pytanie. Czy wtedy w tym grafie rysuję też wierzcholek 12?
W necie tego typu przykładów nie widziałem.
#kiciochpyta #matematyka #grafy
x.....x - Mam taki graf. Moimi E' są krawedzie b,f,g,i. Graf G [E'] to tylko te krawę...

źródło: comment_kxWIGTadkqdYRqMyLm1wr9Z3mRGBcOoD.jpg

Pobierz
  • 2
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
Jakubussimus
Jakubussimus
  • 1
@michvl: Indukcja :) pierwszy krok: jeśli drzewo ma jeden lub dwa wierzchołki, to nie ma problemu. W drugim kroku korzystamy z faktu, że każde drzewo (rzędu >=2) posiada co najmniej dwa liście, wybieramy jeden z nich i nadajemy mu wagę n, a następnie usuwamy go z grafu. Pozostały graf jest drzewem rzędu n-1, które umiemy z założenia indukcyjnego pokolorować tak, aby spełniał ten warunek. Po przywróceniu naszego liścia,
  • Odpowiedz
wytrzzeszcz
  • 4
Elo
chce zrobić grę w której gracz rozwiązuje labirynt jak w filmie Cube (struktura 3d ) i wymyśliłem że nie powinienem trzymać labiryntu od razu całego w bazie danych a dopiero w trakcie gry na bieżąco dobudowywać pomieszczenia.
Algorytm dobudowania wygada tak:
1.Gracz wchodzi do pomieszczenia
2.Jeśli pomieszczenie ma flagę "krawędź" to: 3 ; Jeśli nie: kończ
3. Dopóki istnieje miejsce (X,Y,Z) Gdzie nie ma pomieszczenia w promieniu r od aktualnego;
  • 6
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
mdfk
  • 3
Załóżmy, że G jest ścieżka o 6 wierzchołkach, ponumerowanych kolejno 1,2,3,4,5,6.

Ile jest spacerów długości 100 z wierzchołka 1 do 6?

Ktoś ma jakiś pomysł? chyba jedyne rozwiązanie to wymyślenie jakiejś kombinacji spacerów.

#matematyka #grafy #studbaza
  • 5
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
Jakubussimus
Jakubussimus
  • 2
@mdfk: Można to na pewno zrobić w ten sposób, że piszesz sobie macierz sąsiedztwa tego grafu, podnosisz ją do potęgi 100 i sumujesz współczynniki.

Edit: sorki, suma współczynników to będą wszystkie możliwe spacery. Spacery z wierzchołka 1 do 6 to wyraz w 6 wierszu i 1 kolumnie.
  • Odpowiedz
jwojtas
  • 1
Jak przechowywać wagę krawędzi dla grafu?

Każdy wierzchołek ma listę referencji do innych wierzchołków, ale nie wiem gdzie trzymać ich wagę, czy w dodatkowej liście czy da się jakoś podpiąć do listy referencji. Help, newbie here :/

#programowanie #java #grafy
  • 7
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
Wozyack
  • 5
@jwojtas: Najprościej - zamiast listy stwórz mapę, gdzie kluczem będzie referencja do sąsiedniego węzła, a wartością waga krawędzi między danym wierzchołkiem a sąsiadami.
  • Odpowiedz
jwojtas
  • 2
Jakiś poradnik grafów potrzebuje, albo jak zaimplementować listę sąsiedztwa w javie etc? Bo nie ma wskaźników a tak to nauczyciel tłumaczy nam na przykładzie cpp :/

#java #grafy #licbaza
  • 4
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
Wozyack
  • 2
@jwojtas: Nie ma wskaźników, ale są referencje. Obiekt reprezentujacy węzeł grafu powinien mieć listę referencji do sąsiednich węzłów.

Taki mały przykład:

Node node; // to jest referencja pusta, na nic nie
  • Odpowiedz
franczi
  • 1
#algorytmy #programowanie #studbaza #grafy #kiciochpyta #pytanie #pytaniedoeksperta #tagujetogowno

Za pomocą algorytmu Dijkstry da się wyznaczyć najkrótszą ścieżkę między dwoma wierzchołkami grafu. Pytanie czy jest jakiś mądry sposób na znalezienie kolejnej najkrótszej ścieżki między tymi dwoma wierzchołkami - mamy skończoną ilość ścieżek między dwoma wierzchołkami posortowaną malejąco wg kosztu przejścia i ostatnia jest najkrótsza, to ja potrzebuję
  • 5
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
O.....i
O.....i
  • 1
@franczi: Rozwiązanie mam troszkę toporne, ale może Ci pomoże:

Druga najkrótsza ścieżka musi różnić się od najkrótszej ścieżki co najmniej jednym odcinkiem (między dwoma wierzchołkami grafu). Skoro tak, to po wyznaczeniu najkrótszej ścieżki weź tyle grafów ile najkrótsza ma odcinków, z każdego grafu usuń jeden, inny, należący do najkrótszej ścieżki odcinek, dla każdego znajdź najkrótszą ścieżkę za pomocą algorytmu Dijkstry i wybierz najkrótszą z nich. I to będzie ta druga
  • Odpowiedz
T.....K
T.....K
  • 2
#matematyka #informatyka #grafy

jak nazywa się własność grafu skierowanego, że pomiędzy każdymi dwoma wierzchołkami istnieje nie więcej niż jedna droga?

jeżeli graf posiadał powyższą własność, jak sprawdzić czy ją zachowa po dodaniu nowej krawędzi?
  • 8
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
s.....7
s.....7
  • 1
#grafy

#kiciochpyta

Jak przeszukujemy graf w szerz, a graf zawiera litery symbolizujące nazwy miast (Po, Gd, Ra, etc etc) i zakładamy alfabetyczne porządkowanie sąsiadów to na stos kładziemy te co mają wcześniejszą literę alfabetu w taki sposób by pierwsze schodziły?
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
Marmite
  • 2
Mamy jakichś speców od grafów na pokładzie? "Wyznacz liczbę podgrafów pełnego grafu K10, które są izomorficzne z grafem: a) P8" (Pn to ścieżka o n wierzchołkach) - ja bym dał (10 po 8) * 8!, a w odpowiedziach jest to samo tylko pomnożone jeszcze przez 1/2. Ktoś potrafi mi powiedzieć czemu? Za cholerę nie wiem skąd tu jest ta 1/2 i dodatkowo pojawia się jeszcze we wszystkich innych podpunktach tego zadania -
  • 2
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach

Powiązane tagi