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)
What is a Hamiltonian graph?
A Hamiltonian graph is a graph which contains a Hamiltonian cycle.
What is a Hamiltonian cycle?
A Hamiltonian cycle is a cycle that passes through every vertex precisely once.
For any graph:
- The sum of all the degrees of all the vertices is double the number of edges.
- There is always an even number of odd vertices.
For any simple graph with n vertices:
- The graph can have at most ½n(n-1) edges.
- The degree of each vertex is at most n-1.
