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.
- Tags
-
