โ Discrete Mathematics learning pathDiscrete Mathematics ยท Module 8 of 10
Graph theory basics
Vertices, edges, degrees and paths.
๐ Key ideas
- A graph G = (V, E) has vertices and edges; edges may be directed or undirected, weighted or not.
- Handshaking lemma: the sum of all degrees is twice the number of edges.
- Paths, cycles and connectivity describe how vertices are linked.
- Euler path uses every edge once (exists when 0 or 2 vertices have odd degree); Hamiltonian path visits every vertex once.
- Representations: adjacency matrix and adjacency list.
๐ก Real-life example: A graph is like a road map: towns are vertices and roads are edges.
DegreeNumber of edges at a vertex
Handshaking lemmaSum of degrees = 2 x edges
Euler circuitClosed walk using every edge once
Hamiltonian cycleCycle visiting every vertex once