Graphs and networks Flashcards
What is a graph?
Points (vertices or nodes) which are connected by lines (edges or arcs).
If a graph has a number associated with each edge, then the graph is a weighted graph or network.
What is a subgraph?
A graph consisting of edges and nodes belonging to the original graph.
What is the degree/valency/order of a vertex?
The number of edges incident to it.
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 is a connected graph?
A graph in which all vertices are connected.
What is a loop?
An edge that starts and finishes at the same vertex.
What is a simple graph?
A graph in which there are no loops and at most one edge connecting any pair of vertices.
What is a digraph?
A graph in which edges 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 2 x the number of edges.
What is a tree?
A connected graph with no cycles.
What is a spanning tree?
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 are isomorphic graphs?
Graphs which show the same information drawn differently.
What do the numbers in adjacency matrices show?
The number of arcs joining the corresponding vertices. Put 0 where the headings are the same, unless there is a loop in which case you should put 2.
What do the numbers in a distance matrix show?
The weight of each arc between corresponding vertices. Put dashes through the leading diagonal.
What is a planar graph?
A graph that can be drawn in a plane such that no two edges meet except at a vertex.
How do you execute the planarity algorithm?
- identify a hamiltonian cycle
- draw a polygon with vertices labelled to match the ones in the hamiltonian cycle
- draw edges inside the polygon to match the edges of the original graph
- make a list of all the edges inside the polygon
- chose an unlabelled edge and label it I. If all edges are now labelled the graph is planar
- look at the unlabelled edges that cross the edge just labelled, if none of them cross each other give them all the opposite label. If any of these edges cross each other the graph is non planar.
