Continued Fractions and Unique Factorization on Digraphs
We show that the characteristic series of walks (paths) between any two vertices of any finite digraph or weighted digraph G is given by a universal continued fraction of finite depth involving the simple paths and simple cycles of G. A simple path is a walk forbidden to visit any vertex more than o...
| Hoofdauteurs: | , , |
|---|---|
| Formaat: | Journal article |
| Gepubliceerd in: |
2012
|
| _version_ | 1826299337564487680 |
|---|---|
| author | Giscard, P Thwaite, S Jaksch, D |
| author_facet | Giscard, P Thwaite, S Jaksch, D |
| author_sort | Giscard, P |
| collection | OXFORD |
| description | We show that the characteristic series of walks (paths) between any two vertices of any finite digraph or weighted digraph G is given by a universal continued fraction of finite depth involving the simple paths and simple cycles of G. A simple path is a walk forbidden to visit any vertex more than once. We obtain an explicit formula giving this continued fraction. Our results are based on an equivalent to the fundamental theorem of arithmetic: we demonstrate that arbitrary walks on G uniquely factorize into nesting products of simple paths and simple cycles. Nesting is a walk product which we define. We show that the simple paths and simple cycles are the prime elements of the ensemble of all walks on G equipped with the nesting product. We give an algorithm producing the prime factorization of individual walks. We obtain a recursive formula producing the prime factorization of ensembles of walks. Our results have already found applications in the field of matrix computations. We give examples illustrating our results. |
| first_indexed | 2024-03-07T05:00:24Z |
| format | Journal article |
| id | oxford-uuid:d81312e6-ee10-402a-a6f4-cae77fcc3d25 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:00:24Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | oxford-uuid:d81312e6-ee10-402a-a6f4-cae77fcc3d252022-03-27T08:45:45ZContinued Fractions and Unique Factorization on DigraphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:d81312e6-ee10-402a-a6f4-cae77fcc3d25Symplectic Elements at Oxford2012Giscard, PThwaite, SJaksch, DWe show that the characteristic series of walks (paths) between any two vertices of any finite digraph or weighted digraph G is given by a universal continued fraction of finite depth involving the simple paths and simple cycles of G. A simple path is a walk forbidden to visit any vertex more than once. We obtain an explicit formula giving this continued fraction. Our results are based on an equivalent to the fundamental theorem of arithmetic: we demonstrate that arbitrary walks on G uniquely factorize into nesting products of simple paths and simple cycles. Nesting is a walk product which we define. We show that the simple paths and simple cycles are the prime elements of the ensemble of all walks on G equipped with the nesting product. We give an algorithm producing the prime factorization of individual walks. We obtain a recursive formula producing the prime factorization of ensembles of walks. Our results have already found applications in the field of matrix computations. We give examples illustrating our results. |
| spellingShingle | Giscard, P Thwaite, S Jaksch, D Continued Fractions and Unique Factorization on Digraphs |
| title | Continued Fractions and Unique Factorization on Digraphs |
| title_full | Continued Fractions and Unique Factorization on Digraphs |
| title_fullStr | Continued Fractions and Unique Factorization on Digraphs |
| title_full_unstemmed | Continued Fractions and Unique Factorization on Digraphs |
| title_short | Continued Fractions and Unique Factorization on Digraphs |
| title_sort | continued fractions and unique factorization on digraphs |
| work_keys_str_mv | AT giscardp continuedfractionsanduniquefactorizationondigraphs AT thwaites continuedfractionsanduniquefactorizationondigraphs AT jakschd continuedfractionsanduniquefactorizationondigraphs |