MatexN
#studbaza #studia #matematyka #grafy #teoriagrafow
Mam taki problem, mam zadany taki graf i muszę go pokolorować algorytmem LF i SL.
Wiem jak to powinno działać w praktyce, jednak nie mam pojęcia jak zabrać się za kolorowanie :/
Szukałem w necie jakiś przykładów krok po kroku ale nic nie mogę znaleźć.
1
  • Najlepsze
  • Wszystkie komentarze
wonsz_smieszek
@MatexN: chyba za dużo myślisz jak na takie zadanie :) Jeżeli stopień jest równy, to w dowolnej kolejności, przecież to heurystyka! :) Możesz zresztą sprawdzić wszystkie kolejności - któraś może dać lepszy wynik :)
1
wonsz_smieszek
@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
1
x.....x
x.....x
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
2
  • Najlepsze
  • Wszystkie komentarze
Jakubussimus
Jakubussimus
@xDawidMx: zbiór wierzchołków grafu G[E'] składa się wyłącznie z końców krawędzi z E', czyli 12 nie ma w tym zbiorze. Z tego samego powodu wierzchołka 12 nie ma też w G[E-E'].
0
x.....x
x.....x
@Jakubussimus: dzięki bardzo.
W G - E' rysuje wszystko oprócz tych krawędzi
0
michvl
#matematyka #grafy #matematykadyskretna
Mirki, potrzebuję pomocy z jednym zadaniem. Komis się zbliża, a ja kompletnie nie rozumiem jak się za to wziąć (╯︵╰,).
1
  • Najlepsze
  • Wszystkie komentarze
Jakubussimus
Jakubussimus
@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,
1
Jakubussimus
Jakubussimus
@michvl: dla każdego i>1 liczebność zbioru wierzchołków, które są sąsiadami v_i oraz mają etykietę mniejszą od i, jest równa 1
1
wytrzzeszcz
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;
4
  • Najlepsze
  • Wszystkie komentarze
superbybak
@wytrzzeszcz: takie parę szczegółów:

- możesz się (bardzo teoretycznie) zapętlić na etapie 3-5, jeśli ciągle będziesz losować miejsce które zaraz potem usuniesz; może warto losować tylko z miejsc, które mają sąsiadów?

- graf na pewno kiedyś stanie się spójny, bo nie masz żadnego ograniczenia górnego; teoretycznie wszystkie kostki mogą być pomieszczeniami (przy odpowiednio długiej grze)

- skoro masz mało miejsca na graf, podejrzewam że wolałbyś mieć jakąś kontrolę nad maksymalną
0
mdfk
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
3
  • Najlepsze
  • Wszystkie komentarze
jwojtas
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
1
  • Najlepsze
  • Wszystkie komentarze
jwojtas
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
2
  • Najlepsze
  • Wszystkie komentarze
J.....Q
J.....Q
Mireczki matematyki, możecie zamienić mi ten graf na kod prufera ? Bo nie jestem pewien czy to właściwie rozumiem.

http://i.imgur.com/5CzJ5HJ.png

Z góry dzięki!

#matematyka #graf #teoriagrafow #grafy
1
  • Najlepsze
  • Wszystkie komentarze
lifapek
Wykaż że każdy graf G zawiera przynajmniej X(G) * ( X(G) - 1 ) / 2 krawędzi, gdzie X(G) to liczba chromatyczna dla G

#grafy #matematykadyskretna #egzamin
1
Zwykly_Czlowiek
Kurna, nie rozumiem.

"graf, który można narysować na płaszczyźnie tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą."

A na rysunku przecież się przecinają te krawędzie.

http://pl.wikipedia.org/wiki/Graf_planarny
1
  • Najlepsze
  • Wszystkie komentarze
franczi
#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ę
1
  • Najlepsze
  • Wszystkie komentarze
T.....K
T.....K
#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?
2
  • Najlepsze
  • Wszystkie komentarze
Wyrewolwerowanyrewolwer
Mirki! Jakie jest praktyczne zastosowanie grafów? Tak na zwykły dzień, żeby łatwiej było mi zrozumieć.

Miło byłoby, gdyby było z jakimś przykładem.

Dzięki

#informatyka #algorytmy #grafy #teoriagrafow #czytamcalatealgorytmikeinicnierozumie
1
  • Najlepsze
  • Wszystkie komentarze
bratbud
Poimplementujmy! #grafy #bst
1
s.....7
s.....7
#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?
1
WielkiStalowyNalesnikZaglady
Treść przeznaczona dla osób powyżej 18 roku życia...
2
  • Najlepsze
  • Wszystkie komentarze
Marmite
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
  • Najlepsze
  • Wszystkie komentarze

Powiązane tagi