Metamath Proof Explorer


Table of Contents - 16.3.1. Walks

A "walk" within a graph is usually defined for simple graphs, multigraphs or even pseudographs as "alternating sequence of vertices and edges x0 , e1 , x1 , e2 , ... , e(l) , x(l) where e(i) = x(i-1)x(i), 0Bollobas] p. 4. This definition requires the edges to connect two vertices at most (loops are also allowed: if e(i) is a loop, then x(i-1) = x(i)). For hypergraphs containing hyperedges (i.e. edges connecting more than two vertices), however, a more general definition is needed. Two approaches for a definition applicable for arbitrary hypergraphs are used in the literature: "walks on the vertex level" and "walks on the edge level" (see Aksoy, Joslyn, Marrero, Praggastis, Purvine: "Hypernetwork science via high-order hypergraph walks", June 2020, https://doi.org/10.1140/epjds/s13688-020-00231-0):

"walks on the edge level": For a positive integer s, an s-walk of length k between hyperedges f and g is a sequence of hyperedges, f=e(0), e(1), ... , e(k)=g, where for j=1, ... , k, e(j-1) =/= e(j) and e(j-1) and e(j) have at least s vertices in common (according to Aksoy et al.).

"walks on the vertex level": For a positive integer s, an s-walk of length k between vertices a and b is a sequence of vertices, a=v(0), v(1), ... , v(k)=b, where for j=1, ... , k, v(j-1) and v(j) are connected by at least s edges (analogous to Aksoy et al.).

There are two imperfections for the definition for "walks on the edge level": one is that a walk of length 1 consists of two edges (or a walk of length 0 consists of one edge), whereas a walk of length 1 on the vertex level consists of two vertices and one edge (or a walk of length 0 consists of one vertex and no edge). The other is that edges, especially loops, can be traversed only once (and not repeatedly) because of the condition e(j-1) =/= e(j). The latter is avoided in the definition for , see df-ewlks. To be compatible with the (usual) definition of walks for pseudographs, walks also suitable for arbitrary hypergraphs are defined "on the vertex level" in the following as , see df-wlks, restricting s to 1. wlk1ewlk shows that such a 1-walk "on the vertex level" induces a 1-walk "on the edge level".

  1. cewlks
  2. cwlks
  3. cwlkson
  4. df-ewlks
  5. df-wlks
  6. df-wlkson
  7. ewlksfval
  8. isewlk
  9. ewlkprop
  10. ewlkinedg
  11. ewlkle
  12. upgrewlkle2
  13. wkslem1
  14. wkslem2
  15. wksfval
  16. iswlk
  17. wlkprop
  18. wlkv
  19. iswlkg
  20. wlkf
  21. wlkcl
  22. wlkp
  23. wlkpwrd
  24. wlklenvp1
  25. wksv
  26. wlkn0
  27. wlklenvm1
  28. ifpsnprss
  29. wlkvtxeledg
  30. wlkvtxiedg
  31. relwlk
  32. wlkvv
  33. wlkop
  34. wlkcpr
  35. wlk2f
  36. wlkcomp
  37. wlkcompim
  38. wlkelwrd
  39. wlkeq
  40. edginwlk
  41. upgredginwlk
  42. iedginwlk
  43. wlkl1loop
  44. wlk1walk
  45. wlk1ewlk
  46. upgriswlk
  47. upgrwlkedg
  48. upgrwlkcompim
  49. wlkvtxedg
  50. upgrwlkvtxedg
  51. uspgr2wlkeq
  52. uspgr2wlkeq2
  53. uspgr2wlkeqi
  54. umgrwlknloop
  55. wlkRes
  56. wlkv0
  57. g0wlk0
  58. 0wlk0
  59. wlk0prc
  60. wlklenvclwlk
  61. wlklenvclwlkOLD
  62. wlkson
  63. iswlkon
  64. wlkonprop
  65. wlkpvtx
  66. wlkepvtx
  67. wlkoniswlk
  68. wlkonwlk
  69. wlkonwlk1l
  70. wlksoneq1eq2
  71. wlkonl1iedg
  72. wlkon2n0
  73. 2wlklem
  74. upgr2wlk
  75. wlkreslem
  76. wlkres
  77. redwlklem
  78. redwlk
  79. wlkp1lem1
  80. wlkp1lem2
  81. wlkp1lem3
  82. wlkp1lem4
  83. wlkp1lem5
  84. wlkp1lem6
  85. wlkp1lem7
  86. wlkp1lem8
  87. wlkp1
  88. wlkdlem1
  89. wlkdlem2
  90. wlkdlem3
  91. wlkdlem4
  92. wlkd