Definitions

Graph theory, the study of points (nodes) and the lines connecting them (edges), serves as a powerful mathematical language for modeling complex systems in mechanical engineering. While traditionally associated with computer science, its ability to represent structural relationships makes it indispensable for managing the intricate interdependencies found in modern engineering environments.

Some examples:

  • production and manufacturing systems: In production, graph theory is used to optimize the flow of materials and assembly sequences. By representing a factory floor as a directed graph, engineers can identify bottlenecks, minimize travel distances for automated guided vehicles, and balance assembly lines.

  • organization: beyond the physical hardware, graph theory is a cornerstone of industrial organization. In project management, some dedicated charts use graphs to map out project tasks. This allows engineers to identify the critical path (the sequence of stages determining the minimum time needed for project completion).

  • In structural engineering, graphs aid in the automated generation of stiffness matrices for finite element analysis. Similarly, in hydraulic systems, graph theory helps solve for pressure drops and flow rates across complex piping networks.

In this course, a more playful approach is often taken in problem formulations. However, keep in mind that graphs are very common, concrete and powerful tools in engineering, finance, economics etc

The next sections are partially inspired by [Het14]. To dive deeper, python algorithms can be found online.

  • nodes: usually are/contain a label, can represent a state.

  • directed/undirected: respectively, bi-directional or directional connections between nodes.

  • edges: connections between nodes can be either incoming or outgoing.

  • cyclic/acyclic: denotes the presence or absence of cycles / loops in a graph.

  • weights: usually a float number associated to an edge, can represent a cost, a time, a reward etc depending on the context.

Exercise (easy)

What python structure would you use to represent a weighted directed graph?

Correction

dict[Node, dict[Node, Weight]] with Node being hashable.

Exercise (easy)

Create a function which transposes a directed weighted graph: inverting every edge. Test it.

Correction
src
1def transpose(graph: DirectedWeightedGraph) -> DirectedWeightedGraph:
2    transposed: DirectedWeightedGraph = {node: dict() for node in graph.keys()}
3    for parent, children_and_weights in graph.items():
4        for child, weight in children_and_weights.items():
5            transposed[child][parent] = weight
6    return transposed
tests
1@pytest.fixture
2def simplest_graph() -> DirectedWeightedGraph:
3    return {
4        "a": {"b": 2.0, "c": 5.0},
5        "b": {"d": 1.0},
6        "c": {},
7        "d": {"a": 6.0},
8    }
tests
1def test_transpose_simplest(simplest_graph: DirectedWeightedGraph):
2    expected: DirectedWeightedGraph = {
3        "a": {"d": 6.0},
4        "b": {"a": 2.0},
5        "c": {"a": 5.0},
6        "d": {"b": 1.0},
7    }
8    assert expected == transpose(simplest_graph)