szukanie zaawansowane
 [ Posty: 9 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 5 sty 2018, o 14:01 
Użytkownik

Posty: 48
Witam, po pierwsze zastanawiałem się czy posiada swoją nazwę graf, który łączy wierzchołki położone najbliżej tj. na załączonym rysunku.

Obrazek

Po drugie już na poważnie szukałem wzroru na liczbę krawędzi w tym cudzie, ale nie znalazłem. Zauważyłem jedynie empirycznie, że jeśli:

2w = 1k,
3w = 3k,
4w = 6k,
5w = 8e,
6w = 11e,
7w = 13e,
8w = 16e.

Z tego wynika, że liczba krawędzi w takim grafie rośnie cyklicznie raz o 2, raz o 3 wraz ze wzrostem o 1 liczby wierzchołków. Ciekawe, tylko jak to zapisać wzrorem?

Pozdr
Góra
Mężczyzna Offline
PostNapisane: 5 sty 2018, o 14:13 
Użytkownik
Avatar użytkownika

Posty: 2773
Lokalizacja: Radom
Jak definiujesz ,,położone najbliżej" ?
Góra
Mężczyzna Offline
PostNapisane: 5 sty 2018, o 14:20 
Użytkownik

Posty: 48
Specjalnie dołączyłem rysunek. Nie chodzi o wagi tylko o wierzchołki, które są sąsiadami
Góra
Mężczyzna Offline
PostNapisane: 5 sty 2018, o 14:29 
Użytkownik
Avatar użytkownika

Posty: 2773
Lokalizacja: Radom
Na rysunku łączysz z wierzchołkiem wierzchołki, które są od niego oddalone o różne wartości. Stąd moje pytanie - co to znaczy najbliżej? Definicja takiego grafu wymaga umiejscowienia jego wierzchołków w jakiejś przestrzeni metrycznej.
Góra
Mężczyzna Offline
PostNapisane: 5 sty 2018, o 14:37 
Użytkownik

Posty: 48
Generalnie chodzi o to, że piszę gre na Androida. Na razie wstępne koncepcje, ale ekran jest podzielony na siatkę powiedzmy 6x10. Po tych polach chodzi postać i i ma za zadanie przemieścić się na pole wskazane przez usera palcem. A żeby przemieścić się na pole (nie chaotycznie, w jednej linii) mając do dyspozycji ruchy pionowe, poziome i na ukos (koszt każdego póki co jednakowy powiedzmy 1) potrzeba jakiejś logiki. Od razu pomyślałem o algorytmie Dijsktry i tak oto tu jestem.
Góra
Mężczyzna Offline
PostNapisane: 5 sty 2018, o 15:03 
Użytkownik
Avatar użytkownika

Posty: 2773
Lokalizacja: Radom
A to całkiem co innego. Czyli masz kratę n \times m z wierzchołkami połączonymi tak jak na rysunku (na przykład na rysunku masz sytuację n =4, m=2). Szukasz wzoru na ilość krawędzi. Zaczynamy od wzory na ilośc krawędzi, gdy m =2. Wtedy jest to 2(n-1) + 2(n-1)  + n = 5n -4. Dalej indukcyjnie. O ile więcej krawędzi ma n \times (k+1) od n \times k?
Góra
Mężczyzna Offline
PostNapisane: 5 sty 2018, o 15:23 
Użytkownik

Posty: 48
2(n-1) + 2(n-1)  + n = 5n -4 hmm dlaczego pod n nie podstawiłeś 4 skoro jest to wiadome? Co z tego równania wynika skoro nie ma zmiennej k (krawędzi) ? I w ogóle skad wziąłeś ten wzór?

Indukcyjnie czyli jak?
Góra
Mężczyzna Offline
PostNapisane: 5 sty 2018, o 15:39 
Użytkownik
Avatar użytkownika

Posty: 2773
Lokalizacja: Radom
Przecież chcesz mieć wzór na ilość krawędzi. Dlaczego krawędzie miałyby być zmienna? Przecież napisałem, że 5n -4 to wzór dla kraty n \times 2. Wziąłem go stąd, że sobie policzyłem na palcach. Wzory dla dowolnej kraty n \times m nie ma - to zadanie dla Ciebie.
Cytuj:
Indukcyjnie czyli jak?

graf powstały z kraty n \times (k+1) powstaje z grafu kraty n \times k przez dodanie n wierzchołków i iluś krawędzi. Jeśli wyznaczysz liczbę nowych krawędzi (w zależności od n), to będziesz miał gotowy wzór. Bo Wzor(n \times m) = Wzor(n \times (m-1)) + T(n) = 2T(n) + Wzor(n \times (m-2)=...= (m-2)T(n) + Wzor(n \times 2 ). Wzor na n \times 2 już Ci pdoałem. T(n) to liczba nowych krawędzi powstałych po zrobieni uz n \times k kraty n \times (k+1).
Góra
Mężczyzna Offline
PostNapisane: 5 sty 2018, o 23:40 
Użytkownik

Posty: 48
Muszę to sobie przejrzeć na spokojnie, bo jeszcze nie do końca kumam ;)

Ale póki co dzięki
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 9 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ilość podziałów liczby n - zadanie 2  mantoo  4
 Ilość liczb z przedziału których suma cyfr jest równa x  snaf014  4
 Dwa wierzchołki w grafie prostym  Nitr0Skay  5
 Wzór jawny sprawdzenie  Albatross201  2
 Dowód nierówności w grafie  Fray  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl