Lecture of 20220308. Example of graphs. Informal description of isomorphism. Formal definition of isomorphic graphs. Status of deciding GRAPH ISOMORPHISM and of proving that two graphs are nonisomorphic. 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 2coloring and 3colring.
 Tags
