Girth (graph Theory)
In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles (i.e. it's an acyclic graph), its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.
Read more about Girth (graph Theory): Cages, Girth and Graph Coloring, Related Concepts
Famous quotes containing the word girth:
“It is said that when manners are licentious, a revolution is always near: the virtue of woman being the main girth and bandage of society; because a man will not lay up an estate for children any longer than whilst he believes them to be his own.”
—Ralph Waldo Emerson (1803–1882)