1 Flashcards
Algorithm
A specific set of instructions for carrying out a procedure or solving a problem.
Graph
A graph consists of points (called vertices or nodes) which are connected by lines (called edges or arcs)
Weighted graph
If a graph has a number associated with each edge (usually called its weight), then the graph is known as a weighted graph or network.
Vertex set
The list of vertices or nodes
Edge set
The list of edges or arcs
Subgraphs
A subgraph is one where each of the vertices and edges in it belong to the original graph
Degree / valency
The valency of a vertex is the number of edges incident to it. A loop adds 2 to a valency. If you have odd valencies there will always be an even number of them.
Walk
A walk is a route through a graph along edges from one vertex to the next
Path
A path is a walk in which no vertex is visited more than once
Trail
A trail is a walk in which no edge is visited more than once
Cycle
A cycle is a walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once
Hamiltonian cycle
A Hamiltonian cycle is a cycle which includes every vertex
Connected graphs
A graph is connected if all its vertices have a path between them
Simple graph
A simple graph is one where there are no loops and there is at most one edge connecting any pair of vertices.
Directed graph
A directed graph is one in which the edges of the graph have a direction associated with them, the edges are known as directed edges. Directed graph is abbreviated to digraph.
