Wzór na ilość krawędzi w "grafie pełnym najbliżej"

[Kubaz]

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.



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

[leg14]

Jak definiujesz ,,położone najbliżej" ?

[Kubaz]

Specjalnie dołączyłem rysunek. Nie chodzi o wagi tylko o wierzchołki, które są sąsiadami

[leg14]

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.

[Kubaz]

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.

[leg14]

A to całkiem co innego. Czyli masz kratę \(\displaystyle{ n \times m}\) z wierzchołkami połączonymi tak jak na rysunku (na przykład na rysunku masz sytuację \(\displaystyle{ n =4, m=2}\)). Szukasz wzoru na ilość krawędzi. Zaczynamy od wzory na ilośc krawędzi, gdy \(\displaystyle{ m =2}\). Wtedy jest to \(\displaystyle{ 2(n-1) + 2(n-1) + n = 5n -4}\). Dalej indukcyjnie. O ile więcej krawędzi ma \(\displaystyle{ n \times (k+1)}\) od \(\displaystyle{ n \times k}\)?

[Kubaz]

\(\displaystyle{ 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?

[leg14]

Przecież chcesz mieć wzór na ilość krawędzi. Dlaczego krawędzie miałyby być zmienna? Przecież napisałem, że \(\displaystyle{ 5n -4}\) to wzór dla kraty \(\displaystyle{ n \times 2}\). Wziąłem go stąd, że sobie policzyłem na palcach. Wzory dla dowolnej kraty \(\displaystyle{ n \times m}\) nie ma - to zadanie dla Ciebie.

Indukcyjnie czyli jak?

graf powstały z kraty \(\displaystyle{ n \times (k+1)}\) powstaje z grafu kraty \(\displaystyle{ n \times k}\) przez dodanie \(\displaystyle{ 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 \(\displaystyle{ 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 \(\displaystyle{ n \times 2}\) już Ci pdoałem. T(n) to liczba nowych krawędzi powstałych po zrobieni uz \(\displaystyle{ n \times k}\) kraty \(\displaystyle{ n \times (k+1)}\).

[Kubaz]

Muszę to sobie przejrzeć na spokojnie, bo jeszcze nie do końca kumam

Ale póki co dzięki