Keyterms Flashcards
Graph
Points (called vertices or nodes) connected by lines (edges or arcs)
Weighted graph or network
A graph that has a number associated with each edge (usually called its edge)
Subgraph
A graph, each of whose vertices belongs to the original graph and each of whose edges belongs to the original graph.
It is part of the original graph.
Degree (or valency or order) of a vertex
The number of edged that meet at that vertex
Even degree /odd degree
A degree of a vertex that is even / odd
Walk
A route through a graph along the edges from one vertex to the next
Path
A walk in which no vertex is visited more than once
Trail
A walk in which no edge is visited more than once
Hamiltonian cycle
A cycle that includes every vertex
Connected vertices/graph
Two vertices where there is a path between them/ all vertices are connected
Loop
An edge that starts and finishes at the same vertex
Simple graph
A graph in which there are no loops and there is at most one edge connecting any pair of vertices.
Directed edges
The edges of the graph that have a direction associated with them
Directed graph (or digraph)
A graph with directed edges
Tree
A connected graph with no cycles
Spanning tree
A subgraph which includes all vertices of the original graph and is also a tree
Complete graph
A graph in which every vertex is directly connected by a single edge to each of the other vertices
Isomorphic graphs
Graphs which show the same information but may be drawn differently
Adjacency matrix
A matrix in which each entry describes the number of arcs joining the corresponding vertices
Distance matrix
A matrix in which the entries represent the weight of each arc, not the number of arcs.
Minimum spanning tree (MST)
A spanning tree such that the total length of its arcs (edges) is as small as possible
Eulerian graph/network
Any connected graph whose vertices are all even
Eulerian circuit
A trail that includes every edge and starts and finishes at the same vertex.
Semi-eulerian graph
One which contains a trail that includes every edge but starts and finishes at different vertices
—> any connected graph with exactly 2 odd verices
Algorithm
A finite sequence of step-by-step instructions out to solve a problem
Flow chart
The shape of each box tells you about its function
