D1 Flashcards
(38 cards)
Definition: Loop
When an edge has the same vertex at each end.
Definition: Degree of a vertex
The number of edges incident on the vertex.
Definition: Walk
A sequence of edges.
Definition: Trial
A sequence of edges in which no edge is repeated.
Definition: Path
A sequence of edges in which no edges or vertices are repeated.
Definition: Cycle
A closed sequence of edges in which no edges or vertices are repeated.
Definition: Hamiltonian cycle
A cycle which visits every vertex.
Definition: Simple graph
A graph with no loops where there is no more than one edge connecting any pair of vertices.
Definition: Connected graph
When a path exists between every pair of vertices.
Definition: Disconnected graph
When vertices are connected by different paths.
Definition: Tree
A simple connected graph with no cycles.
What are the features of a tree?
✔️ Path between every pair of vertices.
✖️ No loops.
✖️ No cycles.
✖️ No more than one edge connecting any two vertices.
Definition: Digraph
Where at least one edge has a direction (shown by an arrow).
Definition: Complete graph
A simple graph where every pair of vertices are connected by an edge.
Definition: Isomorphic
When one graph can be stretched or twisted into another.
Definition: Planar graph
A graph which can be drawn without any edges crossing.
Definition: Bipartide graph
Vertices fall into two sets, where an edge has a vertex from both sets.
Definition: Eulerian
A graph which can be drawn continuously starting at any vertex and finishing at the same point.
Definition: Semi-Eulerian
A graph that can be drawn continuously but only starting at certain vertices.
Definition: Non-Eulerian
A graph which cannot be drawn continuously.
Process: Linear programming
1) Define specific variables.
2) Write down all of the constraints.
3) Record points of intersection with axes for each constraint (to help draw graph).
4) Draw graph and shade out regions.
5) Label vertices of the feasible region .
6) Define objective function.
7) Test objective region for each vertex if feasible region. However:
• you may need to find integer co-ordinates for some questions.
• you may need to find the co-ordinates of some vertices by using simultaneous equations.
8) Write a conclusion stating the optimal function, which relates to the question.
Process: Kruskal’s Algorithm
1) List all of the paths from shortest to longest.
2) Select the shortest path in a network and record in a second list (A -> B 25)
3) Select the next shortest edge which doesn’t create a cycle, but still make a note of any cycles in your second list (C -> D Cycle)
4) Repeat the process until all vertices have been connected.
Process: Prim’s Algorithm
1) Select any vertex.
2) Select the shortest edge connected to that vertex and record in a list (A -> D 13)
3) Select the shortest edge connected to any of the connected vertices and record in the list (D -> G 12)
4) Repeat until all vertices are connected.
Process: Prim’s Algorithm (tables)
1) Cross out the first row.
2) Select the smallest value from the first column and circle.
3) Cross out the row containing the value which you have just selected.
4) Select the smallest value from all columns which correspond to crossed out rows.
5) Return to step 3.