Chapter 2 Graphs and Networks Flashcards
What is a graph?
A graph consists of points (called vertices or nodes) which are connected by lines (edges or arcs)
What is a graph where each edge has a numbers associated with it called?
Weighted graph or a Network
What is a weighted graph/network?
A graph withy numbers associated with each edge
In a weighted graph, what are the numbers usually called?
Its weight
What is a vertex?
A point in the graph
What are vertices sometimes called?
Nodes
What is an edge?
A line segment joining vertices
What is the other word for edge?
Arc
What do you need to be careful about with networks?
They aren’t usually drawn to scale
As a result the shortest path may not be the obvious path
That is the list of vertices called?
Vertex set
What is the list of edges called?
The edge set
What is the vertex set?
The list of vertices
What is the edge set?
The list of edges
What is a subgraph?
A subgraph is part of the original graph
When is a vertex and an edge incident?
If they are connected
What is the degree of a vertex?
The number of edges incident to a particular vertex
What are the other ways to say degree of a vertex?
Valency of a vertex
Order of a vertex
What does even degree mean?
The vertex has an even number of incident edges
The degree of vertex will be an even number
What deos odd degree mean?
The vertex has an odd number of incident edges
The degree of vertex will be an odd number
What phrase can be used to say: The vertex has an even number of incident edges?
Even degree
What phrase can be used to say: The vertex has an odd number of incident edges?
Odd degree
What is a walk?
A walk is a route through a graph along edges from 1 vertex to the next
What is a path?
A path is a walk in which no vertex is visited more than once
What is a trail?
A trail is a walk in which no edge is visited more than once
What is a cycle?
A cycle is a path in which the end vertex is the same as the start vertex
What is a hamiltonian cycle?
A hamiltonian cycle is a cycle that includes every vertex
What is the difference between a path and a trail?
A path doesn’t visit any node more than once
A trail doesn’t visit any edge more than once
What does it mean if 2 vertices are connected?
2 vertices are connected if there is a path between them
What does it mean if a graph is connected?
A graph is connected if there is at least 1 path joining any 2 vertices in the graph
What is a loop?
A loop is an edge that starts and finishes at the same vertex
What is a simple graph?
A simple graph is a graph in which there are no loops and there is at most 1 edge connecting any pair of vertices
What is a directed graph?
What is it often abbreviated to?
A graph in which the edges have a direction associated with them
Digraph
What do you know about degrees of vertices in a undirected graph?
The sum of the degrees of the vertices = 2 x the number of edges
What do you know about the number of odd vertices?
What is this result known as?
There must be an even amount of odd vertices
This result is known as Euler’s handshaking lemma
What is a lemma?
A lemma is a mathematical fact used as a stepping stone to more important results
What are the special graphs that you need to know?
A tree
A spanning tree
A complete graph
Isomorphic graphs
What is a tree?
A tree is a connected graph with no cycles
What is a spanning tree?
A spanning tree of a graph, G, is a subgraph which includes all the vertices of G and is also a tree
What is a complete graph?
A complete graph is a graph in which every vertex is directly connected by a single edge to each other vertices
What is an isomorphic graph?
Isomorphic graphs are graphs which show the same information but may be drawn differently
What is the special notation for complete graphs?
What do you know must be true for isomorphic graphs?
They must have the same number of vertices of the same degrees
These vertices must also be connected together in the same way
What can you use to represent graphs and networks?
Adjacent matrices
What does an adjacent matrix do?
Provided information about the connections between the vertices in a graph
If you have a adjacent matrix which has all 0s in its leading diagonal what do you know is true?
There are no loops
If you have a adjacent matrix which has a number greater than 1 what do you know is true?
Those 2 points share more than 1 arc between them
What is a matrix associated with a weight graph called?
A distance matrix
When do you use a distance matrix?
When you have a network
What do you know about a distance matrix of a non directed network?
It will be symmetrical around the matrices leading diagonal
What do you do in the distance matrix if there is no edge between 2 vertices?
You put a dash
What is a planar graph?
A planar graph is a graph that can be drawn in a place such that no 2 edges meet except at a vertex
Give an example of a planar graph?
What fact does the planetary algorithm rely on?
That there is a hamiltonian cycle
State the planetary algorithm
What really helps when implementing the planetary algorithm?
Draw a regular polygon
How does the planetary algorithm generally work?
Generally this works by: if edges crosses inside the hamiltonian cycle then they will both cross outside it. So the algorithm tries to separate all edges into a category that the cross or they don’t. Therefore 1 of each pair can be directed outside the nodes
What does a completed planetary algorithm question look like?
A completed answer should be the table of edges
You only draw the isomorphic graph is asked
What will stop the planetary algorithm?
There not being a hamiltonian cycle
There being 2 outside edges crossing
What happens if there ate 2 outside edges crossing?
Why?
The graph isn’t planar
For there to be 2 outside edges crossing then if they are inside they will cross an inside edge by definition. So there is no possible solution
What happens for the simplex algorithm if there isn’t a hamiltonian cycle?
The algorithm is inconclusive
