Graph Theory is a branch of mathematics with implications/uses is computer science and other domains of study. A [[Graph]] is a structure made of nodes ("vertex") & edges connecting them. - **Degree** - how many edges a node has - In-degree & out-degree - for [[Graph|digraph]]s - **Path** - a literal path that can be traversed by following edges around the network - Simple path - doesn't repeat nodes - **Cycle** - a path starting & ending at the same node - Acyclic - a graph containing no possible cycles - **Connectedness** - does every node have a path to every other node - If every node is reachable by every other node, the graph is "connected" - **Complete** - a _super_ connected graph, where every node has an edge to every other node - Think like gravities, everything pulls on everything - **Tree** - basically a hierarchy, but you can also say this by saying the graph is _connected_ and _acyclic_ - A tree CAN have branch _merges_, though - **Bipartite** - can you separate the graph into two groups, then draw a line and have every single edge cross that line - **Subgraph** - is what it sounds like, a subset of a graph. - **Isomorphism** - graphs that draw the same network structure are "isomorphic" - **Planar** - a graph is _planar_ if you can draw it out on a 2d sheet without crossing lines - **Coloring** - a particular branch of mathematics involving coloring graphs so that no two adjacent nodes share the same color - **Weights** - weighted graphs have "weights" associated with their edges. - This seems related to [[Neutral Circuit]]s, and likely how Google Maps functions - **Traversal** - study of _path_s around a graph - Depth-first Search - Breadth-first Search - **Dijkstra's Algorithm** - finds the shortest path from a source to all possible destinations - **Eulerian Path** - a path visiting every edge of a graph exactly once - The seven bridges of konigsberg are an example - Eulerian Circuits are Eulerian paths that complete a _cycle_ - A graph has one if all vertices have an even degree, if exactly 2 have an odd degree it has a Eulerian Path, but not a eulerian circuit - **Hamiltonian Path** - a path visiting every _node_ exactly once - The knight's tour on a chess board would be an example - Hamiltonian Circuits are Hamiltonian Paths that complete a _cycle_ - There's no simple way to check for these **** # More ## Source - Some self, lots of ChatGPT - https://en.wikipedia.org/wiki/Seven_Bridges_of_Königsberg ## Related - [[Graph Database]]