Terminology Flashcards
A tree
A connected graph with no cycles e.g. Probability tree
A spanning tree
A subgraph that includes all the vertices of the graph and is also a tree
A complete graph Kn
Has n vertices where all the vertices are connected by an edge to each of the other vertices
A bipartite graph
Two sets of vertices (X and Y) where edges only join vertices in X to Y, not within their set
A planar graph
A graph which can be drawn in a plane so that no two edges meet each other, except at a vertex to which they are both incident
Isomorphic
If two graphs have the same number of vertices and the degrees of the corresponding vertices are the same
Network
A graph with weighted edges
Triangle inequality
If weight BC is less than or equal to weight AB + AC for all sets of three vertices (ABC) then it satisfies this
Path
A finite sequence of edges such that the end vertex of one edge is the start vertex of the next. No vertex appears more than once
Cycle
A closed path, the end vertex of the last edge is the start vertex of the first edge
Hamiltonian cycle
A cycle that passes through every vertex of the graph once and only once, and returns to its start vertex
Eulerian cycle
A cycle that includes every edge of a graph exactly once
Edge set
Set of all edges
Vertex set
Set of all vertices
Graph
A collection of nodes (or vertices) which are connected by arcs (or edges)
Subgraph
A subset of the vertices together with a subset of the edges
Two connected vertices
Two vertices with a path inbetween them
Connected graph
All of the vertices are connected
Loop
An edge with the same vertex at each end
Simple graph
Does not contain any ‘parallel’ arcs nor any loops
Degree (or valency or order) of a vertex
The number of edges connected to it
Directed edges
The edges of a graph have a direction associated with them
Digraph
When the edges of a graph have a direction associated with them
Kr,s
Bipartite graph where every vertex in x is joined to every vertex in y and vice versa
