Graphs Flashcards
What is the degree of a vertex?
The number of edges coming out of the vertex.
A vertex with an even degree is called:
An even vertex.
A vertex with an odd degree is called:
An odd vertex.
Two graphs are isomorphic if:
There is a one-to-one correspondence between their vertices which preserves adjacency.
(They are the same graph, possibly laid out and/or labelled differently.
What is a walk?
A sequence of connecting edges in a given graph.
What is a trail?
A walk in which no edge is listed more than once.
What is a path?
A path is a walk in which no vertex is visited more than once.
What is a cycle?
A cycle is a path that finishes where it started.
What is a connected graph?
A connected graph is one in which there is a path between any pair of vertices.
(i.e. the graph is in one piece)
What is a simple graph?
A simple graph is one in which:
* No edge begins and ends at the same vertex.
(There are no loops).
* No two edges connect the same pair of vertices.
(There are no repeated edges).
What is a complete graph?
A complete graph is a simple, connected graph such that there is an edge between every pair of vertices.
We use the standard notation Kₙ for the complete graph with n vertices.
What is an Eulerian graph?
A Eulerian graph is a connected graph that has no odd vertices.
Eulerian graphs always contain an an Eulerian cycle/circuit.
What is an Eulerian cycle (or Eulerian circuit)?
A ‘cycle’ (possibly with repeated vertices) that includes every edge exactly once.
Eulerian graphs always contain an an Eulerian cycle/circuit.
What is a semi-Eulerian graph?
A semi-Eulerian graph is a connected graph with exactly two odd vertices.
For a semi-Eulerian graph, there will always exist a trail containing every edge exactly once, beginning at one of the odd vertices and ending at the other.
(Just need to know this)
