Remember to register **here** for FREE to ask any questions you may come across in your QCE studies!Terminology can easily get the better of you in the graph theory/networks topics. The concepts may be solid to grasp, but I dare say it's easy to forget it all! So it may be easier to have all of those compiled together to help revise over them.

*Please don't become reliant on this because you won't have it in the exam... it's your task to get used to seeing them all the time!**Basics*- The

**graph**/

**network** is the actual structure you're studying! In this course, you should be safe treating them synonymously.

- A

**vertex** (sometimes called a node) is a point on the graph. Usually it is labelled.

- An

**edge** on a graph joins two of its vertices together.

- A

**loop** is an edge that joins a vertex back to itself. It's essentially an edge whose endpoints are the same vertex!

- The

**degree** of a vertex is the number of edges incident on the vertex (i.e. end on the vertex).

**Always remember that loops add 2 to the degree!** - One way I think about the degree is that it counts the number of ways you can "leave" a certain vertex. I always imagine that when we have a loop, we can leave the vertex by going along one end of the loop, and then the other. That way I never forget to address loops separately! (You don't have to do this if you hate this analogy though of course

)

- If you already have a graph, a

**subgraph** is nothing more than a (usually smaller) graph that's contained within it! You can get a subgraph by removing vertices, or edges, or both from your graph.

*Some special graphs*- A

**simple graph** is characterised by the

**absence** of:

- Loops

- Any situation where two vertices are connected by

**more** than one edge

- Given \(n\) vertices, the

**complete graph** on \(n\) vertices is a special simple graph, in which each vertex is connected to

**every other vertex** by an edge. (Of course, because it is a simple graph, there will only be one edge joining each pair of vertices!)

- A

**bipartite** graph is hard to define (feels bad man). Essentially, the vertices of the graph can be split into two groups. The key property is that vertices in the same group can never be joined among each other by an edge. They can only be joined to vertices in the other group.

- A

**directed graph** is one in which each edge has a direction, usually denoted by an arrow on the edge. The assumption is that we can only go from a vertex \(A\) to another vertex \(B\), if an edge

*from \(A\) to \(B\)* exists.

- A

**weighted graph** is one in which each edge is assigned a number to (i.e. its weight).

*Planar graphs*- A

**planar graph** is one in which if we somehow rearrange the vertices and edges of the graph, we can get it so that no edges will cross over each other. (Sometimes we don't need to rearrange them - the edges may already not overlap.)

- When drawn so that there are no overlapping edges, a

**face** of a planar graph is essentially one of the regions cut by the edges in the graph.

*Always remember that there's always at least one face - the 'outside' region is also a face of the graph!*- Euler's formula states that \( v + f - e = 2\) (but it is given on the formula sheet - yay!)

*Paths and cycles*- A

**walk** is a sequence of edges from one vertex to another.

- A

**trail** is a walk with no repeated edges.

- A

**path** is a walk with no repeated vertices and edges. (i.e. it is a trail with no repeated vertices)

- An

**open walk** is one where the initial and final vertices of the walk are NOT the same.

- An open trail is an open walk that is also a trail.

- An open path is an open walk that is also a path.

- A

**closed** walk is one where the initial and final vertices of the walk are the same.

- A closed trail is a closed walk that is also a trail.

- A

**cycle** is similar to a path in that it has no repeated edges, and passes through different vertices, but ends back on the same vertex. Essentially, only two vertices can be the same in a cycle, namely the initial vertex and final vertex.

- A

**connected graph** is a graph where there is always a path from one vertex to another. The following graph is not connected.

- On connected graphs, a

**bridge** is an edge in which once we remove it, the graph will no longer be connected.

- An

**Eulerian graph** is a graph where we can find a

**closed** trail that goes through every edge

*exactly once*. The trail is called an

**Eulerian trail.**- A

**semi-Eulerian graph** is a graph where we can find an

**open** trail that goes through every edge

*exactly once*. The trail is called a

**semi-Eulerian trail.**- A

**Hamiltonian graph** is a graph where we can find a

**cycle** that goes through every vertex

*exactly once*.

- A

**semi-Hamiltonian graph** is a graph where we can find an

**open path** that goes through every vertex

*exactly once*.

- On directed graphs, a

**shortest path** from a vertex \(A\) to a vertex \(B\) is essentially the path, such that the sum of the weights in that path is the least possible. That is, every other path from \(A\) to \(B\) cannot have a smaller weight (i.e. sum of weights) than a shortest path. (Two vertices can have multiple shortest paths.)

*Trees*- A

**tree** is a connected graph with no

*cycles*- Given a graph, a

**spanning tree** is a subgraph that is a tree, and contains

*every vertex* of the graph.

- On weighted graphs, a

**minimum spanning tree** is a spanning tree, that has the smallest possible weight among all spanning trees. A graph can have multiple minimum spanning trees. One way of finding them is through Prim's algorithm.

*Critical path analysis*- An

**activity** is essentially a smaller task required for a big project, and are represented by

*edges* on the network. The start of an activity is denoted at a vertex.

- Given an activity \(A\), a

**predecessor** is an activity that must be done before \(A\) can be commenced. The

**immediate predecessors** of \(A\) are the ones such that the instant they're all done, \(A\) may be commenced.

- The

**EST** stands for the

**earliest start time** of an activity.

**Forward scanning** is used to determine ESTs.

- The

**LST** stands for the

**latest start time** of an activity.

**Backward scanning** is used to determine LSTs.

- The

**float time** of an activity is computed as LST minus EST

- A

**critical path** on the network diagram is a path from the first to last vertex, where all the float times are 0.

- The length of a critical path is the minimum time required to complete a project.

*Flow networks*- The

**capacity** of an edge in a flow network reflects the maximum quantity that can be in an edge.

- The

**source** is the initial vertex, and where everything departs from.

- The

**sink** is the final vertex, and where everything must arrive at.

- A

**flow** represents a way in which the object of interest can leave the source, travel through the edges, and arrive at the sink. In every flow, the amount that passes through each edge cannot exceed the capacity of the edge.

The left diagram reflects the capacities and the right diagram is one possible flow.

- A

**cut** is an imaginary line through edges in the flow network, that split the source and sink into two separate sections.

- The

**capacity** of a cut is the sum of all edges in the cut, where

*the direction of the edges is from the source to the sink*.

- A minimum cut is one which has the smallest capacity in the cut.

- The

**max-flow-min-cut** theorem says that the greatest flow we can have in the network equals the capacity of a minimum cut.