Graphs and Networks Terminology Flashcards
Subgraph
A part of the original graph.
Degree/Valency/Order
he number of arcs incident to a vertex/node.
Path
A finite sequence of edges such that the end vertex of one edge is the start of the next. No vertex appears more than once.
Walk
A path which you are permitted to return to vertices more than once.
Cycle
A closed path where the end vertex of the last edge is the start vertex of the first edge.
Connected Graph
A graph where all vertices are connected.
Simple Graph
Has no loop and has no more than one edge connecting each pair of vertices.
Loop
Starts and finishes at the same vertex.
Digraph
The edges have a direction associated to it.
Adjacency matrix
Records the number of direct links between vertices.
Distance matrix
Records the weights on the edges. Where there is no edge, we write “-“.
A Tree
A connected graph with no cycles.
A spanning tree
A subgraph that is a tree and includes all vertices.
Bipartite graph
Two sets of verticies, X and Y. The edges only join vertices in X to vertices in Y, not to any vertices within another set.
Complete graph
Every vertex is directly connected by an edge to each of the other vertices. Denoted by K_n.
