Chapter 2: Graphs and Networks Flashcards
What is a graph?
Consists of points (VERTICES/NODES) and the points are connected by lines (EDGES/ARCS)
A WEIGHTED GRAPH is a graph with numbers on each arc/edge
What is the degree/valency/order of a vertex?
The DEGREE/VALENCY/ORDER of a vertex is the number of edges connected to the vertice
An EVEN degree is when the degree/valency/order of a vertex is an even number
An ODD degree is when the degree/valency/order of a vertex in an odd number
What is a walk and what type of walks are there?
A WALK is a route through a graph along edges from one vertex to another
A PATH is a walk where no vertex is visited more than once
A TRAIL is a walk where no edge is visited more than once
A CYCLE is a walk in which the start vertex and end vertex are the same and no vertex is visited more than once (a path but start and end vertex are the same)
A HAMILTONIAN CYCLE is a cycle that includes every vertex
What is a connected graph?
A CONNECTED GRAPH is where all vertices are connected
What is a loop?
A LOOP is an edge that starts and ends at the same vertex
What does a simple graph consist of?
A SIMPLE GRAPH has no loops and there is at most one edge connecting a pair of vertices
What is Euler’s handshaking lemma?
In any undirected graph, the sum of the degrees/valencies/order of the vertices = 2 x the number of edges.
This means that the number of odd degree vertices must be even
What is a tree?
A TREE is a connected graph with no cycles
What is a spanning tree?
A SPANNING TREE is a tree and a subgraph that includes all vertices
What is a complete graph?
A graph in which each vertex is connected to each every other vertice.
The number of edges for kn= 1/29(n)(n-1)
What is an isomorphic graph?
A graph that shows the same information but is drawn in a different way
What is an adjacency matrix?
It can be used to represent a graph or network
It shows the number of edges joining together two vertices
What is a distance matrix?
It is used when associated with weighted graphs
It shows the weight of each arc
What is a planar graph?
A graph that can be drawn so that no edges cross over each other and the edges only meet at the vertices.
What is the planarity algorithm?
It can be applied to graphs that contain a HAMILTONIAN CYCLE.
1) Identify a hamiltonian cycle, then draw a polygon to represent the hamiltonian cycle (include edges that aren’t in the hamiltonian cycle but join the nodes together inside)
2) Make a list of all the edges inside the polygon
3) Choose any edge and label is I
4) Look at any unlabelled edged that cross the labelled edge/s, if there are none, choose and label another edge.
5) If any of the edges cross each other, the graph is NON-PLANAR
6) If none of the edges cross each other, label them O
7) Continue step 4 and onwards until all edges are labelled. If all edges are labelled, the graph is PLANAR
EASIER WAY:
Split arcs into either arcs crossing just inside and arcs crossing just inside.
If you can make the list, the graph is PLANAR
If a graph has to cross both an inside and outside plane, it is NON-PLANAR
