Graphs and networks Flashcards
What is a graph?
A collection of vertices and edges
What is a vertex/node?
A point on a graph
What is an edge/arc?
A line connecting two points on a graph
What is a network?
A graph in which the edges have a weight (e.g. distance) associated with it
What is a subgraph?
A graph in which all vertices and edges are also present in another larger graph
What is the degree/valency/order of a vertex?
The number of edges incident to it
What is a path?
A finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once
What is a walk?
A path in which it is permitted to return to vertices more than once
What is a cycle/circuit?
A closed path, i.e. the end vertex of the last edge is the start vertex of the first edge
What does it mean for two vertices to be connected?
There exists a path between them
What is a connected graph?
A graph in which all vertices are connected to each other
What is a loop?
An edge that starts and finishes at the same vertex
What is a simple graph?
A graph which has no loops and no pair of vertices being joined by more than one edge
What is a digraph?
A graph in which the edges have a direction associated with them
What is a tree?
A connected graph with no cycles
What is a spanning tree?
A subgraph that is a tree and also contains all the vertices of the original graph
What is a bipartite graph?
A graph consisting of two sets of vertices, X and Y. The edges only go between a vertex in X and a vertex in Y
What is a complete graph?
A graph in which every vertex is directly joined to every other vertex
How is a complete graph notated?
Kᵥ, where v is the number of vertices
What is a complete bipartite graph?
A bipartite graph in which each vertex in one set is directly joined to every vertex in the other set
How is a complete bipartite graph notated?
Kᵢ,ⱼ, where i is the number of vertices in set X and j is the number of vertices in set Y
What is graph isomorphism?
The property of two graphs having a difference appearance but still showing the same information
What is an adjacency matrix?
A matrix that records the number of edges linking vertices
What is a distance matrix?
A matrix that records the distances between vertices
In adjacency and distance matrices, which out of the row and the column represents the vertex that the edge is going from, and which represents the vertex that the edge is going to?
The row represents the vertex that the edge is going from, and the column represents the vertex that the edge is going to
