Graph theory considered to be born with Euler, solved Konigsberg bridge problem
Town has 7 bridges in center. Was it possible to walk across each bridge just once and return to where
Euler proved it was impossible, proof involved representing problem as a graph, thoroughly ruining
Multigraph - two vertices can have more than one edge between them
Graphs very useful, can be used to represent many many different problems
Graph consists of two sets:
V: set of vertices / nodes
E: set of edges that connect the vertices
|V| = size of V, |E| size of E
Two vertices may be connected by a path. Sequence of edges that starts at one vertex, ends at another.
Simple does not pass through same vertex more than once
Cycle is path that ends at same vertex. Add complexity, may not be allowed in some systems.
If graph has V vertices, how many edges?
If every vertex connected to every other vertex, count each direction as 2 edges: v^2 - v
If tree: v - 1 (tree is specialized graph)
Min number of edges: 0
Connected graph: every pair of vertices has a path between them (tree)
Complete: every pair of vertices has an edge between them (not path, all directly connected)
Graph cannot have multiple edges between same vertices
Graph cannot have self edges, edge from and to the same vertex
Disconnected graphs can exist too
Directed graph (digraph): each edge has direction, called a directed edge, directed edge can only be
traveled in one direction. Can have vertices with two edges between them, if going different directions.
Weighted graph: each edge assigned weight, edges' weights are displayed, represent cost to travel that
edge. Could be distance. Cost depends on underlying problem. Used for wayfinding!
Can combo: directed weighted graph.
Test if empty
Determine number vertices
Does edge exist between x and y ?
Delete a vertex, associated edges
Delete an edge Return vertex with given key
Not really anything interesting, but you need to have these.
Two common implementations:
Both need list of all vertices V (other ways if you don't really have vertices)
- example: vertices are just 0 through n, just care about edges
- hash tables?
Implementation differs in recording of edges
- fast lookup of individual edges
- wasted space if sparse (few edges, trees as example)
- more space efficient (only maintain the space that is needed)
- can efficiently find all neighbours of vertex
- not as good for individual edges
Edges are recorded in a |V| * |V| matrix