Metamath Proof Explorer


Table of Contents - 17.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. wksvOLD
  27. wlkn0
  28. wlklenvm1
  29. ifpsnprss
  30. wlkvtxeledg
  31. wlkvtxiedg
  32. relwlk
  33. wlkvv
  34. wlkop
  35. wlkcpr
  36. wlk2f
  37. wlkcomp
  38. wlkcompim
  39. wlkelwrd
  40. wlkeq
  41. edginwlk
  42. upgredginwlk
  43. iedginwlk
  44. wlkl1loop
  45. wlk1walk
  46. wlk1ewlk
  47. upgriswlk
  48. upgrwlkedg
  49. upgrwlkcompim
  50. wlkvtxedg
  51. upgrwlkvtxedg
  52. uspgr2wlkeq
  53. uspgr2wlkeq2
  54. uspgr2wlkeqi
  55. umgrwlknloop
  56. wlkResOLD
  57. wlkv0
  58. g0wlk0
  59. 0wlk0
  60. wlk0prc
  61. wlklenvclwlk
  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