Please enable JavaScript.
Coggle requires JavaScript to display documents.
Discrete Mathematical Modeling - Coggle Diagram
Discrete Mathematical Modeling
Graph
Unordered pairs of edges
Complete Graph
\(\exists\) edges \(\forall\) vertices
\(\frac{n(n-1)}{2}\) edges for 'n' vertices
In a complete graph, there exists
\((n-1)!\) Hamiltonian cycles for 'n' vertices
Hamiltonian Path
Path
passing through each vertex exactly once
Hamiltonian Cycle
Closed loop
passing through each vertex exactly once
Cycle
Starts and ends at the same point
No repeating edges
Eulerian Circuit
Crosses every edge exactly once
Circuit
Starts and ends at the same point
Tree
Connected
graph without cycle
Spanning Tree
A tree
Contains all vertices
Network
A Graph or Digraph, yet "weight" (or cost) is assigned to each edges
Traveling Salesman Problem (TSP)
Visit n vertices, cheapest way possible, and return to starting point
Algorithms
Greedy Algorithm
Choose the best path at the moment
Relatively fast
Does not guarantee to find the optimal solution
Branch and Bound Algorithm
Similar to Brute Force, yet if cost exceeds the baseline while searching for the path, the search ends early for the path
Brute Force Algorithm
Try every possible path
Guaranteed to find the best solution
Computationally intensive/not practical
Dijkstra's Algorithm
Least-cost path between two vertices in a
weighted graph
Need hands on practice
Minimum Spanning Tree
Find a minimum spanning tree in a weighted graph
Algorithms
Prim's Algorithm
Choose a vertex and minimum cost edge
\(O(E + Vln(V))\)
Kruskal's Algorithm
Sort edges by weight
Include edges, in order, that doesn't create cycle
\(O(E ln(V))\)
Digraph
Edges are ordered pairs (has direction)
Activity Digraph
Each node is assigned duration
Edges are weighted by the duration of origin
Critical Path
Path(s) that are made up of vertices with same earliest and latest start time
Earliest Start Time
: \(e(V) = max[w(X) + e(X)] \forall X \in V_{preds}\)
Latest Start Time
: \(l(V) = min[l(Y) - w(V)] \forall Y \in V_{succs}\)
Multigraph
Graph with more than one edge between vertices
Eulerian Circuit Algorithm
Find eulerian circuit from given graph
Find local circuit
Glue all local circuits together
Planar Graph
None of the edges intersect
Euler Characteristics
\(V - E + F = 2\)
V
: # of vertices
E
: # of edges
F
: # of faces (including outside)