Project Links Logo Artwork
Graph Theory: Industrial Drilling
Home > Graph Theory: Industrial Drilling > Foundations > Walks, Paths, Cycles
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

Walks, Paths, Cycles

A walk from vertex to a vertex is a sequence of alternating vertices and edges



Equation 6

such that

  1. , , and
  2. is incident with and .

A walk is called a path if it does not repeat any vertex.

A graph is called connected if, for any two vertices and of the graph, there is a walk from to .

A connected component is a maximal connected subgraph. A subset of vertices of a graph is a connected component if and only if:

  1. For any two vertices in , there is a path connecting them.
  2. Any vertex not in is not adjacent to any vertex in .

A closed walk is a walk whose first and last vertices are the same.

A cycle is a closed walk which does not repeat any vertex, except for the first and the last.

 
 
go backgo forward
go backgo forward