2 - Graphs and networks Flashcards
Define a walk.
A route through a graph along edges from one vertex to the next.
Define a path.
A walk in which no vertex is visited more than once.
Define a trail.
A walk in which no edge is visited more than once.
Define 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.
Define a Hamiltonian cycle.
A cycle that includes every vertex.
Define a simple graph.
A graph in which there are no loops and there is at most one edge connecting any pair of vertices.
What is Euler’s handshaking lemma?
In an undirected graph, the sum of degrees of vertices is 2x the number of edges. So the number of odd vertices must be even.
What is a tree?
A connected graph with no cycles.
What is a spanning tree?
A subgraph which includes all vertices and is a tree.
What is a complete graph?
A graph in which every vertex is directly connected by a single arc to every other vertex.
What are isomorphic graphs?
Graphs which are drawn differently, but contain the same information. (edges and arcs)
Define a planar graph.
A graph which can be drawn in a way such that no two edges meet except at a vertex. (no edges cross)
Describe the planarity algorithm.
- Identify Hamiltonian cycle
- Draw a polygon with vertices labelled as in Hamiltonian cycle
- Draw arcs inside polygon as in original graph (excluding ones done by edges of polygon)
- Make a list of all edges inside polygon
- Choose an unlablled edge and label it I
- Look at unlabelled edges which cross edge in Step 5
* If there are none, go back to Step 5
* If any of these cross each other, the graph is non-planar
* If none do, label them the opposite to the prior labelled graph (O in the first case)
* If all edges are now labelled, the graph is planar, else go back to Step 5.
