Graph Theory Flashcards
Connected graph
A graph where, for every pair of vertices, there is a way to get from one vertex to another
Multigraph
A graph in which at least one pair of vertices have multiple edges
Simple graph
A graph with no multiple edges or loops
Isomorphic graph
Can be made by moving vertices (without inserting or deleting edges)
Tree
A graph that is connected and has no circuits or cycles
Walk
A sequence of edges and vertices such that the finishing vertex of an edge becomes the starting vertex of the next edge
Path
A walk in which no edge is travelled more than once
Chain
A path such that no vertex is visited more than once
Hamiltonian circuit
A circuit that starts at a vertex of a graph, passed through every vertex exactly once and returns to the starting vertex
Eulerian path
A path that contains every edge of a connected graph exactly once
Eulerian circuit
An eulerian path starting and finishing at the same vertex
Planar graph
Can be drawn in the plane in such a way that no 2 edges meet each other except at a vertex
Weighted graph
Graph in which the edges are labelled with a weight
Directed graph
A graph in which a line from A to B is considered to be distinct from a line from B to A
Spanning tree
A tree that ensures a path exists between any 2 vertices
