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. 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. wlkv0
  56. g0wlk0
  57. 0wlk0
  58. wlk0prc
  59. wlklenvclwlk
  60. wlkson
  61. iswlkon
  62. wlkonprop
  63. wlkpvtx
  64. wlkepvtx
  65. wlkoniswlk
  66. wlkonwlk
  67. wlkonwlk1l
  68. wlksoneq1eq2
  69. wlkonl1iedg
  70. wlkon2n0
  71. 2wlklem
  72. upgr2wlk
  73. wlkreslem
  74. wlkres
  75. redwlklem
  76. redwlk
  77. wlkp1lem1
  78. wlkp1lem2
  79. wlkp1lem3
  80. wlkp1lem4
  81. wlkp1lem5
  82. wlkp1lem6
  83. wlkp1lem7
  84. wlkp1lem8
  85. wlkp1
  86. wlkdlem1
  87. wlkdlem2
  88. wlkdlem3
  89. wlkdlem4
  90. wlkd