On the Number of Shortest Weighted Paths in a Triangular Grid
Counting the number of shortest paths in various graphs is an important and interesting combinatorial problem, especially in weighted graphs with various applications. We consider a specific infinite graph here, namely the honeycomb grid. Changing to its dual, the triangular grid, paths between tria...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-01-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/8/1/118 |
| _version_ | 1818506190604206080 |
|---|---|
| author | Benedek Nagy Bashar Khassawneh |
| author_facet | Benedek Nagy Bashar Khassawneh |
| author_sort | Benedek Nagy |
| collection | DOAJ |
| description | Counting the number of shortest paths in various graphs is an important and interesting combinatorial problem, especially in weighted graphs with various applications. We consider a specific infinite graph here, namely the honeycomb grid. Changing to its dual, the triangular grid, paths between triangle pixels (we abbreviate this term to trixels) are counted. The number of shortest weighted paths between any two trixels of the triangular grid is discussed. For each trixel, there are three different types of neighbor trixels, 1-, 2- and 3-neighbours, depending the Euclidean distance of their midpoints. When considering weighted distances, the positive values <i>α</i>, <i>β</i> and <i>γ</i> are assigned to the ‘steps’ to various neighbors. We gave formulae for the number of shortest weighted paths between any two trixels in various cases by the respective weight values. The results are nicely connected to various numbers well-known in combinatorics, e.g., to binomial coefficients and Fibonacci numbers. |
| first_indexed | 2024-12-10T22:01:10Z |
| format | Article |
| id | doaj.art-329877cd398f41a5a8a67536b058139b |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-12-10T22:01:10Z |
| publishDate | 2020-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-329877cd398f41a5a8a67536b058139b2022-12-22T01:31:54ZengMDPI AGMathematics2227-73902020-01-018111810.3390/math8010118math8010118On the Number of Shortest Weighted Paths in a Triangular GridBenedek Nagy0Bashar Khassawneh1Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University, North Cyprus, via Mersin 10, Famagusta 99450, TurkeyDepartment of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University, North Cyprus, via Mersin 10, Famagusta 99450, TurkeyCounting the number of shortest paths in various graphs is an important and interesting combinatorial problem, especially in weighted graphs with various applications. We consider a specific infinite graph here, namely the honeycomb grid. Changing to its dual, the triangular grid, paths between triangle pixels (we abbreviate this term to trixels) are counted. The number of shortest weighted paths between any two trixels of the triangular grid is discussed. For each trixel, there are three different types of neighbor trixels, 1-, 2- and 3-neighbours, depending the Euclidean distance of their midpoints. When considering weighted distances, the positive values <i>α</i>, <i>β</i> and <i>γ</i> are assigned to the ‘steps’ to various neighbors. We gave formulae for the number of shortest weighted paths between any two trixels in various cases by the respective weight values. The results are nicely connected to various numbers well-known in combinatorics, e.g., to binomial coefficients and Fibonacci numbers.https://www.mdpi.com/2227-7390/8/1/118triangular gridhoneycomb networkweighted distancechamfer distancecombinatoricsshortest weighted pathspath counting |
| spellingShingle | Benedek Nagy Bashar Khassawneh On the Number of Shortest Weighted Paths in a Triangular Grid Mathematics triangular grid honeycomb network weighted distance chamfer distance combinatorics shortest weighted paths path counting |
| title | On the Number of Shortest Weighted Paths in a Triangular Grid |
| title_full | On the Number of Shortest Weighted Paths in a Triangular Grid |
| title_fullStr | On the Number of Shortest Weighted Paths in a Triangular Grid |
| title_full_unstemmed | On the Number of Shortest Weighted Paths in a Triangular Grid |
| title_short | On the Number of Shortest Weighted Paths in a Triangular Grid |
| title_sort | on the number of shortest weighted paths in a triangular grid |
| topic | triangular grid honeycomb network weighted distance chamfer distance combinatorics shortest weighted paths path counting |
| url | https://www.mdpi.com/2227-7390/8/1/118 |
| work_keys_str_mv | AT benedeknagy onthenumberofshortestweightedpathsinatriangulargrid AT basharkhassawneh onthenumberofshortestweightedpathsinatriangulargrid |