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.
Loop
A loop is an edge which starts and finishes at the same vertex
The handshake lemma
In any undirected graph, the sum of the degrees of the vertices is equal to 2x the number of edges, as a consequence, the number of odd vertices must be even.
Tree
A tree is a connected graph with no cycles
Spanning tree
A spanning tree is a subgraph, which includes all the vertices and is a tree
Complete graphs
A complete graph is a graph in which every vertex is directly connected by a single edge to each of the other vertices. No. Edges: VERTEXn = n(n-1)/2
