ECS20 - W23 - Lecture 19 (10T): Graphs

Lecture of 2022-03-08. Example of graphs. Informal description of isomorphism. Formal definition of isomorphic graphs.  Status of deciding GRAPH ISOMORPHISM and of proving that two graphs are non-isomorphic.  Representing graphs (adjacency matrix, adjacency list) and their efficiency. Sparse vs. dense graphs.The sum of the degrees of all vertices is twice the number of edges. Eulerian graphs. A graph is Eulerian iff all of its vertices are of even degree.  Hamiltonian graphs (have a Hamiltonian cycle)..  No known algorithm to efficiently decide if a graph is Hamiltonian. Seemingly close problems with radically different complexity. Similarly for 2-coloring and 3-colring.