Graphs Flashcards
What are the dots called?
Vertices or Nodes
What are the lines called?
Edges or Arcs
What is a simple graph
No loops and there is no more than one edge connecting any pair of vertices
What is a complete graph?
A graph in which every vertex is connected to every other vertex
What is a walk?
A sequence of edges in which the end of one edge (except the last) is the beginning of the next
What is a trail?
A walk in which no edge is repeated
What is a path?
A trail such that no vertex is visited more than once (except that the first vertex may also be the last)
What is a cycle?
A closed path Eg. The end of the last edge is the start vertex of the next
What is a hamiltonian cycle?
A cycle which visits every vertex once and only once
What is a traversable graph?
One that can be drawn without taking a pencil from the paper and without retracing the same edge
What is a Eulerian graph?
A graph which can be traversed by starting and finishing at the same node, without retracing an edge
What is a semi-Eulerian graph?
A graph where you start at a node, traverse each edge exactly once and end up somewhere different to the starting point
What is a bipartite graph?
A graph consisting of two sets of vertices. The edges only join vertices in X to vertices in Y.
What is a connected graph?
A graph in which every vertex is joined directly or indirectly to every other vertex
What is a tree?
A connected graph with no cycles
