Decision - 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 are points on a graph called?
Vertices or nodes
What are lines on a graph called?
Edges or arcs
What is a weighted graph?
A graph that has a number associated with each edge (usually known as its weight)
What is a network?
A weighted graph
How are 2 vertices connected?
If there is a path between them
What is a connected graph?
A graph where all its vertices are connected
What is a simple graph?
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?
A graph in which the edges of the graph have a direction associated with them, the edges are known as directed edges.
What is directed graph abbreviated to?
Digraph
What are all the vertices, or nodes, in a graph called?
The vertex set
What are all the edges, or arcs, in a graph called?
The edge set
What is a subgraph?
A subgraph of G is a graph, whos vertices belong to graph G and edges belong to G. It is simply a part of the original graph
What is the degree of a vertex?
The number of edges incident to it
What is the valency of a vertex?
The degree of a vertex
What is an even vertex?
A vertex with an even degree/valency
What is an odd vertex?
A vertex with an odd degree/valency
What is a loop?
An edge where the start vertex and end vertex are the same
What does a loop add to the valency?
2
What is the rule with odd vertex’s?
If you have odd vertex’s, you will always have an even number of them
What is a walk?
A walk is a route through a graph along edges from one vertex to the next
What is a path?
A path is a finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next. No vertices can appear 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 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 Hamiltonian cycle is a cycle which includes every vertex
What is the handshake lemma?
In any undirected graph, the sum of the degrees of the vertices is equal to 2 x the number of edges, as a result, the number of odd vertices must be even
Why must the number of odd vertices be even?
The handshake lemma
What is the order of a graph?
the degree or valency
What is a circuit?
A walk in which the start vertex and end vertex are the same
What is a tree?
A connected graph with no cycles
What is a spanning tree?
A spanning tree is a subgraph, which includes all of the vertices and is 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 of the other vertices
What is the formula for the number of sides of the completed graph Kₙ?
0.5n(n-1)
What is an algorithm?
A set of instructions which are followed to achieve a task
What is the meaning of this shape in a flow chart?
Start/End
What is the meaning of this shape in a flow chart?
A command to follow
What is the meaning of this shape in a flow chart?
A decision/question
What is a planar graph?
A planar graph is a graph which can be drawn in a plane such that no two edges meet except for at a vertex
What is 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 not already represented
- Make a list of all the edges “inside” the polygon
- Choose any unlabelled edge in your list and label it “I” for inside. If all edges are now labelled then the graph is planar
- Look at any unlabelled eges that cross the edge(s) just labelled:
* If there are none then go back to step 5
* If any of these edges cross each other then the graph is non-planar
* If none of these edges cross each other, give them the opposite label the edge just labelled (“I” for inside or “O” for outside)
* If all edges are now labelled, the graph is planar. Otherwise, go back to step 6.
