Graphs Flashcards
Vocabulary/language, Eulerian, Hamiltonian and planar graphs, Further graphs theory, Isomorphisms, and Kuratowski's theorem.
A graph consists of…
vertices and edges.
A path is…
a trail where no vertex is repeated.
A trail is…
a sequence of edges in which the end of one edge is the start of the next, and where no edge is repeated.
A cycle is…
a closed path.
A connected graph is…
where for each pair of vertices there exists at least one single path which joins them (i.e. every pair of vertices in the graph is connected).
A simple graph is…
one that has no multiple edges or loops.
A tree is…
a simple connected graph with no cycles.
The degree of a vertex is…
the number of edges that join it.
A graph is Eulerian if…
all vertices have even degree and it contains a closed trail that includes all the edges (i.e. you can start and finish at the same vertex whilst visiting each edge exactly once).
A graph is semi-Eulerian if…
all but two vertices have even degree and it contains an open trail that includes all the edges (i.e. you start and finish at different vertices whilst visiting each edge exactly once).
A graph is Hamiltonian if…
it contains a cycle that visits each vertex exactly once.
A graph is planar if…
it can be drawn in such a way that no edges cross each other (i.e. it can be drawn on the plane in such a way that its edges intersect only at their endpoints).
An adjacency matrix shows…
the number of edges connecting any two vertices.
A complete graph is…
one where every pair of vertices share exactly one edge, and there are no loops.
The complement of a simple graph is…
obtained by adding in the edges needed to make it a complete graph, and then removing the original edges (i.e. the complement is the ‘missing’ edges from the complete graph for that number of vertices).
