Graph Theory

• A graph is a set of vertices and edges.
• A vertex is one of the nodes of a graph.
• An edge connects vertices.
• An adjacency table is a table that stores the adjacency of each vertex in a graph.
• A weighted graph includes numbers allocated to each edge that represent something.
• A walk is a sequence of vertices reached by consecutively travelling along edges.
• A connected graph is when it is possible to walk between any two points.
• A subgraph is a graph which contains only vertices and edges from another graph and must have the same edges and vertices.
• A directed graph is a graph where edges have directions.
• A strongly connected graph is when vertices are connected in both directions.
• A weakly connected graph is when vertices are connected in at least one direction.
• A degree is the number of edges attached to a vertex.
• An even degree is a vertex with a degree which is an even number.
• An odd degree is a vertex with a degree which is an odd number.
• An in-degree is all edges going in.
• An out-degree is all edges going out.
• A multigraph is a graph that has more than one edge connected to it going in the same direction. It can also be a loop.
• A simple graph is any unweighted graph which is not a multigraph.
• A transition matrix takes you from one state matrix to another state matrix.
• A random walk is when a walk around a graph is equally likely to occur (ie. probability of edges isn't weighted).
• A steady state is using any initial state at a high power for the transition matrix.
• A cycle is a walk that starts and ends at the same place with no repeated vertices.
• A tree is a connected graph with no cycles.
• A spanning tree is a subgraph which contains all original vertices and is a tree.
• A minimum spanning tree is the spanning tree of least weight.
• Kruskal's Algorithm is a method to find the minimum spanning tree. First you write the edge of least weight, then add the next edge of least weight and then continue adding the edge of least weight until finished.
• Prim's Algorithm is a method for calculating a minimum spanning tree. First you select any vertex and draw the edge of least weight attached to it. Then, you add the edge of least weight attached to your existing graph without creating a cycle and keep on attaching the next edge of least weight until complete.
• A trail is a walk with no repeated edges.
• A circuit is a trail that starts and ends at the same vertex.
• Eulerian is a path that visits every edge on a graph.
• An eulerian circuit is a path that visits all edges and returns to the start.
• An eulerian trail is a path that visits all edges and does not return to the start.
• The Chinese Postman Problem is the least weight to visit all edges and return to the start.
• A path is a walk that doesn't pass through any vertex more than once.
• A cycle is a path which ends where it started.
• A hamiltonian passes through all vertices.
• A complete graph is when all vertices are directly attached to every other vertex.
• The travelling salesman problem is finding the walk of least weight by visiting every vertex and returning to the start.
• The classical salesman problem is a complete graph.
• A practical salesmen problem is when a table of least weights is used to construct fake connections.