Decision C2 - Graphs and networks Flashcards
What is a graph?
A graph consists of points which are connected by lines
What are points also referred to as?
Vertices or nodes
What are lines also referred to as?
Edges or arcs
What is a weighted graph?
A graph with a number associate with each edge (it’s weight)
What is a weighted graph also known as?
A network
What is a subgraph?
A graph each of whose vertices and edges belong to the original graph. It is part of the original graph
What is the degree of a vertex?
The number of edges incident to it
What is the degree of a vertex also known as?
Valency or order
What is a walk?
A route through a graph along edges from one vertex to the next
What is a path?
A walk in which no vertex is visited more than once
What is a trail?
A walk in which no edge is visited more than once
What is a cycle?
A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once
What is a hamiltonian cycle?
A cycle that includes every vertex
What makes two vertices connected?
If there is a path between them
What makes a graph connected?
If all it’s vertices are connected
What is a loop?
An edge that starts and finishes at the same vertex
What is a simple graph?
A graph with no loops and at most one edge connecting any pair of vertices
What are directed graphs also known as?
Digraph
What makes a graph a directed graph?
If they have a direction associated with them
What is Euler’s handshaking lemma?
In any undirected graph, the sum of the degrees of the vertices is equal to 2x the number of edges. As a result, the number of odd nodes must be even
What is a tree?
A connected graph with no cycles
What is a spanning tree of a graph?
A subgraph which includes all the vertices of the original graph and is also a tree
What is a complete graph?
A graph in which every vertex is directly connected by a single edge to each of the other vertices
What is an isomorphic graph?
Graphs which show the same information but mat be drawn differently
Describe an adjacency matrix
Each entry in an adjacency matrix describes the number of arcs joining the corresponding vertices
Describe a distance matrix
Each entry represents the weight of each arc, not the number of arcs
What is a planar graph?
One that can be drawn such that no 2 edges meet except at a vertex
When is it appropriate to use the planarity algorithm?
When it contains a hamiltonian cycle
