CMPT 225 Lecture Notes - Wayfinding, Graph Operations, Graph Theory
4 Sep 2013
School
Department
Course
Professor
Document Summary
Graph theory considered to be born with euler, solved konigsberg bridge problem. Was it possible to walk across each bridge just once and return to where they started. Euler proved it was impossible, proof involved representing problem as a graph, thoroughly ruining everyone"s fun. Multigraph - two vertices can have more than one edge between them. Graphs very useful, can be used to represent many many different problems. 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 every vertex connected to every other vertex, count each direction as 2 edges: v^2 - v. If tree: v - 1 (tree is specialized graph)
