2. Graphs and Networks Flashcards
What does a graph consist of?
Points called vertices or nodes
Lines called edges or arcs
What is a weighted graph or network?
A graph that has a number associated with each edge (usually known as weight)
What is a subgraph?
A part of the original graph
What is the degree of a vertex also known as?
- Order
2. Valency
What is the degree of a vertex?
The number of edges incident to it
Define the term walk
A route through a graph along edges from one vertex to the next
Define the term path
A walk in which no vertex is visited more than once
Define the term trail
A walk in which no edge is visited more than once
Define the term 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 where all vertices are connected
Define the term loop
An edge that starts and finishes at the same vertex
What is a simple graph?
A graph that has no loops and only one edge connecting any pair of vertices
What is a directed graph (digraph)?
A graph which has directed edges (edges that have a direction associated with them)
What is the relationship between the sum of the degrees of the vertices and the number of edges in an undirected graph?
sum of degrees of vertices = 2 x number of edges
This means the number of odd vertices must be even
What is Euler’s handshaking lemma?
sum of degrees of vertices = 2 x number of edges
Define the term tree
A connected graph with no cycles
What is the spanning tree of a graph?
A subgraph including all of 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 to every other vertex with a single edge
What are isomorphic graphs?
Graphs that show the same information but may be drawn differently
What does each entry in an adjacency matrix show?
The number of arcs joining corresponding vertices
What does each entry in a distance matrix show?
The weight of each arc
What is a planar graph?
A graph that can be drawn with no two edges crossing each other
What are the steps to the planarity algorithm?
- Identify a Hamiltonian cycle
- Draw polygon with vertices labelled to match the ones in the Hamiltonian cycle
- Draw edges inside polygon to match ones in original graph not already represented by polygon itself
- Make list of all edges inside polygon, in any order
- Choose any unlabelled edge and call it ‘I’ If all edges are labelled, the graph is planar
- Look at all unlabelled edges that cross edge(s) just labelled
- If there are none, go back to step 5
- If any of these edges cross each other, the graph is non-planar
- If none of these edges cross each other, give them the opposite label (‘I’ and ‘O’ are opposites)
- If all edges are now labelled, the graph is planar. Otherwise go back to step 6
