Key Terms Flashcards
GRAPH
a finite number of vertices/nodes connected by edges/arcs
PATH
a finite sequence of edges such that the end vertex of one edge is the start vertex of the next, and in which no vertex appears more than once
WALK
path in which you are permitted to return to vertices more than once
CYCLE
a closed path ie. the end vertex of the last edge is the start vertex of the first edge (starts and finishes in the same place)
SUBGRAPH
a subset of the vertices together with a subset of the edges
CONNECTED GRAPH
all vertices on the graph are connected by a path
SIMPLE GRAPH
a graph in which there are no loops and not more than one edge connecting any pair of vertices
VALENCY/DEGREE/ORDER
number of edges connected to a vertex
ODD VERTEX
vertex with an odd valency
EVEN VERTEX
vertex with an even valency
DIGRAPH
a graph in which the edges are directed (have directions associated with them)
TREE
a connected graph with no cycles
SPANNING TREE
a subgraph of a graph, that includes all the vertices of the original and is also a tree
COMPLETE GRAPH
every vertex is connected by a edge to every other vertex (Kn denoted a complete graph with n vertices)
BIPARTITE GRAPH
consist of two sets of vertices, X and Y
the edges only join vertices is X to vertices in Y, not vertices within a set
Kr.s denotes a complete bipartite graph with r vertices in X, and s vertices in Y
