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).
Euler’s formula
v - e + f = 2
or
F + V = E + 2
A subdivision of a graph is…
obtained by inserting a new vertex into an edge.
A bipartite graph contains…
two sets of vertices, with edges only joining a vertex in one set to a vertex in the other set.
Two graphs are isomorphic if…
one can be re-drawn in some way to match the other (i.e. distorted to produce the other).
Kuratowski’s theorem says…
that a graph is non-planar if and only if it contains a subgraph that is a subdivision of either K_3,3 or K_5
