11 - Graphs and Applications

11.1 - Introduction

Many real-world problems can be solved using graph algorithms.
Vertex/Vertices = A point of meaning. (City, person, entity, object etc.)
Edge = Lines connecting vertex/nodes .
Directed Graph = Each edge can be used to move one way. (think of arrows)
Undirected Graph = Each edge can be used to move both ways.
Weighted Graph = Each edge has a certain indicator or weight. (This can be time, cost, distance oa.)
Unweighted Graph = Each edge is equal to one another.
Adjacent Vertices = Two vertices connected to each other via the same edge.
Incident Edges = An edge that connects two vertices.
Vertex Degree = The number of edges connected to the vertex.
Vertex Neighbors = If two edges are connected/adjecent.
Loop = An vertex that has an edge connecting it to itself.
Parallel edge = If two vertices are connected via multiple edges.
Simple Graph = A graph that has NO loops or parallel edges.
Complete Graph = A graph with all two pairs of vertices connected.
Connected Graph = A graph with paths to all vertices.
Subgraph = A graph made up of parts of another graph.
Cycle = A closed path that starts from a vertex and ends on the same vertex.
Tree= A graph is a tree when if it does not have any cycles.
Spanning Tree = A graph including all verticles, which are connected, with the least amount of edges.
Hamiltoninan path/cycle = A cycle that visits each vertex exactly once. In the cycle version it needs to end where it started.

Visiting each vertex level by level.
The first level consists of the starting vertex
Each level consists of the vertices adjacent to the vertieces in the preceding level.
Usefull cases:
- Detecting whether a graph is connected.
- Detecting whether there is a path between two vertices.
- Finding the shortest path between two vertices.
- Finding all connected components.
- Detecting/finding a cycle in the graph.